The DOI matches its Crossref record; 10 of the 10 references it cites were found in a registry or an index.
Fast Approximation Algorithms for Fractional Packing and Covering Problems
Abstract
This paper presents fast algorithms that find approximate solutions for a general class of problems, which we call fractional packing and covering problems. The only previously known algorithms for solving these problems are based on general linear programming techniques. The techniques developed in this paper greatly outperform the general methods in many applications, and are extensions of a method previously applied to find approximate solutions to multicommodity flow problems. Our algorithm is a Lagrangian relaxation technique; an important aspect of our results is that we obtain a theoretical analysis of the running time of a Lagrangian relaxation-based algorithm. We give several applications of our algorithms. The new approach yields several orders of magnitude of improvement over the best previously known running times for algorithms for the scheduling of unrelated parallel machines in both the preemptive and the nonpreemptive models, for the job shop problem, for the Held and Karp bound for the traveling salesman problem, for the cutting-stock problem, for the network embedding problem, and for the minimum-cost multicommodity flow problem.
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
Fibonacci heaps and their uses in improved network optimization algorithms
Fredman, M. L., & Tarjan, R. E. (1987) · Journal of the ACM · doi:10.1145/28869.28874 · Cited by 3,132
A Linear Programming Approach to the Cutting-Stock Problem
Gilmore, P. C., & Gomory, R. E. (1961) · Operations Research · doi:10.1287/opre.9.6.849 · Cited by 2,024
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
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
An efficient approximation scheme for the one-dimensional bin-packing problem
Karmarkar, N. K., & Karp, R. M. (1982) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1982.61 · Cited by 491
Fast Approximation Algorithms for Knapsack Problems
Lawler, E. L. (1979) · Mathematics of Operations Research · doi:10.1287/moor.4.4.339 · Cited by 411
Leighton, T., & Rao, S. (1988) · [Proceedings 1988] 29th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1988.21958 · Cited by 395
Speeding-up linear programming using fast matrix multiplication
Vaidya, P. M. (1989) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1989.63499 · Cited by 315
Fast approximation algorithms for multicommodity flow problems
Leighton, T., Stein, C., Makedon, F. S., Eva Tardos, D., Plotkin, S. A., & Tragoudas, S. (1991) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/103418.103425 · Cited by 201
Self-citationA new algorithm for minimizing convex functions over convex sets
Vaidya, P. M. (1989) · 30th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1989.63500 · Cited by 172
Cited by
Introduction to Online Convex Optimization
Hazan, E. (2016) · now publishers, Inc. eBooks · doi:10.1561/9781680831719 · Cited by 813
Introduction to Online Convex Optimization
Hazan, E. (2016) · Foundations and Trends in Optimization · doi:10.1561/2400000013 · Cited by 747
Adaptive Game Playing Using Multiplicative Weights
Freund, Y., & Schapire, R. E. (1999) · Games and Economic Behavior · doi:10.1006/game.1999.0738 · Cited by 515
A Spectral Bundle Method for Semidefinite Programming
Helmberg, C., & Rendl, F. (2000) · SIAM Journal on Optimization · doi:10.1137/s1052623497328987 · Cited by 436
On the Complexity of Solving Markov Decision Problems
Littman, M. L., Dean, T., & Kaelbling, L. P. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1302.4971 · Cited by 424
Game theory, on-line prediction and boosting
Freund, Y., & Schapire, R. E. (1996) · Proceedings of the ninth annual conference on Computational learning theory - COLT '96 · doi:10.1145/238061.238163 · Cited by 383
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
Self-citationExpander flows, geometric embeddings and graph partitioning
Arora, S., Rao, S., & Vazirani, U. (2004) · Proceedings of the thirty-sixth annual ACM symposium on Theory of computing · doi:10.1145/1007352.1007355 · Cited by 297
Potential Function Methods for Approximately Solving Linear Programming Problems
(2002) · International Series in Operations Research & Management Science · doi:10.1007/b115460 · Cited by 291
The Design of Competitive Online Algorithms via a Primal—Dual Approach
Buchbinder, N., & (Seffi) Naor, J. (2009) · now publishers, Inc. eBooks · doi:10.1561/9781601982179 · Cited by 260
Tight Approximation Algorithms for Maximum Separable Assignment Problems
Fleischer, L., Goemans, M. X., Mirrokni, V. S., & Sviridenko, M. (2011) · Mathematics of Operations Research · doi:10.1287/moor.1110.0499 · Cited by 65
Metadata
- Authors
- Plotkin, S. A., Shmoys, D. B., & Tardos, É.
- Venue
- Mathematics of Operations Research
- Published
- 1995-05
- Volume
- 20
- Issue
- 2
- Pages
- 257-301
- ISSN
- 0364-765X (ISSN-L)
- 1526-5471
- OpenAlex
- W2134422938
- Cited by
- 542
- References
- 10
- FWCI
- 17.85
- Type
- journal article
- 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.