Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with MIN-LIN2:
TR01-026 | 3rd April 2001
Piotr Berman, Marek Karpinski

Approximation Hardness of Bounded Degree MIN-CSP and MIN-BISECTION

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 ... more >>>

ISSN 1433-8092 | Imprint