Content: 
 
This seminar discusses topics in integer programming and combinatorial optimization.  
 
Requirements: 
 
This seminar addresses the attendance of the lecture Discrete Mathematics II: Optimization (WS23/24) and Discrete Mathematics III: Integer Programming (SS24). 
 
Organisation:
 
The seminar will be held as a block seminar of three appointments:
- Thu, 18.10.2024, 10:30, ZIB, R 3034: Topic assignment
- Tue, 10.12.2024, 13:00, ZIB, R 2006: Short talks
- Tue, 04.02.2025, 9:00, ZIB, R 2006 and
   Fri, 07.02.2025, 9:00, ZIB, R 2006: Talks
 
In the second meeting, short talks on what you plan to present and how you want to do it will be held. The actual seminar is in February. Everybody gives 2 professional talks of 45 minutes, one in lecture style, and the second about an example, an application, and extension etc. on which you have worked yourself.
 
The second requirement is a 5 page summary of the talk in Master's thesis quality. The limit of 5 pages including title page and literature is strict.  
 

We have the following topic assignment:

1. Nobody: Minimum weight arborescences [a polynomial time algorithm, Korte & Vygen Chapter 6, Section 2]

2. Nobody: Matroid intersection [a complete description, Korte & Vygen Chapter 13, Sectiuon 4]

3. Nobody: Set covering [an approximation algorithm, A Greedy Heuristic for the Set-Covering Problem on JSTOR]

4. Liquin Chen: 2-person 0-sum games [Chvatal, Linear Programming, Chapter 13, (PDF) Zero-Sum Two Person Games]

5. Hassan Hiyazi: Machine scheduling [approximation, Brucker, Peter: Scheduling Algorithms 4th ed., 2004, Springer Verlag Berlin, Hardcover, ISBN: 3-540-20524-1; Pinedo, Michael L: Scheduling: Theory, Algorithms, and Systems 2nd ed., 2002, Prentice Hall, ISBN 0-13-028138-7; https://www.zib.de/userpage/groetschel/teaching/skriptADM-I.pdf, Kap. 13]

6. Theresa Graeber: Contraction hierarchies [a shorstet path algorithm, Exact Routing in Large Road Networks Using Contraction Hierarchies on JSTOR]

7. Tugba Akkaya: Facility location [approximation, Korte & Vygen Chapter 22, Section 3]

8. Vanessa Hiebeler: Max cut [approxmiation by semidefinite programming, math.mit.edu/~goemans/PAPERS/maxcut-jacm.pdf]

9. Nobody: Stable sets in perfect graphs [a complete description, GLS]

10. Nobody: IP in fixed dimension [On the complexity of integer programming in fixed dimension (researchgate.net)]

11. Nobody: Basis reduction & LLL algorithm  [a lattice based algorithm, sources to be identified by yourself]

12. Nobody: Network simplex algorithm [dito, Chvatal, Linear Programming]

13. Baixin Chen: Vehicle Routing [Vehicle Routing | SIAM Publications Library; relevant parts of https://optimizingwithcolumngeneration.github.io/]

14. Sergio Tinaharimanjaka: Railway Track Allocation [Railway Track Allocation | SpringerLink; https://doi.org/10.1007/s00291-009-0189-0]