A Knapsack Secretary Problem with Applications

DOI10.1007/978-3-540-74208-1_2zbMATH Open1171.90417OpenAlexW2164792208MaRDI QIDQ3603454FDOQ3603454

Authors: Moshe Babaioff, Nicole Immorlica, David Kempe, 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

Recommendations

• scientific article; zbMATH DE number 4005976
• scientific article; zbMATH DE number 1302173
• scientific article; zbMATH DE number 3852791
• The constrained compartmentalised knapsack problem
• Knapsack problems: a parameterized point of view
• Knapsack problems with setups
• The knapsack problem with a minimum filling constraint
• scientific article; zbMATH DE number 4031399

Mathematics Subject Classification ID

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

Cited In (50)

• Stochastic models for budget optimization in search-based advertising
• Algorithms for maximum social welfare of online random trading
• Primal beats dual on online packing LPs in the random-order model
• Strong algorithms for the ordinal matroid secretary problem
• A Framework for the Secretary Problem on the Intersection of Matroids
• Improved Online Algorithms for Knapsack and GAP in the Random Order Model
• Title not available (Why is that?)
• Prophet secretary
• Prophet secretary
• Longest Increasing Subsequences of Randomly Chosen Multi-Row Arrays
• Prophet secretary for \(k\)-knapsack and \(l\)-matroid intersection via continuous exchange property
• The submodular secretary problem goes linear
• The online knapsack problem with incremental capacity
• Online collaborative filtering on graphs
• Randomized algorithms for online knapsack problems
• The Temp Secretary Problem
• The simulated greedy algorithm for several submodular matroid secretary problems
• Optimal composition ordering problems for piecewise linear functions
• Scheduling In the random-order model
• Improved online algorithms for knapsack and GAP in the random order model
• Upper bounds for the 0-1 stochastic knapsack problem and a B\&B algorithm
• On the sum minimization version of the online bin covering problem
• Secretary problems with convex costs
• Formal barriers to simple algorithms for the matroid secretary problem
• Budget-feasible mechanism design for non-monotone submodular objectives: offline and online
• Approximate and exact merging of knapsack constraints with cover inequalities
• Packing a knapsack of unknown capacity
• New results for the \(k\)-secretary problem
• Online network design with outliers
• Relative Worst-Order Analysis: A Survey
• Improved competitive ratios for submodular secretary problems (extended abstract)
• A note on the online interval scheduling secretary problem
• Prior independent mechanisms via prophet inequalities with limited information
• How experts can solve LPs online
• A dynamic near-optimal algorithm for online linear programming
• Packing returning secretaries
• Improved competitive ratio for the matroid secretary problem
• Knapsack secretary through boosting
• Online generalized assignment problem with historical information
• Exploiting action impact regularity and exogenous state variables for offline reinforcement learning
• Online algorithms for the maximum \(k\)-interval coverage problem
• Uniformly bounded regret in the multisecretary problem
• Machine covering in the random-order model
• The secretary problem with reservation costs
• Two-set inequalities for the binary knapsack polyhedra
• Analysis of the ``hiring above the median selection strategy for the hiring problem
• Improved online algorithm for fractional knapsack in the random order model
• Maximizing profit with convex costs in the random-order model
• Buyback problem -- approximate matroid intersection with cancellation costs
• Online budgeted maximum coverage

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

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