Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-APX-Reports 2006 Copyright 2006 University of Bonn, Department of Computer Science, Abt. V
89106

26.09.2006

Approximation of Global MAX-CSP Problems
W. Fernandez de la Vega, Ravi Kannan and Marek Karpinski
[Download PostScript] [Download PDF]

We study the problem of absolute approximability of MAX-CSP problems withthe global constraints. We prove existence of an efficient sampling methodfor the MAX-CSP class of problems with linear global constraints and boundedfeasibility gap. It gives for the first time a polynomial inε-1sample complexity bound for that class of problems. The method yields also thebest up to date sample complexity bound for the balanced MAX-CSP problemssuch as the graph and hypergraph BISECTION problems.

Last Change: 11/05/14 at 10:35:27
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V