Explore the construction of extended formulations in this lecture by Volker Kaibel from Otto-von-Guericke-Universität Magdeburg. Delve into topics such as convex hulls, linear programming, representations as projections, and various polytopes including completion times, colorful matching, and cycle polytopes. Examine special matchings, perfect hash functions, and hyperpath polytopes. Investigate branched combinatorial and polyhedral systems, extended formulations via duality, and their applications to spanning tree polytopes. Learn about non-extended formulations of nonempty-subgraphs polytopes, graphs of bounded genus, and spanning trees in planar graphs. Gain insights into linear descriptions and polynomial spanning tree optimization in this comprehensive exploration of extended formulations and related concepts.
Overview
Syllabus
Intro
Convex Hulls and Linear Programming
Representations as Projections
Completion Times Polytope
Unions of Polytopes
Special Matchings
Colorful Matching Polytopes
Making all Matchings Colorful
Perfect Hash Functions
Outline
Special Cycles
Colorful Cycles with Prescribed Node a
Colorful Cycle Polytopes (Prescribed Node)
Combining Things for Cycle Polytopes
Hyperpath Polytopes
Branched Combinatorial/Polyhedral Systems
Extended Formulatations via Duality
Application to Spanning Tree Polytopes
Extended Formulations for Non-Empty Subgraphs Polytopes All Subgraphs Polytope of G
Non-Extended Formulations of Nonempty-Subgraphs Polytopes
Graphs of Bounded Genus
Spanning Trees in Planar Graphs
Linear Description of Pub
Polynomial Spanning Tree Optimization Setup for G=(V. E), MS2 (acyclic subsets)
Taught by
Simons Institute
