EUVIMEDAtrasti EUVIMED
Crossref

The Design of Competitive Online Algorithms via a Primal—Dual Approach

Niv Buchbinder, Joseph (Seffi) Naor

Foundations and Trends® in Theoretical Computer Science · 2009-05-15 · 3 (2-3) · 93-263

DOI: 10.1561/0400000024 ↗

At a glance

Journal article in Foundations and Trends® in Theoretical Computer Science, published online on 2009-05-15. Written by Niv Buchbinder and 1 co-authors. Cited 220 times so far (Crossref); 94 references.

SantraukaBibliografiniai duomenysCiteRelated studies

Abstract (original language)

The primal—dual method is a powerful algorithmic technique that has proved to be extremely useful for a wide variety of problems in the area of approximation algorithms for NP-hard problems. The method has its origins in the realm of exact algorithms, e.g., for matching and network flow. In the area of approximation algorithms, the primal—dual method has emerged as an important unifying design methodology, starting from the seminal work of Goemans and Williamson [60] We show in this survey how to extend the primal—dual method to the setting of online algorithms, and show its applicability to a wide variety of fundamental problems. Among the online problems that we consider here are the weighted caching problem, generalized caching, the set-cover problem, several graph optimization problems, routing, load balancing, and the problem of allocating ad-auctions. We also show that classic online problems such as the ski rental problem and the dynamic TCP-acknowledgement problem can be solved optimally using a simple primal—dual approach. The primal—dual method has several advantages over existing methods. First, it provides a general recipe for the design and analysis of online algorithms. The linear programming formulation helps detecting the difficulties of the online problem, and the analysis of the competitive ratio is direct, without a potential function appearing "out of nowhere." Finally, since the analysis is done via duality, the competitiveness of the online algorithm is with respect to an optimal fractional solution, which can be advantageous in certain scenarios.

Cite

APA

Buchbinder, N., & Naor, J. S. (2009). The Design of Competitive Online Algorithms via a Primal—Dual Approach. Foundations and Trends® in Theoretical Computer Science, 3(2-3), 93-263. https://doi.org/10.1561/0400000024

Vancouver

Buchbinder N, Naor JS. The Design of Competitive Online Algorithms via a Primal—Dual Approach. Foundations and Trends® in Theoretical Computer Science. 2009;3(2-3):93-263. doi:10.1561/0400000024

BibTeX
@article{Buchbinder2009,
  author = {Buchbinder, Niv and Naor, Joseph (Seffi)},
  title = {The Design of Competitive Online Algorithms via a Primal—Dual Approach},
  journal = {Foundations and Trends® in Theoretical Computer Science},
  year = {2009},
  volume = {3},
  number = {2-3},
  pages = {93--263},
  doi = {10.1561/0400000024}
}
Start for free →