Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming

Goemans, M. X., & Williamson, D. P. (1995). Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming. Journal of the ACM, 42(6).

Type

Journal article

Intellectual base

Primary research

Year

1995

DOI

10.1145/227683.227684

Link

https://doi.org/10.1145/227683.227684

Cited by

1 citation across 1 artifact.

Each citation links to the sentence it supports in the citing article.

Domain-specific

• Randomized Rounding
  • Goemans and Williamson's MAX CUT algorithm, for example, samples a random direction and separates relaxation vectors by the signs of their inner products with that direction.

    This sourceThe primary paper verifies randomized hyperplane rounding of an SDP relaxation and the expected `>0.87856` MAX CUT guarantee.

Verification

This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. See how references were verified.

Links previously used in the corpus

Before the registry existed this work was also linked 1 other way.

• https://math.mit.edu/~goemans/PAPERS/maxcut-jacm.pdf ×1

Registry ID ref:932b2f7510ff · see in the full table