License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CSL.2018.7
URN: urn:nbn:de:0030-drops-96742
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9674/
Go to the corresponding LIPIcs Volume Portal

Atserias, Albert ; Dawar, Anuj

Definable Inapproximability: New Challenges for Duplicator

pdf-format:
LIPIcs-CSL-2018-7.pdf (0.5 MB)

Abstract

We consider the hardness of approximation of optimization problems from the point of view of definability. For many NP-hard optimization problems it is known that, unless P = NP, no polynomial-time algorithm can give an approximate solution guaranteed to be within a fixed constant factor of the optimum. We show, in several such instances and without any complexity theoretic assumption, that no algorithm that is expressible in fixed-point logic with counting (FPC) can compute an approximate solution. Since important algorithmic techniques for approximation algorithms (such as linear or semidefinite programming) are expressible in FPC, this yields lower bounds on what can be achieved by such methods. The results are established by showing lower bounds on the number of variables required in first-order logic with counting to separate instances with a high optimum from those with a low optimum for fixed-size instances.

BibTeX - Entry

@InProceedings{atserias_et_al:LIPIcs:2018:9674,
  author =	{Albert Atserias and Anuj Dawar},
  title =	{{Definable Inapproximability: New Challenges for Duplicator}},
  booktitle =	{27th EACSL Annual Conference on Computer Science Logic  (CSL 2018)},
  pages =	{7:1--7:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-088-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{119},
  editor =	{Dan Ghica and Achim Jung},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9674},
  URN =		{urn:nbn:de:0030-drops-96742},
  doi =		{10.4230/LIPIcs.CSL.2018.7},
  annote =	{Keywords: Descriptive Compleixty, Hardness of Approximation, MAX SAT, Vertex Cover, Fixed-point logic with counting}
}

Keywords: Descriptive Compleixty, Hardness of Approximation, MAX SAT, Vertex Cover, Fixed-point logic with counting
Collection: 27th EACSL Annual Conference on Computer Science Logic (CSL 2018)
Issue Date: 2018
Date of publication: 29.08.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI