Primal beats dual on online packing LPs in the random-order model

DOI10.1137/15M1033708MaRDI QIDQ4554073zbMATH OpenOpenAlexWikidataFDO

Authors Thomas Kesselheim, Klaus Radke, Andreas Tönnis, Berthold Vöcking

Publication date 7 November 2018

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/15m1033708

zbMATH Keywords

secretary problemgeneralized assignment problempacking linear program

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Analysis of algorithms and problem complexity (68Q25) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08)

Recommendations

• Primal beats dual on online packing LPs in the random-order model

Cites work

• scientific article; zbMATH DE number 5764830 (Why is no real title available?)
• scientific article; zbMATH DE number 3383344 (Why is no real title available?)
• A Knapsack Secretary Problem with Applications
• A dynamic near-optimal algorithm for online linear programming
• A multiple-choice secretary algorithm with applications to online auctions
• AdWords and generalized online matching
• Algorithms for Secretary Problems on Graphs and Hypergraphs
• An optimal online algorithm for weighted bipartite matching and extensions to combinatorial auctions
• Approximability of sparse integer programs
• Dynamic Programming and Decision Theory
• Fast algorithms for online stochastic convex programming
• Online bipartite matching with random arrivals, an approach based on strongly factor-revealing LPs
• Online bipartite matching with unknown distributions
• Online primal-dual algorithms for covering and packing
• Online stochastic packing applied to display ad allocation
• Randomized Distributed Edge Coloring via an Extension of the Chernoff--Hoeffding Bounds
• Secretary Problems with Non-Uniform Arrival Order
• Solving packing integer programs via randomized rounding with alterations
• Truthful and Near-Optimal Mechanism Design via Linear Programming

Cited in

(14)

• Improved Online Algorithms for Knapsack and GAP in the Random Order Model
• New bounds for online packing LPs
• Primal beats dual on online packing LPs in the random-order model
• Online lower bounds via duality
• Improved online algorithms for knapsack and GAP in the random order model
• Monotone \(k\)-submodular secretary problems: cardinality and knapsack constraints
• Online stochastic packing applied to display ad allocation
• A dynamic near-optimal algorithm for online linear programming
• Packing returning secretaries
• Online generalized assignment problem with historical information
• Knapsack secretary through boosting
• Machine covering in the random-order model
• Near optimal online algorithms and fast approximation algorithms for resource allocation problems
• A truthful near-optimal mechanism for online linear packing-covering problem in the random order model

This page was built for publication: Primal beats dual on online packing LPs in the random-order model

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