The DOI matches its Crossref record; 154 of the 154 references it cites were found in a registry or an index.
The Design of Approximation Algorithms
Abstract
Discrete optimization problems are everywhere, from traditional operations research planning (scheduling, facility location and network design); to computer science databases; to advertising issues in viral marketing. Yet most such problems are NP-hard; unless P = NP, there are no efficient algorithms to find optimal solutions. This book shows how to design approximation algorithms: efficient algorithms that find provably near-optimal solutions. The book is organized around central algorithmic techniques for designing approximation algorithms, including greedy and local search algorithms, dynamic programming, linear and semidefinite programming, and randomization. Each chapter in the first section is devoted to a single algorithmic technique applied to several different problems, with more sophisticated treatment in the second section. The book also covers methods for proving that optimization problems are hard to approximate. Designed as a textbook for graduate-level algorithm courses, it will also serve as a reference for researchers interested in the heuristic solution of discrete optimization problems.
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
(1979) · Cited by 43,841
A note on two problems in connexion with graphs
Dijkstra, E. W. (1959) · Numerische Mathematik · doi:10.1007/bf01386390 · Cited by 29,065
Horn, R. A., & Johnson, C. R. (1985) · Cited by 22,203
Adhi Harmoko, S., M.Komp, Jacquard, J. M., Zuse, K., & Eniac (2005) · Cited by 18,035
Fast approximate energy minimization via graph cuts
Boykov, Y., Veksler, O., & Zabih, R. (2001) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.969114 · Cited by 6,988
Probability Inequalities for sums of Bounded Random Variables
Hoeffding, W. (1994) · Springer Series in Statistics · doi:10.1007/978-1-4612-0865-5_26 · Cited by 6,666
Combinatorial Optimization: Algorithms and Complexity.
Johnson, D. S., Papadimitriou, C. H., & Steiglitz, K. (1984) · The American Mathematical Monthly · doi:10.2307/2322374 · Cited by 5,942
Integer and Combinatorial Optimization
Williams, H. P., Nemhauser, G. L., & Wolsey, L. A. (1990) · Journal of the Operational Research Society · doi:10.2307/2583737 · Cited by 5,485
Motwani, R., & Raghavan, P. (1995) · Cambridge University Press eBooks · doi:10.1017/cbo9780511814075 · Cited by 5,123
An analysis of approximations for maximizing submodular set functions—I
Nemhauser, G. L., Wolsey, L. A., & Fisher, M. L. (1978) · Mathematical Programming · doi:10.1007/bf01588971 · Cited by 4,412
Interior-Point Polynomial Algorithms in Convex Programming
Nesterov, Y., & Nemirovskii, A. (1994) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611970791 · Cited by 4,334
Goemans, M. X., & Williamson, D. P. (1995) · Journal of the ACM · doi:10.1145/227683.227684 · Cited by 3,587 · cited 5×
“The Design of Approximation Algorithms David P. Williamson and David B. Shmoys Frontmatter More information”
BackgroundInfluentialSelf-citationA Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
Chernoff, H. (1952) · The Annals of Mathematical Statistics · doi:10.1214/aoms/1177729330 · Cited by 3,550
Geometric Algorithms and Combinatorial Optimization
Grötschel, M., Lovász, L., & Schrijver, A. (1988) · Algorithms and Combinatorics · doi:10.1007/978-3-642-97881-4 · Cited by 3,431
(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
Introduction to linear optimization
Bertsimas, D., & Tsitsiklis, J. N. (1997) · Cited by 2,705
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
(2003) · Selected Papers of Alan J Hoffman · doi:10.1142/9789812796936_others05 · Cited by 2,465
Bounds on Multiprocessing Timing Anomalies
Graham, R. L. (1969) · SIAM Journal on Applied Mathematics · doi:10.1137/0117039 · Cited by 2,443
Computational Complexity: A Modern Approach
Arora, S., & Barak, B. (2009) · Cited by 2,376
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
Some simplified NP-complete graph problems
Garey, M. R., Johnson, D. S., & Stockmeyer, L. (1976) · Theoretical Computer Science · doi:10.1016/0304-3975(76)90059-1 · Cited by 2,059
The ellipsoid method and its consequences in combinatorial optimization
Grötschel, M., Lovász, L., & Schrijver, A. (1981) · Combinatorica · doi:10.1007/bf02579273 · Cited by 2,011
Some optimal inapproximability results
Håstad, J. (2001) · Journal of the ACM · doi:10.1145/502090.502098 · Cited by 1,902
Various optimizers for single‐stage production
Smith, W. E. (1956) · Naval Research Logistics Quarterly · doi:10.1002/nav.3800030106 · Cited by 1,831
Probability and computing: randomized algorithms and probabilistic analysis
Mitzenmacher, M., & Upfal, E. (2005) · CERN Document Server (European Organization for Nuclear Research) · Cited by 1,824
The Traveling salesman problem: a computational study
(2007) · Choice Reviews Online · doi:10.5860/choice.45-0928 · Cited by 1,726
Clustering to minimize the maximum intercluster distance
Gonzalez, T. F. (1985) · Theoretical Computer Science · doi:10.1016/0304-3975(85)90224-5 · Cited by 1,717
P-Complete Approximation Problems
Sahni, S., & Gonzalez, T. (1976) · Journal of the ACM · doi:10.1145/321958.321975 · Cited by 1,703
The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization
(1986) · Journal of the Operational Research Society · doi:10.1057/jors.1986.93 · Cited by 1,679
Optimization, approximation, and complexity classes
Papadimitriou, C. H., & Yannakakis, M. (1991) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(91)90023-x · Cited by 1,653
Introduction to linear algebra
(2016) · Cybersecurity and Applied Mathematics · doi:10.1016/b978-0-12-804452-0.09998-x · Cited by 1,646
On the Shannon capacity of a graph
Lovasz, L. (1979) · IEEE Transactions on Information Theory · doi:10.1109/tit.1979.1055985 · Cited by 1,624
Proof verification and the hardness of approximation problems
Arora, S., Lund, C., Motwani, R., Sudan, M., & Szegedy, M. (1998) · Journal of the ACM · doi:10.1145/278298.278306 · Cited by 1,413
Kleinberg, J. M., & Eva Tardos, D. (2005) · Cited by 1,400
Clique is hard to approximate within n1−ε
Håstad, J. (1999) · Acta Mathematica · doi:10.1007/bf02392825 · Cited by 1,369
A First Course in Probability.
Sherman, M. J., & Ross, S. (1984) · Journal of the American Statistical Association · doi:10.2307/2288753 · Cited by 1,344
(2000) · Computers & Mathematics with Applications · doi:10.1016/s0898-1221(00)90183-4 · Cited by 1,263
Probabilistic checking of proofs: a new characterization of NP
Arora, S., & Safra, S. (1998) · Journal of the ACM · doi:10.1145/273865.273901 · Cited by 1,153
Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
Arora, S. (1998) · Journal of the ACM · doi:10.1145/290179.290180 · Cited by 1,137
Worst-Case Analysis of a New Heuristic for the Travelling Salesman Problem
Christofides, N. (2022) · Operations Research Forum · doi:10.1007/s43069-021-00101-z · Cited by 1,131
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
On the Complexity of Timetable and Multicommodity Flow Problems
Even, S., Itai, A., & Shamir, A. (1976) · SIAM Journal on Computing · doi:10.1137/0205048 · Cited by 1,057
Deza, M. M., & Laurent, M. (1997) · Algorithms and combinatorics · doi:10.1007/978-3-642-04295-9 · Cited by 1,014
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
Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
Ibarra, O. H., & Kim, C. E. (1975) · Journal of the ACM · doi:10.1145/321906.321909 · Cited by 959
The geometry of graphs and some of its algorithmic applications
Linial, N., London, E., & Rabinovich, Y. (1995) · Combinatorica · doi:10.1007/bf01200757 · Cited by 952
Approximation algorithms for NP-complete problems on planar graphs
Baker, B. S. (1994) · Journal of the ACM · doi:10.1145/174644.174650 · Cited by 947
A Best Possible Heuristic for the k-Center Problem
Hochbaum, D. S., & Shmoys, D. B. (1985) · Mathematics of Operations Research · doi:10.1287/moor.10.2.180 · Cited by 921
Self-citationInterior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
Alizadeh, F. (1995) · SIAM Journal on Optimization · doi:10.1137/0805002 · Cited by 892
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
Self-citationOn the hardness of approximating minimization problems
Lund, C., & Yannakakis, M. (1994) · Journal of the ACM · doi:10.1145/185675.306789 · Cited by 872
Matroids and the greedy algorithm
Edmonds, J. (1971) · Mathematical Programming · doi:10.1007/bf01584082 · Cited by 866
Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
Leighton, T., & Rao, S. (1999) · Journal of the ACM · doi:10.1145/331524.331526 · Cited by 820
On the power of unique 2-prover 1-round games
Khot, S. (2002) · Proceedings of the thiry-fourth annual ACM symposium on Theory of computing · doi:10.1145/509907.510017 · Cited by 818
Vertex cover might be hard to approximate to within 2−ε
Khot, S., & Regev, O. (2007) · Journal of Computer and System Sciences · doi:10.1016/j.jcss.2007.06.019 · Cited by 795
Using dual approximation algorithms for scheduling problems theoretical and practical results
Hochbaum, D. S., & Shmoys, D. B. (1987) · Journal of the ACM · doi:10.1145/7531.7535 · Cited by 790
Self-citationAn analysis of several heuristics for the traveling salesman problem
Rosenkrantz, D. J., Stearns, R. E., & Lewis, P. M. (2009) · Fundamental Problems in Computing · doi:10.1007/978-1-4020-9688-4_3 · Cited by 772
Rényi, A. (2007) · Cited by 727
An approximation algorithm for the generalized assignment problem
Shmoys, D. B., & Tardos, É. (1993) · Mathematical Programming · doi:10.1007/bf01585178 · Cited by 726
Self-citationRaz, R. (1998) · SIAM Journal on Computing · doi:10.1137/s0097539795280895 · Cited by 703
Gilbert, E. N., & Pollak, H. O. (1968) · SIAM Journal on Applied Mathematics · doi:10.1137/0116001 · Cited by 690
The Brunn-Minkowski inequality in Gauss space
Borell, C. (1975) · Inventiones mathematicae · doi:10.1007/bf01425510 · Cited by 682
Vertex packings: Structural properties and algorithms
Nemhauser, G. L., & Trotter, L. E. (1975) · Mathematical Programming · doi:10.1007/bf01580444 · Cited by 664
The Complexity of Multiterminal Cuts
Dahlhaus, E., Johnson, D. S., Papadimitriou, C. H., Seymour, P. D., & Yannakakis, M. (1994) · SIAM Journal on Computing · doi:10.1137/s0097539792225297 · Cited by 662
On the Abstract Properties of Linear Dependence1
Whitney, H. (2009) · Classic Papers in Combinatorics · doi:10.1007/978-0-8176-4842-8_5 · Cited by 653
Probabilistic approximation of metric spaces and its algorithmic applications
Bartal, Y. (2002) · Proceedings of 37th Conference on Foundations of Computer Science · doi:10.1109/sfcs.1996.548477 · Cited by 635
Algorithms for Scheduling Independent Tasks
Sahni, S. K. (1976) · Journal of the ACM · doi:10.1145/321921.321934 · Cited by 597
Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
Khot, S., Kindler, G., Mossel, E., & O’Donnell, R. (2007) · SIAM Journal on Computing · doi:10.1137/s0097539705447372 · Cited by 578
Linear time algorithms for NP-hard problems restricted to partial k-trees
Arnborg, S., & Proskurowski, A. (1989) · Discrete Applied Mathematics · doi:10.1016/0166-218x(89)90031-0 · Cited by 577
Near-optimal bin packing algorithms
Johnson, D. S. (1973) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 573
Handbook of semidefinite programming : theory, algorithms, and applications
Wolkowicz, H., Saigal, R., & Vandenberghe, L. (2000) · Cited by 568
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
On lipschitz embedding of finite metric spaces in Hilbert space
Bourgain, J. (1985) · Israel Journal of Mathematics · doi:10.1007/bf02776078 · Cited by 560
Approximation Schemes for the Restricted Shortest Path Problem
Hassin, R. (1992) · Mathematics of Operations Research · doi:10.1287/moor.17.1.36 · Cited by 557
Interactive proofs and the hardness of approximating cliques
Feige, U., Goldwasser, S., Lovász, L., Safra, M., & Szegedy, M. (1996) · Journal of the ACM · doi:10.1145/226643.226652 · Cited by 525
Greedy strikes back: Improved Facility Location Algorithms
Guha, S., & Khuller, S. (1998) · Cited by 515
Bin packing can be solved within 1 + ε in linear time
de la Véga, W. F., & Lueker, G. S. (1981) · COMBINATORICA · doi:10.1007/bf02579456 · Cited by 510
Approximation Algorithms for the Set Covering and Vertex Cover Problems
Hochbaum, D. S. (1982) · SIAM Journal on Computing · doi:10.1137/0211045 · Cited by 506
The PCP theorem by gap amplification
Dinur, I. (2006) · Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing · doi:10.1145/1132516.1132553 · Cited by 501
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
Free Bits, PCPs, and Nonapproximability---Towards Tight Results
Bellare, M., Goldreich, O., & Sudan, M. (1998) · SIAM Journal on Computing · doi:10.1137/s0097539796302531 · Cited by 453
Ten Lectures on the Probabilistic Method: Second Edition
Spencer, J. (1994) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9781611970074 · Cited by 440
Cornuéjols, G., Fisher, M. L., & Nemhauser, G. L. (1979) · Management Science · doi:10.1287/mnsc.25.8.808 · Cited by 432
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
Approximate graph coloring by semidefinite programming
Karger, D., Motwani, R., & Sudan, M. (1998) · Journal of the ACM · doi:10.1145/274787.274791 · Cited by 420
Expander flows, geometric embeddings and graph partitioning
Arora, S., Rao, S., & Vazirani, U. (2009) · Journal of the ACM · doi:10.1145/1502793.1502794 · Cited by 418
Fast Approximation Algorithms for Knapsack Problems
Lawler, E. L. (1979) · Mathematics of Operations Research · doi:10.1287/moor.4.4.339 · Cited by 411
A Local-Ratio Theorem for Approximating the Weighted Vertex Cover Problem
Bar-Yehuda, R., & Even, S. (1985) · North-Holland Mathematics Studies · doi:10.1016/s0304-0208(08)73101-3 · Cited by 404
Kleinberg, J., & Tardos, É. (2002) · Journal of the ACM · doi:10.1145/585265.585268 · Cited by 400
Leighton, T., & Rao, S. (1988) · [Proceedings 1988] 29th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1988.21958 · Cited by 395
Korte, B., & Vygen, J. (2000) · Algorithms and Combinatorics · doi:10.1007/978-3-662-21708-5 · Cited by 393
Optimal algorithms and inapproximability results for every CSP?
Raghavendra, P. (2008) · Proceedings of the fortieth annual ACM symposium on Theory of computing · doi:10.1145/1374376.1374414 · Cited by 384
Primal-dual approximation algorithms for integral flow and multicut in trees
Garg, N., Vazirani, V. V., & Yannakakis, M. (1997) · Algorithmica · doi:10.1007/bf02523685 · Cited by 378
Semidefinite relaxation and nonconvex quadratic optimization
Nesterov, Y. (1998) · Optimization Methods and Software · doi:10.1080/10556789808805690 · Cited by 375
The primal-dual method for approximation algorithms and its application to network design problems
Goemans, M. X., & Williamson, D. P. (1996) · PWS Publishing Co. eBooks · Cited by 365
Self-citationPipage Rounding: A New Method of Constructing Algorithms with Proven Performance Guarantee
Ageev, A. A., & Sviridenko, M. I. (2004) · Journal of Combinatorial Optimization · doi:10.1023/b:joco.0000038913.96607.c2 · Cited by 363
The Hardness of Approximate Optima in Lattices, Codes, and Systems of Linear Equations
Arora, S., Babai, L., Stern, J., & Sweedyk, Z. (1997) · Journal of Computer and System Sciences · doi:10.1006/jcss.1997.1472 · Cited by 344
Approximation schemes for Euclidean k-medians and related problems
Arora, S., Raghavan, P., & Rao, S. (1998) · Proceedings of the thirtieth annual ACM symposium on Theory of computing - STOC '98 · doi:10.1145/276698.276718 · Cited by 341
A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
Bafna, V., Berman, P., & Fujito, T. (1999) · SIAM Journal on Discrete Mathematics · doi:10.1137/s0895480196305124 · Cited by 340
Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications
Garg, N., Vazirani, V. V., & Yannakakis, M. (1996) · SIAM Journal on Computing · doi:10.1137/s0097539793243016 · Cited by 335
The Ellipsoid Method: A Survey
Bland, R. G., Goldfarb, D., & Todd, M. J. (1980) · eCommons (Cornell University) · Cited by 334
Tighter Bounds for Graph Steiner Tree Approximation
Robins, G., & Zelikovsky, A. (2005) · SIAM Journal on Discrete Mathematics · doi:10.1137/s0895480101393155 · Cited by 327
Efficient probabilistically checkable proofs and applications to approximations
Bellare, M., Goldwasser, S., Lund, C., et al. (1993) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/167088.167174 · Cited by 317
A Graph-Theoretic Game and Its Application to the k -Server Problem
Alon, N., Karp, R. M., Peleg, D., & West, D. B. (1995) · SIAM Journal on Computing · doi:10.1137/s0097539792224474 · Cited by 303
An improved LP-based approximation for steiner tree
Byrka, J., Grandoni, F., Rothvoß, T., & Sanità, L. (2010) · Proceedings of the forty-second ACM symposium on Theory of computing · doi:10.1145/1806689.1806769 · Cited by 296
Noise stability of functions with low influences: Invariance and optimality
Mossel, E., O’Donnell, R., & Oleszkiewicz, K. (2010) · Annals of Mathematics · doi:10.4007/annals.2010.171.295 · Cited by 288
A note on the prize collecting traveling salesman problem
Bienstock, D., Goemans, M. X., Simchi-Levi, D., & Williamson, D. (1993) · Mathematical Programming · doi:10.1007/bf01581256 · Cited by 280
Self-citationThe traveling salesman problem on a graph and some related integer polyhedra
Cornuéjols, G., Fonlupt, J., & Naddef, D. (1985) · Mathematical Programming · doi:10.1007/bf01582008 · Cited by 280
An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm
Aumann, Y., & Rabani, Y. (1998) · SIAM Journal on Computing · doi:10.1137/s0097539794285983 · Cited by 260
Global min-cuts in RNC, and other ramifications of a simple min-cut algorithm
Karger, D. R. (1993) · doi:10.5555/313559.313605 · Cited by 238
New $\frac{3}{4}$-Approximation Algorithms for the Maximum Satisfiability Problem
Goemans, M. X., & Williamson, D. P. (1994) · SIAM Journal on Discrete Mathematics · doi:10.1137/s0895480192243516 · Cited by 227
Self-citationEasy and hard bottleneck location problems
Hsu, W.-L., & Nemhauser, G. L. (1979) · Discrete Applied Mathematics · doi:10.1016/0166-218x(79)90044-1 · Cited by 215
Maximizing Quadratic Programs: Extending Grothendieck's Inequality
Charikar, M., & Wirth, A. (2004) · 45th Annual IEEE Symposium on Foundations of Computer Science · doi:10.1109/focs.2004.39 · Cited by 214
The importance of being biased
Dinur, I., & Safra, S. (2002) · Proceedings of the thiry-fourth annual ACM symposium on Theory of computing · doi:10.1145/509907.509915 · Cited by 212
Scheduling Parallel Machines On-Line
Shmoys, D. B., Wein, J., & Williamson, D. P. (1995) · SIAM Journal on Computing · doi:10.1137/s0097539793248317 · Cited by 207
Self-citationOn the Approximation of Maximum Satisfiability
Yannakakis, M. (1994) · Journal of Algorithms · doi:10.1006/jagm.1994.1045 · Cited by 200
Polynomial Time Approximation Schemes for Dense Instances of NP-Hard Problems
Arora, S., Karger, D., & Karpinski, M. (1999) · Journal of Computer and System Sciences · doi:10.1006/jcss.1998.1605 · Cited by 199
Finding k Cuts within Twice the Optimal
Saran, H., & Vazirani, V. V. (1995) · SIAM Journal on Computing · doi:10.1137/s0097539792251730 · Cited by 195
Iterative Methods in Combinatorial Optimization
Lau, L. C., Ravi, R., & Singh, M. (2011) · Cambridge University Press eBooks · doi:10.1017/cbo9780511977152 · Cited by 194
On maximization of quadratic form over intersection of ellipsoids with common center
Nemirovski, A., Roos, C., & Terlaky, T. (1999) · Mathematical Programming · doi:10.1007/s101070050100 · Cited by 168
Optimal assignments in an ordered set: An application of matroid theory
Gale, D. (1968) · Journal of Combinatorial Theory · doi:10.1016/s0021-9800(68)80039-0 · Cited by 158
Correlation Clustering: maximizing agreements via semidefinite programming
Swamy, C. (2004) · doi:10.5555/982792.982866 · Cited by 140
Approximation schemes for NP-hard geometric optimization problems: a survey
Arora, S. (2003) · Mathematical Programming · doi:10.1007/s10107-003-0438-y · Cited by 133
A linear time approximation algorithm for multiprocessor scheduling
Finn, G., & Horowitz, E. (1979) · BIT Numerical Mathematics · doi:10.1007/bf01930985 · Cited by 128
On the optimality of the random hyperplane rounding technique for MAX CUT
Feige, U., & Schechtman, G. (2002) · Random Structures and Algorithms · doi:10.1002/rsa.10036 · Cited by 127
Prömel, H. J., & Steger, A. (2002) · Advanced lectures in mathematics · doi:10.1007/978-3-322-80291-0 · Cited by 124
Near-optimal algorithms for unique games
Charikar, M., Makarychev, K., & Makarychev, Y. (2006) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1132516.1132547 · Cited by 124
Approximation schemes for scheduling
Alon, N., Azar, Y., Woeginger, G. J., et al. (1997) · doi:10.5555/314161.314371 · Cited by 104
Derandomizing Approximation Algorithms Based on Semidefinite Programming
Mahajan, S., & Ramesh, H. (1999) · SIAM Journal on Computing · doi:10.1137/s0097539796309326 · Cited by 99
One for the Price of Two: a Unified Approach for Approximating Covering Problems
Bar-Yehuda, R. (2000) · Algorithmica · doi:10.1007/s004530010009 · Cited by 92
Approximation via cost sharing
Gupta, A., Kumar, A., ́al, M. P., et al. (2007) · Journal of the ACM · doi:10.1145/1236457.1236458 · Cited by 84
MAX-CUT has a randomized approximation scheme in dense graphs
de la Véga, W. F. (1996) · Random Structures and Algorithms · doi:10.1002/(sici)1098-2418(199605)8:3<187::aid-rsa3>3.0.co;2-u · Cited by 78
New approximation guarantee for chromatic number
Arora, S., & Chlamtáč, E. (2006) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/1132516.1132548 · Cited by 75
On the Hardness of 4-Coloring a 3-Colorable Graph
Guruswami, V., & Khanna, S. (2004) · SIAM Journal on Discrete Mathematics · doi:10.1137/s0895480100376794 · Cited by 70
Parallel Approximation Algorithms by Positive Linear Programming
Trevisan, L. (1998) · Algorithmica · doi:10.1007/pl00009209 · Cited by 70
Complexity of Partial Satisfaction
Lieberherr, K. J., & Specker, E. P. (1981) · Journal of the ACM · doi:10.1145/322248.322260 · Cited by 70
An Efficient Approximation Algorithm for Minimizing Makespan on Uniformly Related Machines
Chekuri, C., & Bender, M. A. (2001) · Journal of Algorithms · doi:10.1006/jagm.2001.1184 · Cited by 60
How to Play Unique Games Using Embeddings
Chlamtáč, E., Makarychev, K., & Makarychev, Y. (2006) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2006.36 · Cited by 59
Raghavendra, P., & Steurer, D. (2009) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2009.74 · Cited by 59
On the Equivalence between the Primal-Dual Schema and the Local Ratio Technique
Bar-Yehuda, R., & Rawitz, D. (2005) · SIAM Journal on Discrete Mathematics · doi:10.1137/050625382 · Cited by 54
Minimum cuts, modular functions, and matroid polyhedra
Cunningham, W. H. (1985) · Networks · doi:10.1002/net.3230150206 · Cited by 52
Gupta, A., & Talwar, K. (2006) · doi:10.5555/1109557.1109569 · Cited by 48
Complexity of approximation algorithms for combinatorial problems: a survey
Gens, G. V., & Levner, E. V. (1980) · ACM SIGACT News · doi:10.1145/1008861.1008867 · Cited by 48
On Dinur’s proof of the PCP theorem
Radhakrishnan, J., & Sudan, M. (2006) · Bulletin of the American Mathematical Society · doi:10.1090/s0273-0979-06-01143-8 · Cited by 47
Bertsimas, D., & Teo, C. (1998) · Operations Research · doi:10.1287/opre.46.4.503 · Cited by 41
Relaxations of Quadratic Programs in Operator Theory and System Analysis
Megretski, A. (2001) · Birkhäuser Basel eBooks · doi:10.1007/978-3-0348-8362-7_15 · Cited by 39
Geometry, flows, and graph-partitioning algorithms
Arora, S., Rao, S. B., & Vazirani, U. V. (2008) · Communications of the ACM · doi:10.1145/1400181.1400204 · Cited by 39
Positive linear programming, parallel approximation and PCP's
Trevisan, L. (1996) · Lecture notes in computer science · doi:10.1007/3-540-61680-2_47 · Cited by 29
Chekuri, C., Guha, S., & Naor, J. S. (2006) · SIAM Journal on Discrete Mathematics · doi:10.1137/s0895480104445095 · Cited by 25
New primal and dual matching heuristics
J�nger, M., & Pulleyblank, W. R. (1995) · Algorithmica · doi:10.1007/bf01293485 · Cited by 20
Approximating Node-Deletion Problems for Matroidal Properties
Fujito, T. (1999) · Journal of Algorithms · doi:10.1006/jagm.1998.0995 · Cited by 15
Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes)Preprint
Harsha, P., Charikar, M., Andrews, M., Arora, S., Khot, S., Moshkovitz, D., Zhang, L., Aazami, A., Desai, D., Gorodezky, I., et al. (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1002.3864 · Cited by 4
Cited by
Near optimal placement of virtual network functions
Cohen, R., Lewin-Eytan, L., Naor, J. S., & Raz, D. (2015) · 2015 IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infocom.2015.7218511 · Cited by 519
Spatial crowdsourcing: a survey
Tong, Y., Zhou, Z., Zeng, Y., Chen, L., & Shahabi, C. (2020) · The VLDB Journal · doi:10.1007/s00778-019-00568-7 · Cited by 305
Assortment Optimization Under Variants of the Nested Logit Model
Davis, J. M., Gallego, G., & Topaloglu, H. (2014) · Operations Research · doi:10.1287/opre.2014.1256 · Cited by 295
Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search
Li, Z., Chen, Q., & Koltun, V. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1810.10659 · Cited by 287
A survey on influence maximization in a social network
Banerjee, S., Jenamani, M., & Pratihar, D. K. (2020) · Knowledge and Information Systems · doi:10.1007/s10115-020-01461-4 · Cited by 262
Metadata
- Authors
- Williamson, D. P., & Shmoys, D. B.
- Venue
- Cambridge University Press eBooks
- Publisher
- Cambridge University Press
- Published
- 2011-04-26
- OpenAlex
- W1899379166
- Cited by
- 1,301
- References
- 154
- FWCI
- 16.51
- 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.