Relating max-cut problems and binary linear feasibility problems

This paper explores generalizations of the Goemans-Williamson randomization technique. It establishes a simple equivalence of binary linear feasibility problems and max-cut problems and presents an analysis of the semidefinite max-cut relaxation for the case of a single linear equation. Numerical examples for feasible random binary problems indicate that the randomization technique is efficient when the number of linear equations is large.

Citation

Preprint, Mathematisches Institut, Universitaet Duesseldorf Feb. 2009

Article

Download

View Relating max-cut problems and binary linear feasibility problems