Optimization Online


Relating max-cut problems and binary linear feasibility problems

Florian Jarre (jarre***at***opt.uni-duesseldorf.de)

Abstract: 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.

Keywords: Max-cut problem, semidefinite relaxation, randomized algorithm.

Category 1: Combinatorial Optimization (Approximation Algorithms )

Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Citation: Preprint, Mathematisches Institut, Universitaet Duesseldorf Feb. 2009

Download: [PDF]

Entry Submitted: 02/20/2009
Entry Accepted: 02/20/2009
Entry Last Modified: 03/03/2009

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society