Improved online algorithms for Knapsack and GAP in the random order model
type: Item
instance of: scholarly article
title: Improved online algorithms for Knapsack and GAP in the random order model
author: Susanne Albers
author: Arindam Khan
author: Leon Ladewig
published in: Algorithmica
publication date: 2021-06-11T00:00:00Z
full work available at URL: https://arxiv.org/abs/2012.00497
Mathematics Subject Classification ID: 68Wxx
Mathematics Subject Classification ID: 05Cxx
zbMATH DE Number: 7357818
zbMATH Keywords: online algorithms
zbMATH Keywords: random order model
zbMATH Keywords: packing problems
MaRDI profile type: Publication
OpenAlex ID: W3133095683
cites work: Q4821303
cites work: Q3993418
cites work: Approximation and online algorithms for multidimensional bin packing: a survey
cites work: A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem
cites work: On-line algorithms for weighted bipartite matching and stable marriages
cites work: AdWords and generalized online matching
cites work: A survey of algorithms for the generalized assignment problem
cites work: A Survey of the Generalized Assignment Problem and Its Applications
cites work: Q5653410
cites work: Dynamic Programming and Decision Theory
cites work: Matroid Secretary Problems
cites work: A Simple O(log log(rank))-Competitive Algorithm for the Matroid Secretary Problem
cites work: Revealing Optimal Thresholds for Generalized Secretary Problem via Continuous LP: Impacts on Online K-Item Auction and Bipartite K-Matching with Random Arrival Order
cites work: A multiple-choice secretary algorithm with applications to online auctions
cites work: Online Appointment Scheduling in the Random Order Model
cites work: Online and Random-order Load Balancing Simultaneously
cites work: A Dynamic Near-Optimal Algorithm for Online Linear Programming
cites work: Online Stochastic Packing Applied to Display Ad Allocation
cites work: Q4875207
cites work: Primal Beats Dual on Online Packing LPs in the Random-Order Model
cites work: Geometry of Online Packing Linear Programs
cites work: Q5417603
cites work: An Optimal Online Algorithm for Weighted Bipartite Matching and Extensions to Combinatorial Auctions
cites work: Online bipartite matching with random arrivals
cites work: Q5743510
cites work: Online Submodular Welfare Maximization: Greedy Beats 1/2 in Random Order
cites work: Stochastic on-line knapsack problems
cites work: A Knapsack Secretary Problem with Applications
cites work: Average-Case Analysis of Off-Line and On-Line Knapsack Problems
cites work: Randomized algorithms for online knapsack problems
cites work: Q4737165
cites work: Online unweighted knapsack problem with removal cost
cites work: The Online Stochastic Generalized Assignment Problem
cites work: Online Primal-Dual Algorithms for Covering and Packing
cites work: New results for the \(k\)-secretary problem
cites work: On a Generalization of the Best Choice Problem
cites work: Recognizing both the maximum and the second maximum of a sequence
DOI: 10.1007/S00453-021-00801-2
description: scientific article; zbMATH DE number 7357818