Improved online algorithm for fractional knapsack in the random order model

DOI10.1007/978-3-030-92702-8_12OpenAlexW3196368932MaRDI QIDQ2085749

Andreas Karrenbauer, Jeff Giliberti

Publication date: 19 October 2022

Full work available at URL: https://arxiv.org/abs/2109.04428

zbMATH Keywords

online algorithmsrandom order modelfractional knapsack

Mathematics Subject Classification ID

Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)

Related Items (1)

Knapsack secretary through boosting

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The robust knapsack problem with queries
• Randomized algorithms for online knapsack problems
• Online unweighted knapsack problem with removal cost
• Stochastic on-line knapsack problems
• Improved online algorithms for Knapsack and GAP in the random order model
• The online knapsack problem: advice and randomization
• New results for the \(k\)-secretary problem
• Reading articles online
• An Optimal Online Algorithm for Weighted Bipartite Matching and Extensions to Combinatorial Auctions
• Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity
• A Knapsack Secretary Problem with Applications
• Average-Case Analysis of Off-Line and On-Line Knapsack Problems
• Matroid Secretary Problems
• Primal beats dual on online packing LPs in the random-order model
• Revealing Optimal Thresholds for Generalized Secretary Problem via Continuous LP: Impacts on Online K-Item Auction and Bipartite K-Matching with Random Arrival Order
• A Simple O(log log(rank))-Competitive Algorithm for the Matroid Secretary Problem
• Algorithms – ESA 2005
• Dynamic Programming and Decision Theory

This page was built for publication: Improved online algorithm for fractional knapsack in the random order model