Linear vs. Semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds

Details Linear vs. Semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds Linear vs. Semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds

2011-11-03

arxiv.org/abs/1111.0837v2

Mathematics

Combinatorics

15 pages, 1 figure

Scientific paper

We solve a 20-year old problem posed by M. Yannakakis and prove that there exists no polynomial-size linear program (LP) 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 maximum cut problem and the stable set problem. These results follow from a new connection that we make between one-way quantum communication protocols and semidefinite programming reformulations of LPs.

Affiliated with

Also associated with

No associations

Rating

Linear vs. Semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Linear vs. Semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Linear vs. Semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-702626