Show simple item record

dc.contributor.authorAtserias, Aen
dc.contributor.authorDawar, Anujen
dc.date.accessioned2019-09-06T23:32:07Z
dc.date.available2019-09-06T23:32:07Z
dc.date.issued2019-12-31en
dc.identifier.issn0955-792X
dc.identifier.urihttps://www.repository.cam.ac.uk/handle/1810/296566
dc.description.abstractWe 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~$\PT = \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.
dc.publisherOxford University Press
dc.rightsAll rights reserved
dc.rights.uri
dc.titleDefinable inapproximability: New challenges for duplicatoren
dc.typeArticle
prism.endingPage1210
prism.issueIdentifier8en
prism.publicationDate2019en
prism.publicationNameJournal of Logic and Computationen
prism.startingPage1185
prism.volume29en
dc.identifier.doi10.17863/CAM.43613
dcterms.dateAccepted2019-09-03en
rioxxterms.versionofrecord10.1093/logcom/exz022en
rioxxterms.versionAM
rioxxterms.licenseref.urihttp://www.rioxx.net/licenses/all-rights-reserveden
rioxxterms.licenseref.startdate2019-12-31en
dc.contributor.orcidDawar, Anuj [0000-0003-4014-8248]
dc.identifier.eissn1465-363X
rioxxterms.typeJournal Article/Reviewen
pubs.funder-project-idEPSRC (EP/S03238X/1)
cam.orpheus.successTue Mar 31 10:39:56 BST 2020 - Embargo updated*
cam.orpheus.counter2*
rioxxterms.freetoread.startdate2020-12-31


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record