The DOI matches its Crossref record; 57 of the 57 references it cites were found in a registry or an index.
The Design of Competitive Online Algorithms via a Primal—Dual Approach
Abstract
The Design of Competitive Online Algorithms via a Primal-Dual Approach extends the primal-dual method to the setting of online algorithms, and shows its applicability to a wide variety of fundamental problems. Among the online problems considered 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. There is also an illustration of how 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 Design of Competitive Online Algorithms via a Primal-Dual Approach is an invaluable reference for anyone working in the area of computational theory, and especially those interested in exploring online scenarios that can benefit from the primal-dual framework.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Bertsekas, D. P., & Gallager, R. G. (1987) · Cited by 5,561
Spencer, J. (1991) · Medical Entomology and Zoology · Cited by 4,310
(2011) · SpringerReference · doi:10.1007/springerreference_57547 · Cited by 3,190
Approximation Algorithms for NP-Hard Problems
(1997) · ACM SIGACT News · doi:10.1145/261342.571216 · Cited by 3,103
A threshold of ln n for approximating set cover
Feige, U. (1998) · Journal of the ACM · doi:10.1145/285055.285059 · Cited by 3,086
A Greedy Heuristic for the Set-Covering Problem
Chvatal, V. (1979) · Mathematics of Operations Research · doi:10.1287/moor.4.3.233 · Cited by 2,581
Online Computation and Competitive Analysis
Borodin, A., & El‐Yaniv, R. (1998) · Cited by 2,333
Approximation algorithms for combinatorial problems
Johnson, D. S. (1974) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(74)80044-9 · Cited by 2,197
Amortized efficiency of list update and paging rules
Sleator, D. D., & Tarjan, R. E. (1985) · Communications of the ACM · doi:10.1145/2786.2793 · Cited by 2,123
Bounds for Certain Multiprocessing Anomalies
Graham, R. L. (1966) · Bell System Technical Journal · doi:10.1002/j.1538-7305.1966.tb01709.x · Cited by 1,647
On the ratio of optimal integral and fractional covers
Lovász, L. (1975) · Discrete Mathematics · doi:10.1016/0012-365x(75)90058-8 · Cited by 1,114
Randomized rounding: A technique for provably good algorithms and algorithmic proofs
Raghavan, P., & Tompson, C. D. (1987) · Combinatorica · doi:10.1007/bf02579324 · Cited by 1,010
Cost-aware WWW proxy caching algorithms
Cao, P., & Irani, S. (1997) · Cited by 925
A General Approximation Technique for Constrained Forest Problems
Goemans, M. X., & Williamson, D. P. (1995) · SIAM Journal on Computing · doi:10.1137/s0097539793242618 · Cited by 884
Faster and simpler algorithms for multicommodity flow and other fractional packing problems
Garg, N., & Könemann, J. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1998.743463 · Cited by 584
A tight bound on approximating arbitrary metrics by tree metrics
Fakcharoenphol, J., Rao, S. B., & Talwar, K. (2003) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/780542.780608 · Cited by 566
Probabilistic construction of deterministic algorithms: Approximating packing integer programs
Raghavan, P. (1988) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(88)90003-7 · Cited by 554
Fast Approximation Algorithms for Fractional Packing and Covering Problems
Plotkin, S. A., Shmoys, D. B., & Tardos, É. (1995) · Mathematics of Operations Research · doi:10.1287/moor.20.2.257 · Cited by 542
Fiat, A., Karp, R. M., Luby, M., McGeoch, L. A., Sleator, D. D., & Young, N. E. (1991) · Journal of Algorithms · doi:10.1016/0196-6774(91)90041-v · Cited by 457
Jaffe, J. (1981) · IEEE Transactions on Communications · doi:10.1109/tcom.1981.1095081 · Cited by 455
A linear-time approximation algorithm for the weighted vertex cover problem
Bar-Yehuda, R., & Even, S. (1981) · Journal of Algorithms · doi:10.1016/0196-6774(81)90020-1 · Cited by 430
Imase, M., & Waxman, B. M. (1991) · SIAM Journal on Discrete Mathematics · doi:10.1137/0404033 · Cited by 354
On-line routing of virtual circuits with applications to load balancing and machine scheduling
Aspnes, J., Azar, Y., Fiat, A., Plotkin, S., & Waarts, O. (1997) · Journal of the ACM · doi:10.1145/258128.258201 · Cited by 330
An optimal on-line algorithm for metrical task system
Borodin, A., Linial, N., & Saks, M. E. (1992) · Journal of the ACM · doi:10.1145/146585.146588 · Cited by 326
Competitive randomized algorithms for nonuniform problems
Karlin, A. R., Manasse, M. S., McGeoch, L. A., & Owicki, S. (1994) · Algorithmica · doi:10.1007/bf01189993 · Cited by 258
Thek-server dual and loose competitiveness for paging
Young, N. (1994) · Algorithmica · doi:10.1007/bf01189992 · Cited by 252
The Competitiveness of On-Line Assignments
Azar, Y., Naor, J. S., & Rom, R. (1995) · Journal of Algorithms · doi:10.1006/jagm.1995.1008 · Cited by 241
Koutsoupias, E., & Papadimitriou, C. H. (1995) · Journal of the ACM · doi:10.1145/210118.210128 · Cited by 240
A strongly competitive randomized paging algorithm
McGeoch, L. A., & Sleator, D. D. (1991) · Algorithmica · doi:10.1007/bf01759073 · Cited by 238
Multi-unit auctions with budget-constrained bidders
Borgs, C., Chayes, J., Immorlica, N., Mahdian, M., & Saberi, A. (2005) · ACM Conference on Electronic Commerce (EC) · doi:10.1145/1064009.1064014 · Cited by 218
New Ressults on Server Problems
Chrobak, M., Karloof, H., Payne, T., & Vishwnathan, S. (1991) · SIAM Journal on Discrete Mathematics · doi:10.1137/0404017 · Cited by 208
Randomized Rounding without Solving the Linear Program
Young, N. E. (1995) · Cited by 183
Fairness in Routing and Load Balancing
Kleinberg, J., Rabani, Y., & Tardos, É. (2001) · Journal of Computer and System Sciences · doi:10.1006/jcss.2001.1752 · Cited by 163
Dynamic TCP acknowledgement and other stories about e/(e-1)
Karlin, A. R., Mathieu, C., & Randall, D. (2001) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/380752.380845 · Cited by 155
Competitive k-server algorithms
Fiat, A., Rabani, Y., & Ravid, Y. (1994) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(05)80060-1 · Cited by 135
Improved Approximation Guarantees for Packing and Covering Integer Programs
Srinivasan, A. (1999) · SIAM Journal on Computing · doi:10.1137/s0097539796314240 · Cited by 127
Competitive analysis of randomized paging algorithms
Achlioptas, D., Chrobak, M., & Noga, J. (2000) · Theoretical Computer Science · doi:10.1016/s0304-3975(98)00116-9 · Cited by 127
Online Primal-Dual Algorithms for Covering and Packing Problems
Buchbinder, N., & Naor, J. S. (2005) · Lecture notes in computer science · doi:10.1007/11561071_61 · Cited by 109
Self-citationPage replacement with multi-size pages and applications to Web caching
Irani, S. (1997) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/258533.258666 · Cited by 108
On-line caching as cache size varies
Young, N. E. (1991) · Symposium on Discrete Algorithms · doi:10.5555/127787.127832 · Cited by 101
A Linear Programming Formulation and Approximation Algorithms for the Metric Labeling Problem
Chekuri, C., Khanna, S., Naor, J. S., & Zosin, L. (2004) · SIAM Journal on Discrete Mathematics · doi:10.1137/s0895480101396937 · Cited by 98
Haitner, I., Hoch, J. J., Reingold, O., & Segev, G. (2007) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2007.7 · Cited by 96
Auctions with Budget Constraints
Andelman, N., & Mansour, Y. (2004) · Lecture notes in computer science · doi:10.1007/978-3-540-27810-8_4 · Cited by 92
A polylog( n )-competitive algorithm for metrical task systems
Bartal, Y., Blum, A. L., Burch, C., & Tomkins, A. (1997) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/258533.258667 · Cited by 90
Young, N. E. (1998) · doi:10.5555/314613.314658 · Cited by 88
Improved Bounds for Online Routing and Packing Via a Primal-Dual Approach
Buchbinder, N., & Naor, J. S. (2006) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2006.39 · Cited by 87
Self-citationMeyerson, A. (2005) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2005.72 · Cited by 81
On-line analysis of the TCP acknowledgment delay problem
Dooly, D. R., Goldman, S. A., & Scott, S. (2001) · Journal of the ACM · doi:10.1145/375827.375843 · Cited by 81
Making commitments in the face of uncertainty
Awerbuch, B., Azar, Y., Fiat, A., et al. (1996) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/237814.238000 · Cited by 79
On metric ramsey-type phenomena
Bartal, Y., Linial, N., Mendel, M., & Naor, A. (2003) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/780542.780610 · Cited by 56
Bartal, Y., Bollobás, B., & Mendel, M. (2001) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2001.959914 · Cited by 48
Blum, A. L., Burch, C., & Kalai, A. T. (2003) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sffcs.1999.814617 · Cited by 46
Randomized competitive algorithms for generalized caching
Bansal, N., Buchbinder, N., & Naor, J. S. (2008) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1374376.1374412 · Cited by 41
Self-citationBuchbinder, N., & Naor, J. S. (2006) · ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) · doi:10.1145/1148109.1148159 · Cited by 24
Self-citationRandomized Weighted Caching with Two Page Weights
Irani (2002) · Algorithmica · doi:10.1007/s00453-001-0095-6 · Cited by 21
Randomized k-server algorithms for growth-rate bounded graphs
Bartal, Y., & Mendel, M. (2004) · Journal of Algorithms · doi:10.1016/j.jalgor.2004.06.002 · Cited by 18
A General Decomposition Theorem for the k-Server Problem
Seiden, S. S. (2001) · Lecture notes in computer science · doi:10.1007/3-540-44676-1_7 · Cited by 15
Cited by
Adaptive Submodularity: Theory and Applications in Active Learning and Stochastic Optimization
Golovin, D., & Krause, A. (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1003.3967 · Cited by 461
Metadata
- Authors
- Buchbinder, N., & (Seffi) Naor, J.
- Venue
- now publishers, Inc. eBooks
- Publisher
- now Publishers Inc
- Published
- 2009
- OpenAlex
- W2142339200
- Cited by
- 260
- References
- 57
- FWCI
- 8.30
- Type
- book
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.