TR01-026 Authors: Piotr Berman, Marek Karpinski

Publication: 3rd April 2001 16:24

Downloads: 2587

Keywords:

We consider bounded occurrence (degree) instances of a minimum

constraint satisfaction problem MIN-LIN2 and a MIN-BISECTION problem for

graphs. MIN-LIN2 is an optimization problem for a given system of linear

equations mod 2 to construct a solution that satisfies the minimum number

of them. E3-OCC-MIN-E3-LIN2 is the bounded occurrence (degree) problem

restricted as follows: each equation has exactly 3 variables and each

variable occurs in exactly 3 equations. Clearly, MIN-LIN2 is equivalent to

another well known problem, the Nearest Codeword problem, and

E3-OCC-MIN-E3-LIN2 to its bounded occurrence version. MIN-BISECTION is a

problem of finding a minimum bisection of a graph, while 3-MIN-BISECTION is

the MIN-BISECTION problem restricted to 3-regular 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 E3-OCC-MIN-E3-LIN2 (bounded 3-occurrence 3-ary Nearest

Codeword problem) is equal to MIN-LIN2 (Nearest Codeword problem) lower bound

n^(Omega(1)/log log n). Moreover, an existence of a constant factor

approximation ratio (or a PTAS) for 3-MIN-BISECTION entails existence of a

constant approximation ratio (or a PTAS) for the general MIN-BISECTION.