TU Berlin

FG Kombinatorische Optimierung und GraphenalgorithmenSE: Algorithmic Discrete Mathematics

COGA 5-Wheel

Inhalt des Dokuments

zur Navigation

Seminar on Algorithmic Discrete Mathematics

Purpose 

We will read and understand recent publications on Combinatorial Optimization, Discrete Algorithms, and related areas.

Prerequisites

Participants should already be familiar with the most important techniques and algorithms from Algorithmic Discrete Mathematics, as e.g. obtained by taking the courses on Geometric Foundations on Linear Optimization (former ADM I) and Discrete Optimization (ADM II).

Important Dates

On January 6, 2017, 10-12, in room MA548, all participants have to give a 5 minutes outline of their seminar topic. More details will be announced shortly.

The seminar will be organized as a block course and take place on February 22 and 23, 2017, between 9am and 6pm in room MA544. More details will be announced shortly.

An informal meeting took place on October 31, 2016 at 16:00h in room MA315.

In order to register for the seminar, please send an email to with the following information by Wednesday, Nov. 2:

  • last name:
  • first name:
  • matr.-nr.:
  • email-address: 
  • study program (BSc or MSc Mathe/Wirtschaftsmathe/Technomathe):
  • prior knowledge (which ADM-courses did you attend):
  • do you plan to write a BSc/MSc thesis based on the seminar?:
  • list of 3-4 favorite topics (numbers) sorted by decreasing preference:
  • remarks (optional): 

Contact

Prof. Dr. Martin SkutellaSebastian Schenker

List of papers

(in case you cannot access the papers via the corresp. link, write a message to )

  1. R. Duan and S. Pettie: Linear-Time Approximation for Maximum Weight Matching link
  2. J. Erickson: Maximum flows and parametric shortest paths in planar graphs link
  3. A. Gupta and A. Kumar: Greedy Algorithms for Steiner Forest link
  4. C. Ambühl, M. Mastrolilli, N. Mutsanas and O. Svensson: On the Approximability of Single-Machine Scheduling with Precedence Constraints link
  5. S. Chechik, D.H. Larkin, L. Roditty, G. Schoenebeck, R.E. Tarjan and V.V. Williams: Better Approximation Algorithms for the Graph Diameter link
  6. L. Bulteau, V. Froese and N. Talmon: Multi-player Diffusion Games on Graph Classes link
  7. C. Kalaitzis, O. Svensson and J. Tarnawski: Unrelated Machine Scheduling of Jobs with Uniform Smith Ratios link
  8. M.X. Goemans and T. Rothvoß: Polynomiality for Bin Packing with a Constant Number of Item Types link
  9. N. Boland, H. Charkhgard and M. Savelsbergh: The L-shape search method for triobjective integer programming link
  10. D. Adjiashvili, A. Baggio and R. Zenklusen: Firefighting on Trees Beyond Integrality Gaps link
  11. S. Fujishige, M. Goemans, T. Harks, B. Peis and R. Zenklusen: Matroids are Immune to Braess Paradox link
  12. B. Stevens and A. Williams: The Coolest Way to Generate Binary Strings link
  13. T. Dueholm Hansen and U. Zwick: Random-Edge is slower than Random-Facet on abstract cubes link
  14. N. Kayal, C. Saha and S. Tavenas: An almost Cubic Lower Bound for Depth Three Arithmetic Circuits link
  15. C. Demetrescu, G. F. Italiano: A New Approach to Dynamic All Pairs Shortest Paths link
  16. Special topics for BSc-students: A. Schrijver: Combinatorial Optimization, Chapters 15, 29, 41, 44, or 45.

Navigation

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe