Concepedia

Maximum Cut Approximation

Maximum Cut Approximation is an algorithmic method in combinatorial optimization that achieves a performance guarantee for the Maximum Cut problem by computing a solution whose cut size approximates the optimal cut within a proven factor.

216

Publications

19.9K

Citations

422

Authors

242

Institutions

Publications per year

2017–2026

30

Parents

Publications

216

Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming

Michel X. Goemans, David P. Williamson · Journal of the ACM · 1995 · 3.7K citations · Full text

, , +14

Approximation algorithms for combinatorial problems

David S. Johnson · Journal of Computer and System Sciences · 1974 · 2.2K citations

, , +12

Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms

Tom Leighton, Satish Rao · Journal of the ACM · 1999 · 832 citations · Full text

, , +15

Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?

Subhash Khot, Guy Kindler, Elchanan Mossel et al. · SIAM Journal on Computing · 2007 · 599 citations · Full text

, , +13

An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design

Francisco Barahona, Martin Grötschel, Michael Jünger et al. · Operations Research · 1988 · 509 citations

, , +17

1–5 of 216

Authors

422

  1. DR
    David R. Karger

    Massachusetts Institute of Technology, United States

    7 publications · 1.2K citations

    7

    h-index

  2. DP
    David P. Williamson

    Cornell University, United States

    6 publications · 4.4K citations

    6

    h-index

  3. LT
    Luca Trevisan

    University of California, Berkeley, United States

    6 publications · 504 citations

    6

    h-index

  4. SK
    Subhash Khot

    Georgia Institute of Technology, United States

    5 publications · 867 citations

    5

    h-index

  5. MS
    Madhu Sudan

    Massachusetts Institute of Technology, United States

    5 publications · 775 citations

    5

    h-index

1–5 of 422

Institutions

242

  1. Massachusetts Institute of Technology

    Cambridge, United States

    13 h-index

    17 publications

    8.9K citations

  2. Carnegie Mellon University

    Pittsburgh, United States

    11 h-index

    13 publications

    1.6K citations

  3. University of California, Berkeley

    Berkeley, United States

    9 h-index

    11 publications

    1.3K citations

  4. Centre National de la Recherche Scientifique

    Paris, France

    8 h-index

    12 publications

    376 citations

  5. Georgia Institute of Technology

    Atlanta, United States

    7 h-index

    9 publications

    540 citations

  6. Princeton University

    Princeton, United States

    7 h-index

    11 publications

    1.9K citations

  7. IBM Research - Thomas J. Watson Research Center

    Yorktown Heights, United States

    7 h-index

    12 publications

    4.3K citations

  8. Tel Aviv University

    Tel Aviv, Israel

    7 h-index

    12 publications

    789 citations

1–8 of 242

Venues

  1. Mathematical Programming

    12 publications · 529 citations

    12

    h-index

  2. Operations Research Letters

    9 publications · 465 citations

    9

    h-index

  3. SIAM Journal on Computing

    9 publications · 2.1K citations

    9

    h-index

  4. arXiv (Cornell University)

    Repository · 6 publications · 93 citations

    6

    h-index

  5. Journal of the ACM

    JACM · 5 publications · 5.1K citations

    5

    h-index

1–5