kth.sePublikationer
Ä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 usefulness of predicates
KTH, Skolan för datavetenskap och kommunikation (CSC), Teoretisk datalogi, TCS.ORCID-id: 0000-0002-5379-345X
2012 (Engelska)Ingår i: 2012 IEEE 27th Annual Conference On Computational Complexity (CCC), IEEE , 2012, s. 53-63Konferensbidrag, Publicerat paper (Refereegranskat)
Abstract [en]

Motivated by the pervasiveness of strong in approximability results for Max-CSPs, we introduce a relaxed notion of an approximate solution of a Max-CSP. In this relaxed version, loosely speaking, the algorithm is allowed to replace the constraints of an instance by some other (possibly real-valued) constraints, and then only needs to satisfy as many of the new constraints as possible. To be more precise, we introduce the following notion of a predicate P being \emph{useful} for a (real-valued) objective Q: given an almost satisfiable Max-P instance, there is an algorithm that beats a random assignment on the corresponding Max-Q instance applied to the same sets of literals. The standard notion of a nontrivial approximation algorithm for a Max-CSP with predicate P is exactly the same as saying that P is useful for P itself. We say that P is useless if it is not useful for any Q. Under the Unique Games Conjecture, we can give a complete and simple characterization of useless Max-CSPs defined by a predicate: such a Max-CSP is useless if and only if there is a pair wise independent distribution supported on the satisfying assignments of the predicate. It is natural to also consider the case when no negations are allowed in the CSP instance, and we derive a similar complete characterization (under the UGC) there as well. Finally, we also include some results and examples shedding additional light on the approximability of certain Max-CSPs.

Ort, förlag, år, upplaga, sidor
IEEE , 2012. s. 53-63
Serie
Proceedings of the Annual IEEE Conference on Computational Complexity, ISSN 1093-0159
Nyckelord [en]
Approximability, Approximate solution, Literals, MAX-CSP, Random assignment, Satisfying assignments, Unique games conjecture, Computational complexity, Approximation algorithms
Nationell ämneskategori
Datavetenskap (datalogi)
Identifikatorer
URN: urn:nbn:se:kth:diva-105331DOI: 10.1109/CCC.2012.18ISI: 000308976600006Scopus ID: 2-s2.0-84866503497ISBN: 978-0-7695-4708-4 (tryckt)OAI: oai:DiVA.org:kth-105331DiVA, id: diva2:570627
Konferens
IEEE Computer Society Technical Committee on Mathematical Foundations of Computing, 26 June 2012 through 29 June 2012, Porto
Anmärkning

QC 20121120

Tillgänglig från: 2012-11-20 Skapad: 2012-11-20 Senast uppdaterad: 2022-06-24Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltextScopus

Person

Håstad, Johan

Sök vidare i DiVA

Av författaren/redaktören
Håstad, Johan
Av organisationen
Teoretisk datalogi, TCS
Datavetenskap (datalogi)

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetricpoäng

doi
isbn
urn-nbn
Totalt: 330 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