A Knapsack Secretary Problem with Applications

DOI10.1007/978-3-540-74208-1_2zbMath1171.90417OpenAlexW2164792208MaRDI QIDQ3603454

Nicole Immorlica, David Kempe, Moshe Babaioff, Robert D. Kleinberg

Publication date: 17 February 2009

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-74208-1_2

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Management decision making, including multiple objectives (90B50) Stopping times; optimal stopping problems; gambling theory (60G40) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)

Related Items (45)

Packing a Knapsack of Unknown Capacity ⋮ The online knapsack problem with incremental capacity ⋮ Prophet Secretary ⋮ The simulated greedy algorithm for several submodular matroid secretary problems ⋮ Prophet Secretary ⋮ The Temp Secretary Problem ⋮ Formal barriers to simple algorithms for the matroid secretary problem ⋮ Primal Beats Dual on Online Packing LPs in the Random-Order Model ⋮ Online network design with outliers ⋮ A Dynamic Near-Optimal Algorithm for Online Linear Programming ⋮ New results for the \(k\)-secretary problem ⋮ A Framework for the Secretary Problem on the Intersection of Matroids ⋮ Stochastic models for budget optimization in search-based advertising ⋮ Analysis of the ``hiring above the median selection strategy for the hiring problem ⋮ A note on the online interval scheduling secretary problem ⋮ Packing returning secretaries ⋮ Machine covering in the random-order model ⋮ Relative Worst-Order Analysis: A Survey ⋮ Unnamed Item ⋮ Knapsack secretary through boosting ⋮ Uniformly Bounded Regret in the Multisecretary Problem ⋮ Longest Increasing Subsequences of Randomly Chosen Multi-Row Arrays ⋮ The secretary problem with reservation costs ⋮ Randomized algorithms for online knapsack problems ⋮ Improved Online Algorithms for Knapsack and GAP in the Random Order Model ⋮ The Submodular Secretary Problem Goes Linear ⋮ Scheduling In the random-order model ⋮ Approximate and exact merging of knapsack constraints with cover inequalities ⋮ Buyback Problem - Approximate Matroid Intersection with Cancellation Costs ⋮ On the sum minimization version of the online bin covering problem ⋮ Unnamed Item ⋮ Prior independent mechanisms via prophet inequalities with limited information ⋮ Optimal composition ordering problems for piecewise linear functions ⋮ Upper bounds for the 0-1 stochastic knapsack problem and a B\&B algorithm ⋮ Improved online algorithms for Knapsack and GAP in the random order model ⋮ Improved Competitive Ratios for Submodular Secretary Problems (Extended Abstract) ⋮ Online Collaborative Filtering on Graphs ⋮ How the Experts Algorithm Can Help Solve LPs Online ⋮ Strong Algorithms for the Ordinal Matroid Secretary Problem ⋮ Improved online algorithm for fractional knapsack in the random order model ⋮ Online algorithms for the maximum \(k\)-interval coverage problem ⋮ Unnamed Item ⋮ Online generalized assignment problem with historical information ⋮ Budget-Feasible Mechanism Design for Non-monotone Submodular Objectives: Offline and Online ⋮ Prophet secretary for \(k\)-knapsack and \(l\)-matroid intersection via continuous exchange property

This page was built for publication: A Knapsack Secretary Problem with Applications