Revealing Optimal Thresholds for Generalized Secretary Problem via Continuous LP: Impacts on Online K-Item Auction and Bipartite K-Matching with Random Arrival Order

DOI10.1137/1.9781611973730.78MaRDI QIDQ5363004zbMATH OpenOpenAlexFDO

Authors T.-H. Hubert Chan, Fei Chen, Shaofeng H.-C. Jiang

Publication date 5 October 2017

Published in Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/1.9781611973730.78

Mathematics Subject Classification ID

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

Recommendations

• Online k-max Search Algorithms with Applications to the Secretary Problem
• A multiple-choice secretary algorithm with applications to online auctions
• An optimal online algorithm for weighted bipartite matching and extensions to combinatorial auctions
• Online bipartite matching with random arrivals, an approach based on strongly factor-revealing LPs
• Improved competitive ratios for submodular secretary problems (extended abstract)
• An optimally-competitive algorithm for maximum online perfect bipartite matching with i.i.d. arrivals
• The online stochastic generalized assignment problem
• Online stochastic matching, poisson arrivals, and the natural linear program
• On extensions of the deterministic online model for bipartite matching and max-sat
• Online vertex-weighted bipartite matching and single-bid budgeted allocations

Cited in

(9)

• Knapsack secretary through boosting
• Improved online algorithm for fractional knapsack in the random order model
• New results for the \(k\)-secretary problem
• Strong algorithms for the ordinal matroid secretary problem
• Improved online algorithms for knapsack and GAP in the random order model
• Improved Online Algorithms for Knapsack and GAP in the Random Order Model
• The solution of a generalized secretary problem via analytic expressions
• The secretary problem with reservation costs
• A satisficing policy of the secretary problem: theory and simulation

This page was built for publication: Revealing Optimal Thresholds for Generalized Secretary Problem via Continuous LP: Impacts on Online K-Item Auction and Bipartite K-Matching with Random Arrival Order

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