
Universität Bonn > Institut für Informatik > Abteilung V  
CSAPXReports 2001  Copyright 2001 Universität Bonn, Institut für Informatik, Abt. V  
8967 April 3, 2001 
Approximation Hardness of Bounded Degree MINCSP and MINBISECTION
Piotr Berman and Marek Karpinski [Download PostScript] [Download PDF] We consider bounded occurrence (degree) instances of a minimum constraint satisfaction problem MINLIN2 and a MINBISECTION problem for graphs. MINLIN2 is an optimization problem for a given system of linear equations mod 2 to construct a solution that satisfies the minimum number of them. E3OCCMINE3LIN2 is the bounded occurrence (degree) problem restricted as follows: each equation has exactly 3 variables and each variable occurs in exactly 3 equations. Clearly, MINLIN2 is equivalent to another well known problem, the Nearest Codeword problem, and E3OCCMINE3LIN2 to its bounded occurrence version. MINBISECTION is a problem of finding a minimum bisection of a graph, while 3MINBISECTION is the MINBISECTION problem restricted to 3regular graphs only. We show that, somewhat surprisingly, these two restricted problems are exactly as hard to approximate as their general versions. In particular, an approximation ratio lower bound for E3OCCMINE3LIN2 (bounded 3occurrence 3ary Nearest Codeword problem) is equal to MINLIN2 (Nearest Codeword problem) lower bound n^ (Omega(1) / log log n). Moreover, an existence of a constant factor approximation ratio (or a PTAS) for 3MINBISECTION entails existence of a constant approximation ratio (or a PTAS) for the general MINBISECTION. 

Last Change:
11/05/14 at 10:22:22
English 
Universität Bonn > Institut für Informatik > Abteilung V 