Thumbnail
Access Restriction
Subscribed

Author Fiorini, Samuel ♦ Massar, Serge ♦ Pokutta, Sebastian ♦ Tiwary, Hans Raj ♦ Wolf, Ronald De
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2015
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Combinatorial optimization ♦ Communication complexity ♦ Linear programming ♦ Quantum communication complexity ♦ Semidefinite programming
Abstract We solve a 20-year old problem posed by Yannakakis and prove that no polynomial-size linear program (LP) exists whose associated polytope projects to the traveling salesman polytope, even if the LP is not required to be symmetric. Moreover, we prove that this holds also for the cut polytope and the stable set polytope. These results were discovered through a new connection that we make between one-way quantum communication protocols and semidefinite programming reformulations of LPs.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2015-05-06
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 62
Issue Number 2
Page Count 23
Starting Page 1
Ending Page 23


Open content in new tab

   Open content in new tab
Source: ACM Digital Library