Improved online algorithms for Knapsack and GAP in the random order model
From MaRDI portal
Publication:2032350
DOI10.1007/s00453-021-00801-2OpenAlexW3133095683MaRDI QIDQ2032350
Arindam Khan, Susanne Albers, Leon Ladewig
Publication date: 11 June 2021
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2012.00497
Related Items
Machine covering in the random-order model ⋮ Approximation schemes for packing problems with \(\ell_p\)-norm diversity constraints ⋮ Knapsack secretary through boosting ⋮ Improved online algorithm for fractional knapsack in the random order model ⋮ Prophet secretary for \(k\)-knapsack and \(l\)-matroid intersection via continuous exchange property
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Randomized algorithms for online knapsack problems
- Online unweighted knapsack problem with removal cost
- A survey of algorithms for the generalized assignment problem
- On-line algorithms for weighted bipartite matching and stable marriages
- Stochastic on-line knapsack problems
- Approximation and online algorithms for multidimensional bin packing: a survey
- New results for the \(k\)-secretary problem
- Geometry of Online Packing Linear Programs
- An Optimal Online Algorithm for Weighted Bipartite Matching and Extensions to Combinatorial Auctions
- The Online Stochastic Generalized Assignment Problem
- A Dynamic Near-Optimal Algorithm for Online Linear Programming
- Online Primal-Dual Algorithms for Covering and Packing
- Online Appointment Scheduling in the Random Order Model
- AdWords and generalized online matching
- Online Stochastic Packing Applied to Display Ad Allocation
- A Knapsack Secretary Problem with Applications
- Recognizing both the maximum and the second maximum of a sequence
- On a Generalization of the Best Choice Problem
- Average-Case Analysis of Off-Line and On-Line Knapsack Problems
- Primal Beats Dual on Online Packing LPs in the Random-Order Model
- Online Submodular Welfare Maximization: Greedy Beats 1/2 in Random Order
- Online and Random-order Load Balancing Simultaneously
- Matroid Secretary Problems
- A Simple O(log log(rank))-Competitive Algorithm for the Matroid Secretary Problem
- Revealing Optimal Thresholds for Generalized Secretary Problem via Continuous LP: Impacts on Online K-Item Auction and Bipartite K-Matching with Random Arrival Order
- Online bipartite matching with random arrivals
- A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem
- Dynamic Programming and Decision Theory
- A Survey of the Generalized Assignment Problem and Its Applications
