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.78zbMATH Open1375.91188OpenAlexW4247158798MaRDI QIDQ5363004FDOQ5363004
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
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
Online algorithms; streaming algorithms (68W27) Auctions, bargaining, bidding and selling, and other market models (91B26) Matching models (91B68)
Cited In (9)
- Strong algorithms for the ordinal matroid secretary problem
- Improved Online Algorithms for Knapsack and GAP in the Random Order Model
- A satisficing policy of the secretary problem: theory and simulation
- The solution of a generalized secretary problem via analytic expressions
- Improved online algorithms for knapsack and GAP in the random order model
- New results for the \(k\)-secretary problem
- Knapsack secretary through boosting
- The secretary problem with reservation costs
- 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
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5363004)
