About: This thesis investigates the extent to which the optimal value of a constraint satisfaction problem (CSP) can be approximated by some sentence of fixed point logic with counting (FPC). It is known that, assuming $/mathsf{P} /neq /mathsf{NP}$ and the Unique Games Conjecture, the best polynomial time approximation algorithm for any CSP is given by solving and rounding a specific semidefinite programming relaxation. We prove an analogue of this result for algorithms that are definable as FPC-interpretations, which holds without the assumption that $/mathsf{P} /neq /mathsf{NP}$. While we are not able to drop (an FPC-version of) the Unique Games Conjecture as an assumption, we do present some partial results toward proving it. Specifically, we give a novel construction which shows that, for all $/alpha>0$, there exists a positive integer $q = /text{poly}(/frac{1}{/alpha})$ such that no there is no FPC-interpretation giving an $/alpha$-approximation of Unique Games on a label set of size $q$.   Goto Sponge  NotDistinct  Permalink

An Entity of Type : fabio:Abstract, within Data Space : covidontheweb.inria.fr associated with source document(s)

AttributesValues
type
value
  • This thesis investigates the extent to which the optimal value of a constraint satisfaction problem (CSP) can be approximated by some sentence of fixed point logic with counting (FPC). It is known that, assuming $/mathsf{P} /neq /mathsf{NP}$ and the Unique Games Conjecture, the best polynomial time approximation algorithm for any CSP is given by solving and rounding a specific semidefinite programming relaxation. We prove an analogue of this result for algorithms that are definable as FPC-interpretations, which holds without the assumption that $/mathsf{P} /neq /mathsf{NP}$. While we are not able to drop (an FPC-version of) the Unique Games Conjecture as an assumption, we do present some partial results toward proving it. Specifically, we give a novel construction which shows that, for all $/alpha>0$, there exists a positive integer $q = /text{poly}(/frac{1}{/alpha})$ such that no there is no FPC-interpretation giving an $/alpha$-approximation of Unique Games on a label set of size $q$.
Subject
  • Constraint programming
  • Computational complexity theory
  • Order theory
  • Complexity classes
  • Approximation algorithms
  • Conjectures
  • Computational hardness assumptions
  • Unsolved problems in computer science
  • 2002 in computer science
part of
is abstract of
is hasSource of
Faceted Search & Find service v1.13.91 as of Mar 24 2020


Alternative Linked Data Documents: Sponger | ODE     Content Formats:       RDF       ODATA       Microdata      About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data]
OpenLink Virtuoso version 07.20.3229 as of Jul 10 2020, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (94 GB total memory)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2025 OpenLink Software