The Design of Competitive Online Algorithms via a Primal—Dual Approach
From MaRDI portal
Publication:3636884
DOI10.1561/0400000024zbMath1190.68083MaRDI 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
68-02: Research exposition (monographs, survey articles) pertaining to computer science
68W25: Approximation algorithms
68W20: Randomized algorithms
68W27: Online algorithms; streaming algorithms
Related Items
Unnamed Item, Unnamed Item, Unnamed Item, Online Resource Allocation Under Partially Predictable Demand, Online Linear Programming: Dual Convergence, New Algorithms, and Regret Bounds, Online Algorithms for Multilevel Aggregation, An Approximation Algorithm for Network Revenue Management Under Nonstationary Arrivals, Approximating Sparse Covering Integer Programs Online, Game efficiency through linear programming duality, Online Node-weighted Steiner Forest and Extensions via Disk Paintings, Online \(k\)-taxi via double coverage and time-reverse primal-dual, Online \(k\)-taxi via double coverage and time-reverse primal-dual, Almost Tight Bounds for Reordering Buffer Management, Unnamed Item, How to allocate goods in an online market?, Advertisement allocation for generalized second-pricing schemes, A randomized \(O(\log n)\)-competitive algorithm for the online connected facility location problem, Coupled and \(k\)-sided placements: generalizing generalized assignment, Dynamic algorithms via the primal-dual method, Competitive online algorithms for resource allocation over the positive semidefinite cone, A primal-dual online algorithm for the \(k\)-server problem on weighted HSTs, Primal-dual analysis for online interval scheduling problems, Dynamic clustering to minimize the sum of radii, Online covering with \(\ell_q\)-norm objectives and applications to network design, Welfare maximization with production costs: a primal dual approach, 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, Unified Algorithms for Online Learning and Competitive Analysis, How the Experts Algorithm Can Help Solve LPs Online, A Nonmonotone Analysis with the Primal-Dual Approach: Online Routing of Virtual Circuits with Unknown Durations, A Dynamic Near-Optimal Algorithm for Online Linear Programming, 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, The Power of Deferral: Maintaining a Constant-Competitive Steiner Tree Online
