Symmetry Matters for Sizes of Extended Formulations

Mathematics – Combinatorics

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

23 pages; the new version slightly sharpens the lower bound results and provides corresponding proofs that we believe are easi

Scientific paper

In 1991, Yannakakis (J. Comput. System Sci., 1991) proved that no symmetric extended formulation for the matching polytope of the complete graph K_n with n nodes has a number of variables and constraints that is bounded subexponentially in n. Here, symmetric means that the formulation remains invariant under all permutations of the nodes of K_n. It was also conjectured in the paper mentioned above that "asymmetry does not help much," but no corresponding result for general extended formulations has been found so far. In this paper we show that for the polytopes associated with the matchings in K_n with log(n) (rounded down) edges there are non-symmetric extended formulations of polynomial size, while nevertheless no symmetric extended formulations of polynomial size exist. We furthermore prove similar statements for the polytopes associated with cycles of length log(n) (rounded down). Thus, with respect to the question for smallest possible extended formulations, in general symmetry requirements may matter a lot. Compared to the extended abtract that has appeared in the Proceedings of IPCO XIV at Lausanne, this paper does not only contain proofs that had been ommitted there, but it also presents slightly generalized and sharpened lower bounds.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

Symmetry Matters for Sizes of Extended Formulations 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 Symmetry Matters for Sizes of Extended Formulations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Symmetry Matters for Sizes of Extended Formulations will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-452634

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.