Graduate Seminar on Discrete Optimization (S4C1)

Summer 2017


Extended Formulations


Class hours: Mondays 14:15-15:45. Approval talks: 12:15-13:45

Number Approval talk Talk Name Topic Mentoring
1 10.4.
24.4. Benjamin Klotz Expressing Combinatorial Optimization Problems by Linear Programs Philipp Ochsendorf
2 10.4.
8.5. Fabian Zaiser Symmetry matters for sizes of extended formulations Anna Hermann
3 24.4.
15.5. Dorothee Henke Some 0/1 polytopes need exponential size extended formulations Tomas Salles
4 8.5.
22.5. Benjamin Rockel Exponential lower bounds for polytopes in combinatorial optimization Rudolf Scheifele
5 15.5.
29.5. Friederike Michaelis The matching polytope has exponential extension complexity Daniel Rotter
6 22.5.
12.6. Ardalan Khazraei Approximation limits of linear programs (beyond hierarchies) Rudolf Scheifele
7 29.5.
19.6. Robert Vicari Approximate constraint satisfaction requires large LP relaxations Anna Hermann
8 12.6.
26.6. Ioana Simon No small linear program approximates vertex cover within a factor 2 - epsilon Jannik Silvanus
9 19.6.
3.7. Tobias Elvermann On the existence of 0/1 polytopes with high semidefinite extension complexity Jannik Silvanus
10 26.6.
10.7. Thekla Hamm Extended formulations for permutahedra Pietro Saccardi
11 3.7.
17.7. Lucas Slot Lower bounds on the size of semidefinite programming relaxations (Section 3) Pietro Saccardi
12 10.7.
24.7. Stefan Rabenstein Lower bounds on the size of semidefinite programming relaxations (Sections 5 and 6) Niko Klewinghaus
13 10.7. (16 Uhr)
24.7. Klaus Heeger Lower bounds on the size of semidefinite programming relaxations (Sections 4 and 7) Niko Klewinghaus


Prof. Dr. B. Korte,
Prof. Dr.J. Vygen,
Prof. Dr. S. Hougardy,
Prof. Dr. S. Held,
Dr. U. Brenner