Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Extended Formulations from Communication Protocols in Output-Efficient Time
 
conference paper

Extended Formulations from Communication Protocols in Output-Efficient Time

Aprile, Manuel  
•
Faenza, Yuri  
January 1, 2019
Integer Programming And Combinatorial Optimization, Ipco 2019
20th International Conference on Integer Programming and Combinatorial Optimization (IPCO)

Deterministic protocols are well-known tools to obtain extended formulations, with many applications to polytopes arising in combinatorial optimization. Although constructive, those tools are not output-efficient, since the time needed to produce the extended formulation also depends on the number of rows of the slack matrix (hence, of the exact description in the original space). We give general sufficient conditions under which those tools can be implemented as to be output-efficient, showing applications to e.g. Yannakakis' extended formulation for the stable set polytope of perfect graphs, for which, to the best of our knowledge, an efficient construction was previously not known. For specific classes of polytopes, we give also a direct, efficient construction of those extended formulations. Finally, we deal with extended formulations coming from certain unambiguous non-deterministic protocols.

  • Details
  • Metrics
Type
conference paper
DOI
10.1007/978-3-030-17953-3_4
Web of Science ID

WOS:000493314100004

Author(s)
Aprile, Manuel  
Faenza, Yuri  
Date Issued

2019-01-01

Publisher

SPRINGER INTERNATIONAL PUBLISHING AG

Publisher place

Cham

Published in
Integer Programming And Combinatorial Optimization, Ipco 2019
ISBN of the book

978-3-030-17953-3

978-3-030-17952-6

Series title/Series vol.

Lecture Notes in Computer Science

Volume

11480

Start page

43

End page

56

Subjects

Computer Science, Theory & Methods

•

Computer Science

•

communication protocols

•

extended formulations

•

perfect graphs

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
DISOPT  
Event nameEvent placeEvent date
20th International Conference on Integer Programming and Combinatorial Optimization (IPCO)

Ann Arbor, MI

May 22-24, 2019

Available on Infoscience
November 15, 2019
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/163124
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés