The DOI matches its Crossref record; 33 of the 33 references it cites were found in a registry or an index.
Solving Max-Cut to optimality by intersecting semidefinite and polyhedral relaxations
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
Goemans, M. X., & Williamson, D. P. (1995) · Journal of the ACM · doi:10.1145/227683.227684 · Cited by 3,587 · cited 2×
“Apply the Goemans-Williamson hyperplane rounding technique [23] to the primal matrix X obtained from solving the SDP during the bundle iterations.”
BackgroundMethodOR-Library: Distributing Test Problems by Electronic Mail
Beasley, J. E. (1990) · Journal of the Operational Research Society · doi:10.1057/jors.1990.166 · Cited by 1,899
Optimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning
Johnson, D. S., Aragon, C. R., McGeoch, L. A., & Schevon, C. (1989) · Operations Research · doi:10.1287/opre.37.6.865 · Cited by 1,457
Deza, M. M., & Laurent, M. (1997) · Algorithms and combinatorics · doi:10.1007/978-3-642-04295-9 · Cited by 1,014
An Interior-Point Method for Semidefinite Programming
Helmberg, C., Rendl, F., Vanderbei, R. J., & Wolkowicz, H. (1996) · SIAM Journal on Optimization · doi:10.1137/0806020 · Cited by 706
Self-citationAnnotated Bibliographies in Combinatorial Optimization.
Wilson, J. M., Dell’Amico, M., Maffioli, F., & Martello, S. (1998) · Journal of the Operational Research Society · doi:10.2307/3010676 · Cited by 394
Barahona, F., & Mahjoub, A. R. (1986) · Mathematical Programming · doi:10.1007/bf02592023 · Cited by 374
Solving Large-Scale Sparse Semidefinite Programs for Combinatorial Optimization
Benson, S. J., Ye, Y., & Zhang, X. (2000) · SIAM Journal on Optimization · doi:10.1137/s1052623497328008 · Cited by 276
OR-Library: Distributing Test Problems by Electronic Mail
Beasley, J. E. (1990) · Journal of the Operational Research Society · doi:10.1038/sj/jors/0411109 · Cited by 256
.879-approximation algorithms for MAX CUT and MAX 2SAT
Goemans, M. X., & Williamson, D. P. (1994) · Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 · doi:10.1145/195058.195216 · Cited by 234
Solving quadratic (0,1)-problems by semidefinite programs and cutting planes
Helmberg, C., & Rendl, F. (1998) · Mathematical Programming · doi:10.1007/bf01580072 · Cited by 226
Self-citationMethods of Nonlinear 0-1 Programming
Hansen, P. (1979) · Annals of Discrete Mathematics · doi:10.1016/s0167-5060(08)70343-1 · Cited by 220
Rank-Two Relaxation Heuristics for MAX-CUT and Other Binary Quadratic Programs
Burer, S., Monteiro, R. D. C., & Zhang, Y. (2002) · SIAM Journal on Optimization · doi:10.1137/s1052623400382467 · Cited by 214
Adaptive Memory Tabu Search for Binary Quadratic Programs
Glover, F., Kochenberger, G. A., & Alidaee, B. (1998) · Management Science · doi:10.1287/mnsc.44.3.336 · Cited by 209
Heuristic algorithms for the unconstrained binary quadratic programming problem
Beasley, J. E. (1998) · Cited by 189
Using a Mixed Integer Quadratic Programming Solver for the Unconstrained Quadratic 0-1 Problem
Billionnet, A., & Elloumi, S. (2007) · Mathematical Programming · doi:10.1007/s10107-005-0637-9 · Cited by 182
Laplacian eigenvalues and the maximum cut problem
Delorme, C., & Poljak, S. (1993) · Mathematical Programming · doi:10.1007/bf01585184 · Cited by 179
878-approximation Algorithms for MAX CUT and MAX 2SAT
Goemans, M. X. (1994) · Symposium on the Theory of Computing · Cited by 173
Exact ground states of Ising spin glasses: New experimental results with a branch-and-cut algorithm
De Simone, C., Diehl, M., Jünger, M., Mutzel, P., Reinelt, G., & Rinaldi, G. (1995) · Journal of Statistical Physics · doi:10.1007/bf02178370 · Cited by 160
Self-citationSecond order cone programming relaxation of nonconvex quadratic optimization problems
Kim, S., & Kojima, M. (2001) · Optimization methods & software · doi:10.1080/10556780108805819 · Cited by 123
Nonpolyhedral Relaxations of Graph-Bisection Problems
Poljak, S., & Rendl, F. (1995) · SIAM Journal on Optimization · doi:10.1137/0805024 · Cited by 89
Self-citationSolving the max-cut problem using eigenvalues
Poljak, S., & Rendl, F. (1995) · Discrete Applied Mathematics · doi:10.1016/0166-218x(94)00155-7 · Cited by 79
Self-citationComputing Exact Ground States of Hard Ising Spin Glass Problems by Branch‐and‐Cut
Liers, F., Jünger, M., Reinelt, G., & Rinaldi, G. (2004) · doi:10.1002/3527603794.ch4 · Cited by 77
Self-citationFischer, I., Gruber, G., Rendl, F., & Sotirov, R. (2005) · Mathematical Programming · doi:10.1007/s10107-005-0661-9 · Cited by 67
Self-citationBranch-and-Cut Algorithms for Combinatorial Optimization and Their Implementation in ABACUS
Elf, M., Gutwenger, C., Jünger, M., & Rinaldi, G. (2001) · Lecture notes in computer science · doi:10.1007/3-540-45586-8_5 · Cited by 66
Self-citationA Branch and Bound Algorithm for Max-Cut Based on Combining Semidefinite and Polyhedral Relaxations
Rendl, F., Rinaldi, G., & Wiegele, A. (2007) · Springer eBooks · doi:10.1007/978-3-540-72792-7_23 · Cited by 66
Self-citationSemidefinite programming and combinatorial optimization
Rendl, F. (1999) · Applied Numerical Mathematics · doi:10.1016/s0168-9274(98)00097-x · Cited by 53
Self-citationA max-flow approach to improved lower bounds for quadratic unconstrained binary optimization (QUBO)
Boros, E., Hammer, P. L., Sun, R. L., & Tavares, G. (2007) · Discrete Optimization · doi:10.1016/j.disopt.2007.02.001 · Cited by 50
15. A Cutting Plane Algorithm for Large Scale Semidefinite Relaxations
Helmberg, C. (2004) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9780898718805.ch15 · Cited by 41
Fixing Variables in Semidefinite Relaxations
Helmberg, C. (2000) · SIAM Journal on Matrix Analysis and Applications · doi:10.1137/s089547989631442x · Cited by 41
New approaches for optimizing over the semimetric polytope
Frangioni, A., Lodi, A., & Rinaldi, G. (2005) · Mathematical Programming · doi:10.1007/s10107-005-0620-5 · Cited by 29
Self-citationA NEW SECOND-ORDER CONE PROGRAMMING RELAXATION FOR MAX-CUT PROBLEMS
Muramatsu, M., & Suzuki, T. (2003) · Journal of the Operations Research Society of Japan · doi:10.15807/jorsj.46.164 · Cited by 29
Branch and Cut based on the volume algorithm: Steiner trees in graphs and Max-cut
Barahona, F., & Ladányi, L. (2006) · RAIRO - Operations Research · doi:10.1051/ro:2006010 · Cited by 23
Cited by
Zhou, L., Wang, S.-T., Choi, S., Pichler, H., & Lukin, M. D. (2020) · Physical Review X · doi:10.1103/physrevx.10.021067 · Cited by 913
“Hence, we envision that soon, QAOA can be benchmarked against classical [24, 48, 49] and semiclassical [64–66] solvers on large problem sizes with near-term quantum devices.”
BackgroundEvidence for quantum annealing with more than one hundred qubits
Boixo, S., Rønnow, T. F., Isakov, S. V., Wang, Z., Wecker, D., Lidar, D. A., Martinis, J. M., & Troyer, M. (2014) · Nature Physics · doi:10.1038/nphys2900 · Cited by 810
“[39] Rendl, F.”
MethodA fully programmable 100-spin coherent Ising machine with all-to-all connections
McMahon, P. L., Marandi, A., Haribara, Y., Hamerly, R., Langrock, C., Tamate, S., Inagaki, T., Takesue, H., Utsunomiya, S., Aihara, K., et al. (2016) · Science · doi:10.1126/science.aah5178 · Cited by 702
Hamerly, R., Inagaki, T., McMahon, P. L., Venturelli, D., Marandi, A., Onodera, T., Ng, E., Langrock, C., Inaba, K., Honjo, T., et al. (2019) · Science Advances · doi:10.1126/sciadv.aau0823 · Cited by 328
High-performance combinatorial optimization based on classical mechanics
Goto, H., Endo, K., Suzuki, M., Sakai, Y., Kanao, T., Hamakawa, Y., Hidaka, R., Yamasaki, M., & Tatsumura, K. (2021) · Science Advances · doi:10.1126/sciadv.abe7953 · Cited by 231
Metadata
- Authors
- Rendl, F., Rinaldi, G., & Wiegele, A.
- Venue
- Mathematical Programming
- Published
- 2008-07-22
- Volume
- 121
- Issue
- 2
- Pages
- 307-335
- ISSN
- 0025-5610
- 1436-4646
- OpenAlex
- W2033498477
- Cited by
- 264
- References
- 33
- FWCI
- 30.70
- Type
- conference paper
- 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.