Online (J, K)-search problem and its competitive analysis

DOI10.1016/J.TCS.2015.06.005MaRDI QIDQ501005zbMATH OpenOpenAlexFDO

Authors Yong-Cai Geng, Sumit K. Garg

Publication date 8 October 2015

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2015.06.005

zbMATH Keywords

online algorithmscompetitive ratioonline search problem

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Auctions, bargaining, bidding and selling, and other market models (91B26)

Recommendations

• Online algorithms for the general k-search problem
• Online two stage k-search problem and its competitive analysis
• Optimal online \(k\)-min search
• Optimal search and one-way trading online algorithms
• An online trading problem with an increasing number of available products

Cites work

• A multiple-choice secretary algorithm with applications to online auctions
• Average-case competitive analyses for one-way trading
• Matroids, secretary problems, and online mechanisms
• Online algorithms for the general k-search problem
• Online algorithms for the multiple time series search problem
• Online search with time-varying price bounds
• Optimal algorithms for \(k\)-search with application in option pricing
• Optimal algorithms for the online time series search problem
• Optimal search and one-way trading online algorithms
• Optimal selection based on relative rank (the 'Secretary Problem')

Cited in

(8)

• Algorithms – ESA 2004
• Optimal online \(k\)-min search
• Optimal replenishment under price uncertainty
• Online two stage k-search problem and its competitive analysis
• An online trading problem with an increasing number of available products
• Online k-max Search Algorithms with Applications to the Secretary Problem
• Competitive analysis for two variants of online metric matching problem
• Online algorithms for the general k-search problem

This page was built for publication: Online \((J, K)\)-search problem and its competitive analysis

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q501005)