The Design of Competitive Online Algorithms via a Primal—Dual Approach
- 1 January 2007
- journal article
- research article
- Published by Now Publishers in Foundations and Trends® in Theoretical Computer Science
- Vol. 3 (2–3), 93-263
- https://doi.org/10.1561/0400000024
Abstract
Publishers of Foundations and Trends, making research accessibleKeywords
This publication has 12 references indexed in Scilit:
- AdWords and generalized online matchingJournal of the ACM, 2007
- A general approach to online network optimization problemsACM Transactions on Algorithms, 2006
- A randomized on–line algorithm for thek–server problem on a lineRandom Structures & Algorithms, 2006
- Simultaneous Optimization via Approximate Majorization for Concave Profits or Convex CostsAlgorithmica, 2005
- Randomized k-server algorithms for growth-rate bounded graphsJournal of Algorithms, 2005
- A tight bound on approximating arbitrary metrics by tree metricsJournal of Computer and System Sciences, 2004
- A Linear Programming Formulation and Approximation Algorithms for the Metric Labeling ProblemSIAM Journal on Discrete Mathematics, 2004
- Combining Fairness with Throughput: Online Routing with Multiple ObjectivesJournal of Computer and System Sciences, 2001
- A Polylogarithmic Approximation Algorithm for the Group Steiner Tree ProblemJournal of Algorithms, 2000
- On the ratio of optimal integral and fractional coversDiscrete Mathematics, 1975