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.78zbMath1375.91188OpenAlexW4247158798MaRDI QIDQ5363004

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

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

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

Related Items (9)

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

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