Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • 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). (ApproxNP)
2014 (English)Doctoral thesis, comprehensive summary (Other academic)Alternative title
Ettikettäckningsreduktioner för Obetingad Approximationssvårighet av Vilkorsuppfyllning (Swedish)
Abstract [en]

Combinatorial optimization include such tasks as finding the quickest route to work, scheduling jobs to specialists, and placing bus stops so as to minimize commuter times. We consider problems where one is given a collection of constraints with the objective of finding an assignment satisfying as many constraints as possible, also known as Constraint Satisfaction Problems (CSPs). Most CSPs are NP-hard to solve optimally and we turn to approximations - a solution is said to be a factor-c approximation if its satisfies at least c times the optimal number of constraints. This thesis presents new results on the approximation limits of CSPs in various settings.

In ordering CSPs, one is given constraints which specify the relative order of items, and the objective is order the items so as to satisfy as many constraints as possible. We give improved approximation hardness results for two classical problems: it is NP-hard to approximate Maximum Acyclic Subgraph with a factor better than 14/15 and Maximum Betweenness with a factor better than 1/2. We present ordering problems which are NP-hard to approximate better than random assignments, and that there are ordering problems arbitrarily hard to approximate.

Next, Gaussian elimination can efficiently find exact solutions for satisfiable collections of so-called parity constraints. We show that whenever constraints accept at least one assignment in addition to a parity, then the problem is NP-hard to approximate better than random assignments. Finally, we study the uselessness property which basically states that if one is given a collection where almost all constraints are simultaneously satisfiable and one is permitted to relax the constraints to accept or reject additional assignments, then it is still NP-hard to find solutions noticeably better than random assignments. We consider the setting where all variables appear unnegated and provide the first examples of non-trivially useless predicates assuming only P != NP.

Abstract [sv]

Kombinatoriska optimering inkluderar naturliga uppgifter såsom att hitta den snabbaste vägen till sitt arbetet, att schemalägga jobb hos specialister, eller att placera hållplatser för att minimera resenärers restid.Vi begränsar vi oss till de problem i vilket man ges en samling vilkor på variablermed målet att hitta en tilldelning av variablerna uppfyllandes så många som möjligt av vilkoren;så kallade Vilkorsuppfyllningsproblem (eng: Constraint Satisfaction Problems, CSPs).De flesta CSPs är NP-svåra att lösa optimalt och vi beaktar istället approximationer. Specifikt kallas, för 0 <= c <= 1, en lösning för en faktor-c approximation om antalet vilkor uppfyllda av lösningen är minst cgånger det största antalet uppfyllda av någon läsning. Denna avhandling består av tre artiklar som presenterar nya resultat begränsande hurpass väl man kan approximera CSPs i diverse situationer.För paritetsvilkor är en samling konsistenta vilkor enkla att lösa genom Gausselimination. Vi visar att för samtliga vilkor som uppfylls av en paritet och åtminstonde en ytterliggare tilldelning så är det inte bara NP-svårt at lösa utan till och med att ge en icke-trivial approximation.Oanvändarbarhet är en stark svårighetsegenskap som i princip säger att det är NP-svårt att ge icke-triviala approximationer även när man gemensamt för alla vilkor får ändra vad som uppfyller dem eller inte. Vi ger de första exemplen på icke-trivialt oanvändbara vilkor utan negationer betingat endast på P != NP.Vi visar på approximerbarhet för diverse ordningsvilorsproblem. I dessa ges man vilkor på hur objekt ska vara ordnade relativt varandra och målet är att hitta en ordning som uppfyller så många av vilkoren som möjligt. Vi ger bättre svårighetsresultat för de två mest välkända ordningsproblem, visar att det finns problem där det är NP-svårt att approximera bättre än triviala strategier, och att det finns ordningsproblem där godtyckligt dåliga approximationsgarantier är NP-svåra.

Place, publisher, year, edition, pages
Stockholm: Numerical Analysis and Computer Science (NADA), Stockholm University , 2014. , 55 p.
Keyword [en]
Combinatorial Optimization, Complexity Theory, Approximation, Approximability, Inapproximability, Computational Hardness, NP, Optimization, Constraint Satisfaction
Keyword [sv]
Kombinatorisk optimering, Komplexitetsteori, Beräkningsteori, Approximation, Approximerbarhet, Beräkningssvårighet, NP, Optimering, Vilkorssatisfiering, Vilkorsuppfyllning, Vilkorstillfredställand
National Category
Computer Science
Research subject
Computer Science
Identifiers
URN: urn:nbn:se:su:diva-107685ISBN: 978-91-7447-997-3 (print)OAI: oai:DiVA.org:su-107685DiVA: diva2:749418
Public defence
2014-10-21, sal F3, Sing Sing, Kungliga Tekniska Högskolan, Lindstedtsvägen 26, Stockholm, 13:15 (English)
Opponent
Supervisors
Projects
ApproxNP
Funder
EU, European Research Council, 226203
Note

NADA är en delad institution mellan SU och KTH där senare nu kallar den CSC.

Available from: 2014-09-29 Created: 2014-09-24 Last updated: 2014-09-24Bibliographically 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
2015 (English)In: Theory of Computing, ISSN 1557-2862, E-ISSN 1557-2862, Vol. 11, 10Article in journal (Refereed) Published
Abstract [en]

We show improved NP-hardness of approximating Ordering Constraint Satis-faction Problems (OCSPs). For the two most well-studied OCSPs, Maximum Acyclic Subgraph and Maximum Betweenness, we prove NP-hard approximation factors of 14/15+ε and 1/2+ε. When it is hard to approximate an OCSP by a constant better than takinga uniformly-at-random ordering, then the OCSP is said to be approximation resistant. We show 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 only to P != NP.

Keyword
acyclic subgraph, APPROX, approximation, approximation resistance, betweenness, constraint satisfaction, CSPs, feedback arc set, hypercontractivity, NP-completeness, orderings, PCP, probabilistically checkable proofs
National Category
Computer Science
Research subject
Computer Science
Identifiers
urn:nbn:se:su:diva-107683 (URN)10.4086/toc.2015.v011a010 (DOI)
Projects
ApproxNP
Funder
EU, European Research Council, 226203Swedish Research Council, 621-2012-4546
Available from: 2014-09-24 Created: 2014-09-24 Last updated: 2017-12-05Bibliographically approved
2. 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
2013 (English)In: Theory of Computing, ISSN 1557-2862, E-ISSN 1557-2862, Vol. 9, no 23, 703-757 p.Article in journal (Refereed) Published
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. In comparison to, for example, the approximation hardness of 3SAT, this general result however left open the hardness of perfectly-satisfiable instances. This limitation was addressed by O'Donnell and Wu, and subsequently generalized by Huang, to show the threshold result that predicates strictly containing Parity of width at least three are approximation resistant also for perfectly-satisfiable instances, assuming the d-to-1 Conjecture.

We extend modern hardness-of-approximation techniques by Mossel et al., eliminating the dependency on projection degrees for a special case of decoupling/invariance and -- when reducing from Smooth Label Cover -- the dependency on projection degrees for noise introduction. Tools in hand, we prove the same approximation-resistance result for predicates of width at least four, subject only to P ≠ NP.

A preliminary version of this paper appeared in the International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX'12).

Place, publisher, year, edition, pages
Theory of Computing, 2013
Keyword
Boolean functions, hardness of approximation, inapproximability, constraint satisfaction, Fourier analysis, approximation resistance, dictatorship test, label cover, smooth label cover, correlation bounds, perfect completeness, invariance, d-to-1 games
National Category
Computer Science
Research subject
Computer Science
Identifiers
urn:nbn:se:su:diva-107681 (URN)10.4086/toc.2013.v009a023 (DOI)
Projects
ApproxNP
Funder
EU, European Research Council, 226203
Available from: 2014-09-24 Created: 2014-09-24 Last updated: 2017-12-05Bibliographically approved
3. Parity is Positively Useless
Open this publication in new window or tab >>Parity is Positively Useless
2014 (English)In: APPROX-RANDOM 2014, Vol. 28, 433-448 p.Article in journal (Refereed) Published
Place, publisher, year, edition, pages
Dagstuhl, Germany: Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2014
Keyword
Approximation hardness, approximation resistance, parity, usefulness, negations, monotone, constraint satisfaction problems, smoothness, multilayer, Label Cover
National Category
Computer Science
Research subject
Computer Science
Identifiers
urn:nbn:se:su:diva-107684 (URN)10.4230/LIPIcs.APPROX-RANDOM.2014.433 (DOI)
Conference
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX-RANDOM)
Projects
ApproxNP
Funder
EU, European Research Council, 226203
Note

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

Available from: 2014-09-24 Created: 2014-09-24 Last updated: 2014-10-10Bibliographically approved

Open Access in DiVA

Thesis excluding articles(824 kB)177 downloads
File information
File name FULLTEXT01.pdfFile size 824 kBChecksum SHA-512
6bc7532404efd67e5a01f662f4a7045a17abddf5dff112842eef14b3f8257320a934f964863ff755463a97bb1f563f99ff458589865877917df0fbdd524987db
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Wenner, Cenny
By organisation
Numerical Analysis and Computer Science (NADA)
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 177 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 236 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • 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