Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Label Cover Reductions for Unconditional Approximation Hardness of Constraint Satisfaction
Stockholm University, Faculty of Science, Numerical Analysis and Computer Science (NADA).
2014 (English)Doctoral thesis, comprehensive summary (Other academic)Alternative title
Etikettäckningsreduktioner för Obetingad Approximationssvårighet av Vilkorssatisfiering (Swedish)
Abstract [en]

Problem solving is an integral aspect of modern society and includes such tasks as picking the fastest route to work, optimizing a production line, scheduling computer tasks, placing new bus stops, or picking a meal from available ingredients.We study the hardness of solving Constraint Satisfaction Problems (CSPs). In these, one is given a collection of constraints on variables with the task of finding an assignment satisfying the greatest number of constraints. In particular, parity constraints dictate that an odd (alt. even) number of variables are assigned a certain value.Satisfiable collections of parity constraints are easy in the sense that they can be efficiently solved via Gaussian elimination. We prove the threshold phenomenon that when constraints accept even one more assignment besides parities, then it is hard to find approximate solutions which are essentially better than random assignments.We also investigate the uselessness of predicates. Uselessness is a stronger hardness property in the sense that even if one was permitted to choose the acceptance criteria for given constraints, it is NP-hard to find solutions beating random assignments. We provide the first examples of predicates which are useless even when all variables appear unnegated.Finally, in an Ordering CSP (OCSP), one receives a set of items to order and constraints specifying how the items should be ordered relative to one another. For example, in the problem Maximum Betweenness, we have constraints of the form "order x between y and z". Our contribution is to significantly improve the approximation hardness of various OCSPs and provide the first unconditional direct Probabilistically Checkable Proofs for OCSPs.Notably, all results were previously known assuming the Unique Games Conjecture and the d-to-1 Conjecture. Our unconditional analogues of the same theorems involve developments for dealing with various obstacles faced by conventional techniques.

Place, publisher, year, edition, pages
Stockholm: Numerical Analysis and Computer Science (NADA), Stockholm University , 2014. , xii, 52 p.
Keyword [en]
Optimization, NP, Approximation, Approximability, Inapproximability, Constraint Satisfaction, CSP, Boolean Analysis, Satisfiability, SAT, Acyclic Subgraph, Betweenness, Unique Games
National Category
Computer Science
Research subject
Computer Science
Identifiers
URN: urn:nbn:se:kth:diva-151402OAI: oai:DiVA.org:kth-151402DiVA: diva2:748501
Public defence
2014-10-21, F3, Sing Sing, Lindstedtsvägen 26, KTH, Stockholm, 13:15 (English)
Opponent
Supervisors
Projects
Approximation of NP-hard optimization problems
Funder
EU, European Research Council, 226203
Note

QC 20140929

Available from: 2014-09-29 Created: 2014-09-19 Last updated: 2014-09-30Bibliographically approved
List of papers
1. On the NP-hardness of approximating ordering constraint satisfaction problems
Open this publication in new window or tab >>On the NP-hardness of approximating ordering constraint satisfaction problems
2013 (English)In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques: 16th International Workshop, APPROX 2013, and 17th International Workshop, RANDOM 2013, Berkeley, CA, USA, August 21-23, 2013. Proceedings, Springer, 2013, 26-41 p.Conference paper, Published paper (Refereed)
Abstract [en]

We show improved NP-hardness of approximating Ordering Constraint Satisfaction Problems (OCSPs). For the two most well-studied OCSPs, Maximum Acyclic Subgraph and Maximum Betweenness, we prove inapproximability of 14/15 + ε and 1/2 + ε. An OCSP is said to be approximation resistant if it is hard to approximate better than taking a uniformly random ordering. We prove that the Maximum Non- Betweenness Problem is approximation resistant and that there are width-m approximation-resistant OCSPs accepting only a fraction 1/(m/2)! of assignments. These results provide the first examples of approximation-resistant OCSPs subject only to P ≠ NP. Our reductions from Label Cover differ from previous works in two ways. First, we establish a somewhat general bucketing lemma permitting us to reduce the analysis of ordering predicates to that of classical predicates. Second, instead of "folding", which is not available for ordering predicates, we employ permuted instantiations of the predicates to limit the value of poorly correlated strategies.

Place, publisher, year, edition, pages
Springer, 2013
Series
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), ISSN 0302-9743 ; 8096 LNCS
Keyword
Acyclic subgraph, Betweenness, Inapproximability, IS approximation, NP-hardness, Ordering constraints, Two ways
National Category
Computer and Information Science
Identifiers
urn:nbn:se:kth:diva-136123 (URN)10.1007/978-3-642-40328-6_3 (DOI)2-s2.0-84885206841 (Scopus ID)978-364240327-9 (ISBN)
Conference
16th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2013 and the 17th International Workshop on Randomization and Computation, RANDOM 2013; Berkeley, CA; United States; 21 August 2013 through 23 August 2013
Note

QC 20131204

Available from: 2013-12-04 Created: 2013-12-03 Last updated: 2014-09-29Bibliographically approved
2. Circumventing d-to-1 for approximation resistance of satisfiable predicates strictly containing parity of width four (extended abstract)
Open this publication in new window or tab >>Circumventing d-to-1 for approximation resistance of satisfiable predicates strictly containing parity of width four (extended abstract)
2012 (English)In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, Springer-Verlag , 2012, 325-337 p.Conference paper, Published paper (Refereed)
Abstract [en]

Håstad established that any predicate P ⊆ {0,1} m containing parity of width at least three is approximation resistant for almost satisfiable instances. However, in comparison to for example the approximation hardness of Max-3SAT, the result only holds for almost satisfiable instances. This limitation was mitigated by O'Donnell, Wu, and Huang under the d-to-1 Conjecture. They showed the threshold result that if a predicate contains parity of width at least three, then it is approximation resistant also for satisfiable instances. We extend modern hardness of approximation techniques by Mossel et al. to projection games, eliminating dependencies on the degree of projections via Smooth Label Cover, and prove unconditionally the same approximation resistance result for predicates of width four.

Place, publisher, year, edition, pages
Springer-Verlag, 2012
Series
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), ISSN 0302-9743 ; 7408 LNCS
Keyword
Approximation hardness, Extended abstracts, Hardness of approximation, IS approximation, Combinatorial optimization, Approximation algorithms
National Category
Computer and Information Science
Identifiers
urn:nbn:se:kth:diva-104871 (URN)10.1007/978-3-642-32512-0_28 (DOI)2-s2.0-84865286142 (Scopus ID)978-364232511-3 (ISBN)
Conference
15th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2012 and the 16th International Workshop on Randomization and Computation, RANDOM 2012, 15 August 2012 through 17 August 2012, Cambridge, MA
Note

QC 20121114

Available from: 2012-11-14 Created: 2012-11-14 Last updated: 2014-09-29Bibliographically approved
3. Circumventing d-to-1 for Approximation Resistance of Satisfiable Predicates Strictly Containing Parity of Width at Least Four
Open this publication in new window or tab >>Circumventing d-to-1 for Approximation Resistance of Satisfiable Predicates Strictly Containing Parity of Width at Least Four
2012 (English)In: Electronic Colloquium on Computational Complexity (ECCC), ISSN 1433-8092Article in journal (Refereed) Published
Abstract [en]

Håstad established that any predicate P01m  containing parity of width at least three is approximation resistant for almost satisfiable instances. However, in comparison to for example the approximation hardness of Max-3SAT, the result only holds for almost satisfiable instances. This limitation was addressed by O'Donnell, Wu, and Huang who showed the threshold result that if a predicate strictly contains parity of width at least three, then it is approximation resistant also for satisfiable instances, assuming the d-to-1 Conjecture. We extend modern hardness-of-approximation techniques by Mossel et al. to projection games, eliminating dependencies on the degree of projections via Smooth Label Cover, and prove, subject only to = , the same approximation-resistance result for predicates of width four or greater.

Keyword
Approximation Resistance, correlations, d-to-1 conjecture, Invariance, Perfect Completeness, Smooth Label cover
National Category
Computer Science
Identifiers
urn:nbn:se:kth:diva-113213 (URN)
Note

QC 20130502

Available from: 2013-01-14 Created: 2013-01-14 Last updated: 2014-09-29Bibliographically approved
4. Parity is Positively Useless
Open this publication in new window or tab >>Parity is Positively Useless
2014 (English)In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques: The 17th. International Workshop on Approximation Algorithms for Combinatorial Optimization Problems / [ed] Klaus Jansen, José Rolim, Nikhil Devanur, and Cristopher Moore, Dagstuhl, Germany: Schloss Dagstuhl , 2014, 433-448 p.Conference paper, Published paper (Refereed)
Abstract [en]

We give the first examples of non-trivially positively-useless predicates subject only to P != NP. In particular, for every constraint function Q : {-1,1}^4 -> R, we construct Contraint-Satisfaction-Problem (CSP) instances without negations which have value at least 1-eps when evaluted for the arity-four odd-parity predicate, yet it is NP-hard to find a solution with value significantly better than a random biased assignment when evaluated for Q. More generally, we show that all parities except one are positively useless. Although we are not able to exhibit a single protocol producing hard instances when evaluated for every Q, we show that two protocols do the trick. The first protocol is the classical one used by Håstad with a twist. We extend the protocol to multilayered Label Cover and employ a particular distribution over layers in order to limit moments of table biases. The second protocol is a modification of Chan's multi-question protocol where queried tuples of Label Cover vertices are randomized in such a way that the tables can be seen as being independently sampled from a common distribution and in effect having identical expected biases. We believe that our techniques may prove useful in further analyzing the approximability of CSPs without negations.

Place, publisher, year, edition, pages
Dagstuhl, Germany: Schloss Dagstuhl, 2014
Series
APPROX, ISSN 1868-8969 ; 17
Keyword
Approximation hardness, approximation resistance, parity, usefulness, negations, monotone, constraint satisfaction problems, smoothness, multilayer
National Category
Computer Science
Research subject
Computer Science
Identifiers
urn:nbn:se:kth:diva-151401 (URN)10.4230/LIPIcs.APPROX-RANDOM.2014.433 (DOI)2-s2.0-84920192892 (Scopus ID)978-3-939897-74-3 (ISBN)
Conference
APPROX/RANDOM 2014
Projects
Approximation of NP-hard optimization problems
Funder
EU, European Research Council, 226203
Note

QC 20140922

Available from: 2014-09-19 Created: 2014-09-19 Last updated: 2014-09-29Bibliographically approved

Open Access in DiVA

No full text

Other links

Diva Stockholm Univ.

Search in DiVA

By author/editor
Wenner, Cenny
Computer Science

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 137 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf