The Design of Competitive Online Algorithms via a Primal—Dual Approach
From MaRDI portal
Publication:3636884
DOI10.1561/0400000024zbMath1190.68083OpenAlexW4206478994MaRDI QIDQ3636884
Niv Buchbinder, Joseph (Seffi) Naor
Publication date: 30 June 2009
Published in: Foundations and Trends® in Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1561/0400000024
Research exposition (monographs, survey articles) pertaining to computer science (68-02) Approximation algorithms (68W25) Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27)
Related Items (35)
On the Randomized Competitive Ratio of Reordering Buffer Management with Non-Uniform Costs ⋮ Design of Dynamic Algorithms via Primal-Dual Method ⋮ On Randomized Algorithms for Matching in the Online Preemptive Model ⋮ Online Linear Programming: Dual Convergence, New Algorithms, and Regret Bounds ⋮ Dynamic algorithms via the primal-dual method ⋮ The Power of Deferral: Maintaining a Constant-Competitive Steiner Tree Online ⋮ Competitive online algorithms for resource allocation over the positive semidefinite cone ⋮ A Dynamic Near-Optimal Algorithm for Online Linear Programming ⋮ A primal-dual online algorithm for the \(k\)-server problem on weighted HSTs ⋮ Primal-dual analysis for online interval scheduling problems ⋮ Advertisement allocation for generalized second-pricing schemes ⋮ Coupled and \(k\)-sided placements: generalizing generalized assignment ⋮ Dynamic clustering to minimize the sum of radii ⋮ Online covering with \(\ell_q\)-norm objectives and applications to network design ⋮ Unnamed Item ⋮ Online Algorithms for Multilevel Aggregation ⋮ An Approximation Algorithm for Network Revenue Management Under Nonstationary Arrivals ⋮ Online Node-weighted Steiner Forest and Extensions via Disk Paintings ⋮ Unnamed Item ⋮ Approximating Sparse Covering Integer Programs Online ⋮ Welfare maximization with production costs: a primal dual approach ⋮ A randomized \(O(\log n)\)-competitive algorithm for the online connected facility location problem ⋮ Online \(k\)-taxi via double coverage and time-reverse primal-dual ⋮ Unified Algorithms for Online Learning and Competitive Analysis ⋮ Unnamed Item ⋮ Online \(k\)-taxi via double coverage and time-reverse primal-dual ⋮ Game efficiency through linear programming duality ⋮ How the Experts Algorithm Can Help Solve LPs Online ⋮ Unnamed Item ⋮ Online Resource Allocation Under Partially Predictable Demand ⋮ A nonmonotone analysis with the primal-dual approach: online routing of virtual circuits with unknown durations ⋮ Incentive compatible mulit-unit combinatorial auctions: a primal dual approach ⋮ Almost Tight Bounds for Reordering Buffer Management ⋮ A Nonmonotone Analysis with the Primal-Dual Approach: Online Routing of Virtual Circuits with Unknown Durations ⋮ How to allocate goods in an online market?
This page was built for publication: The Design of Competitive Online Algorithms via a Primal—Dual Approach
