Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Minimum Constraint Satisfaction:
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 >>>

TR01-034 | 30th April 2001
Cristina Bazgan, Wenceslas Fernandez de la Vega, Marek Karpinski

Polynomial Time Approximation Schemes for Dense Instances of Minimum Constraint Satisfaction

It is known that large fragments of the class of dense
Minimum Constraint Satisfaction (MIN-CSP) problems do not have
polynomial time approximation schemes (PTASs) contrary to their
Maximum Constraint Satisfaction analogs. In this paper we prove,
somewhat surprisingly, that the minimum satisfaction of dense
instances of kSAT-formulas, ... more >>>

TR08-101 | 20th November 2008
Marek Karpinski, Warren Schudy

Linear Time Approximation Schemes for the Gale-Berlekamp Game and Related Minimization Problems

We design a linear time approximation scheme for the Gale-Berlekamp Switching Game and generalize it to a wider class of dense fragile minimization problems including the Nearest Codeword Problem (NCP) and Unique Games Problem. Further applications include, among other things, finding a constrained form of matrix rigidity and maximum likelihood ... more >>>

ISSN 1433-8092 | Imprint