Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
On the NP-Hardness of Approximating Ordering-Constraint Satisfaction Problems
Stockholms universitet, Naturvetenskapliga fakulteten, Numerisk analys och datalogi (NADA). KTH - Royal Institute of Technology, Sweden.
2015 (Engelska)Ingår i: Theory of Computing, E-ISSN 1557-2862, Vol. 11, artikel-id 10Artikel i tidskrift (Refereegranskat) 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.

Ort, förlag, år, upplaga, sidor
2015. Vol. 11, artikel-id 10
Nyckelord [en]
acyclic subgraph, APPROX, approximation, approximation resistance, betweenness, constraint satisfaction, CSPs, feedback arc set, hypercontractivity, NP-completeness, orderings, PCP, probabilistically checkable proofs
Nationell ämneskategori
Datavetenskap (datalogi)
Forskningsämne
datalogi
Identifikatorer
URN: urn:nbn:se:su:diva-107683DOI: 10.4086/toc.2015.v011a010OAI: oai:DiVA.org:su-107683DiVA, id: diva2:749393
Projekt
ApproxNP
Forskningsfinansiär
EU, Europeiska forskningsrådet, 226203Vetenskapsrådet, 621-2012-4546Tillgänglig från: 2014-09-24 Skapad: 2014-09-24 Senast uppdaterad: 2024-02-27Bibliografiskt granskad
Ingår i avhandling
1. Label Cover Reductions for Unconditional Approximation Hardness of Constraint Satisfaction
Öppna denna publikation i ny flik eller fönster >>Label Cover Reductions for Unconditional Approximation Hardness of Constraint Satisfaction
2014 (Engelska)Doktorsavhandling, sammanläggning (Övrigt vetenskapligt)
Alternativ titel[sv]
Ettikettäckningsreduktioner för Obetingad Approximationssvårighet av Vilkorsuppfyllning
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.

Ort, förlag, år, upplaga, sidor
Stockholm: Numerical Analysis and Computer Science (NADA), Stockholm University, 2014. s. 55
Nyckelord
Combinatorial Optimization, Complexity Theory, Approximation, Approximability, Inapproximability, Computational Hardness, NP, Optimization, Constraint Satisfaction, Kombinatorisk optimering, Komplexitetsteori, Beräkningsteori, Approximation, Approximerbarhet, Beräkningssvårighet, NP, Optimering, Vilkorssatisfiering, Vilkorsuppfyllning, Vilkorstillfredställand
Nationell ämneskategori
Datavetenskap (datalogi)
Forskningsämne
datalogi
Identifikatorer
urn:nbn:se:su:diva-107685 (URN)978-91-7447-997-3 (ISBN)
Disputation
2014-10-21, sal F3, Sing Sing, Kungliga Tekniska Högskolan, Lindstedtsvägen 26, Stockholm, 13:15 (Engelska)
Opponent
Handledare
Projekt
ApproxNP
Forskningsfinansiär
EU, Europeiska forskningsrådet, 226203
Anmärkning

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

Tillgänglig från: 2014-09-29 Skapad: 2014-09-24 Senast uppdaterad: 2022-02-23Bibliografiskt granskad

Open Access i DiVA

fulltext(326 kB)153 nedladdningar
Filinformation
Filnamn FULLTEXT01.pdfFilstorlek 326 kBChecksumma SHA-512
f1ec55465857cb797cea9b37da143c4026cb101caba307f0e51727e97b88855cc6ba3e66d354ad62488d71e91cac9d96837417b28abf7498dbc2f68db5ab36ef
Typ fulltextMimetyp application/pdf

Övriga länkar

Förlagets fulltext

Person

Wenner, Cenny

Sök vidare i DiVA

Av författaren/redaktören
Wenner, Cenny
Av organisationen
Numerisk analys och datalogi (NADA)
I samma tidskrift
Theory of Computing
Datavetenskap (datalogi)

Sök vidare utanför DiVA

GoogleGoogle Scholar
Totalt: 153 nedladdningar
Antalet nedladdningar är summan av nedladdningar för alla fulltexter. Det kan inkludera t.ex tidigare versioner som nu inte längre är tillgängliga.

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 370 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf