Generalized assignment and knapsack problems in the random-order model

DOI10.1007/978-3-031-93112-3_25MaRDI QIDQ6880123zbMATH OpenFDO

Authors Max Klimm, Martin Knaack

Publication date 22 December 2025

Full work available at URL https://doi.org/10.1007/978-3-031-93112-3_25

zbMATH Keywords

generalized assignment problemknapsack problemonline optimizationrandom-order model

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Discrete location and assignment (90B80) Combinatorial optimization (90C27)

Cites work

• O( rank) competitive ratio for the matroid secretary problem
• A dynamic near-optimal algorithm for online linear programming
• A Knapsack Secretary Problem with Applications
• A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem
• A simple \(O(\log\log(\mathrm{rank}))\)-competitive algorithm for the matroid secretary problem
• Algorithms for Secretary Problems on Graphs and Hypergraphs
• An approximation algorithm for the generalized assignment problem
• An optimal online algorithm for weighted bipartite matching and extensions to combinatorial auctions
• Combinatorial optimization. Theory and algorithms
• Dynamic Programming and Decision Theory
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Formal barriers to simple algorithms for the matroid secretary problem
• scientific article; zbMATH DE number 44282 (Why is no real title available?)
• scientific article; zbMATH DE number 7650243 (Why is no real title available?)
• Improved competitive ratio for the matroid secretary problem
• Improved online algorithm for fractional knapsack in the random order model
• Improved online algorithms for knapsack and GAP in the random order model
• Knapsack secretary through boosting
• Matroid Secretary Problems
• Matroids, secretary problems, and online mechanisms
• Online bipartite matching with random arrivals, an approach based on strongly factor-revealing LPs
• Online primal-dual algorithms for covering and packing
• Primal beats dual on online packing LPs in the random-order model
• Prophet inequalities for independent and identically distributed random variables from an unknown distribution
• Randomized algorithms for online knapsack problems
• Reading articles online
• Reducibility among combinatorial problems
• Strong algorithms for the ordinal matroid secretary problem
• The simulated greedy algorithm for several submodular matroid secretary problems

This page was built for publication: Generalized assignment and knapsack problems in the random-order model

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