Polynomial time approximation schemes for dense instances of minimum constraint satisfaction
Open Access
- 18 June 2003
- journal article
- research article
- Published by Wiley in Random Structures & Algorithms
- Vol. 23 (1) , 73-91
Abstract
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 ofkSAT‐formulas, and linear equations mod 2, Ek‐LIN2, do have PTASs for anyk.The MIN‐Ek‐LIN2 problems are equivalent to thek‐ary versions of the Nearest Codeword problem, the problem which is known to be exceedingly hard to approximate on general instances. The method of solution of the above problems depends on the development of a new density sampling technique fork‐uniform hypergraphs which could be of independent interest. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 23: 73–91, 2003Keywords
This publication has 20 references indexed in Scilit:
- Polynomial time approximation of dense weighted instances of MAX-CUTRandom Structures & Algorithms, 2000
- On the approximation hardness of dense TSP and other path problemsInformation Processing Letters, 1999
- Polynomial Time Approximation Schemes for Dense Instances of NP-Hard ProblemsJournal of Computer and System Sciences, 1999
- Property testing and its connection to learning and approximationJournal of the ACM, 1998
- Approximating dense cases of covering problems1998
- MAX-CUT has a randomized approximation scheme in dense graphsRandom Structures & Algorithms, 1996
- Approximate Max-Flow Min-(Multi)Cut Theorems and Their ApplicationsSIAM Journal on Computing, 1996
- On dependent randomized rounding algorithmsLecture Notes in Computer Science, 1996
- The Minimum Satisfiability ProblemSIAM Journal on Discrete Mathematics, 1994
- Probability Inequalities for Sums of Bounded Random VariablesJournal of the American Statistical Association, 1963