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 |
- A regular participation in the talks and an active collaboration are mandatory for passing the seminar.
- The talks will take approximately 75 minutes. The remaining 15 minutes are intended for a discussion.
- Each participant has to write a summary consisting of one or two pages.
- Each participant has to give an approval talk (typically three weeks before the regular talk). Passing the approval talk is a prerequisite for giving the regular seminar talk.
Prof. Dr. B. Korte,
Prof. Dr.J. Vygen,
Prof. Dr. S. Hougardy,
Prof. Dr. S. Held,
Dr. U. Brenner