Improved Online Algorithms for Knapsack and GAP in the Random Order Model
From MaRDI portal
Publication:5875474
DOI10.4230/LIPICS.APPROX-RANDOM.2019.22OpenAlexW2977419720MaRDI QIDQ5875474FDOQ5875474
Authors: Susanne Albers, Arindam Khan, Leon Ladewig 
Publication date: 3 February 2023
Full work available at URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2019.22
Recommendations
Cites Work
- Title not available (Why is that?)
- A survey of algorithms for the generalized assignment problem
- Title not available (Why is that?)
- A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem
- On-line algorithms for weighted bipartite matching and stable marriages
- Stochastic on-line knapsack problems
- Online primal-dual algorithms for covering and packing
- AdWords and generalized online matching
- Average-Case Analysis of Off-Line and On-Line Knapsack Problems
- Title not available (Why is that?)
- Approximating Geometric Knapsack via L-packings
- Title not available (Why is that?)
- A Knapsack Secretary Problem with Applications
- Randomized algorithms for online knapsack problems
- A multiple-choice secretary algorithm with applications to online auctions
- Online stochastic packing applied to display ad allocation
- The Secretary Problem and Its Extensions: A Review
- Online bipartite matching with random arrivals, an approach based on strongly factor-revealing LPs
- A Survey of the Generalized Assignment Problem and Its Applications
- Title not available (Why is that?)
- Profit-earning facility location
- Dynamic Programming and Decision Theory
- Online unweighted knapsack problem with removal cost
- Approximation and online algorithms for multidimensional bin packing: a survey
- Recognizing both the maximum and the second maximum of a sequence
- On a Generalization of the Best Choice Problem
- An optimal online algorithm for weighted bipartite matching and extensions to combinatorial auctions
- Online appointment scheduling in the random order model
- Matroid Secretary Problems
- Revealing Optimal Thresholds for Generalized Secretary Problem via Continuous LP: Impacts on Online K-Item Auction and Bipartite K-Matching with Random Arrival Order
- Primal beats dual on online packing LPs in the random-order model
- Online submodular welfare maximization: greedy beats 1/2 in random order
- A 1.43-competitive online graph edge coloring algorithm in the random order arrival model
- Title not available (Why is that?)
Cited In (2)
This page was built for publication: Improved Online Algorithms for Knapsack and GAP in the Random Order Model
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5875474)
