Show simple item record

dc.contributor.authorAnderson, Matthewen
dc.contributor.authorDawar, Anujen
dc.contributor.authorHolm, Bjarkien
dc.date.accessioned2015-09-22T09:36:40Z
dc.date.available2015-09-22T09:36:40Z
dc.date.issued2015-12-10en
dc.identifier.citationJournal of the ACM 2015, 62(6): 48. doi:10.1145/2822890en
dc.identifier.issn0004-5411
dc.identifier.urihttps://www.repository.cam.ac.uk/handle/1810/251099
dc.description.abstractWe show that the ellipsoid method for solving linear programs can be implemented in a way that respects the symmetry of the program being solved. That is to say, there is an algorithmic implementation of the method that does not distinguish, or make choices, between variables or constraints in the program unless they are distinguished by properties definable from the program. In particular, we demonstrate that the solvability of linear programs can be expressed in fixed-point logic with counting (FPC) as long as the program is given by a separation oracle that is itself definable in FPC. We use this to show that the size of a maximum matching in a graph is definable in FPC. This settles an open problem first posed by Blass, Gurevich and Shelah [Blass et al. 1999]. On the way to defining a suitable separation oracle for the maximum matching program, we provide FPC formulas defining canonical maximum flows and minimum cuts in undirected capacitated graphs.
dc.description.sponsorshipResearch supported by EPSRC grant EP/H026835.
dc.languageEnglishen
dc.language.isoenen
dc.publisherACM
dc.subjectlinear programmingen
dc.subjectmaximum matchingen
dc.subjectellipsoid methoden
dc.subjectfixed-point logic with countingen
dc.subjectchoiceless polynomial timeen
dc.titleSolving Linear Programs without Breaking Abstractionsen
dc.typeArticle
dc.description.versionThis is the author accepted manuscript. The final version is available from ACM via http://dx.doi.org/10.1145/2822890en
prism.number48en
prism.publicationDate2015en
prism.publicationNameJournal of the ACMen
prism.volume62en
dc.rioxxterms.funderEPSRC
dc.rioxxterms.projectidEP/H026835
dcterms.dateAccepted2015-09-08en
rioxxterms.licenseref.urihttp://www.rioxx.net/licenses/all-rights-reserveden
rioxxterms.licenseref.startdate2015-12-10en
dc.contributor.orcidDawar, Anuj [0000-0003-4014-8248]
dc.identifier.eissn1557-735X
rioxxterms.typeJournal Article/Reviewen
pubs.funder-project-idEPSRC (EP/H026835/1)


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record