Algorithms and Complexity Group

Lars Rohwedder


Christian-Albrechts-Platz 4, Raum 1009
Phone: +49 431 880-7522
Telefax: +49 431 880-7614

Email-Lars Rohwedder


  • Klaus Jansen, Lars Rohwedder: A note on the integrality gap of the configuration LP for restricted Santa Claus. Available as arxiv report 1807.03626.



  • Marin Bougeret, Klaus Jansen, Michael Poss, Lars Rohwedder: Approximation results for makespan minimization with budgeted uncertainty. To appear on WAOA 2019. Available as arxiv report 1905.08592.

  • Sebastian Berndt, Leah Epstein, Klaus Jansen, Asaf Levin, Marten Maack,  Lars Rohwedder: Online Bin Covering with Limited Migration. To appear on ESA 2019. Available as arxiv report 1904.06543

  • Klaus Jansen, Lars Rohwedder: Local search breaks 1.75 for Graph Balancing. ICALP 2019: 74:1-74:14. Available as arxiv report 1811.00955.

  • Klaus Jansen, Alexandra Lassota, Lars Rohwedder: Near-Linear Time Algorithm for n-fold ILPs via Color Coding. ICALP 2019: 75:1-75:13. Verfügbar als arxiv report 1811.00950.

  • Klaus Jansen, Lars Rohwedder: On Integer Programming and Convolution. ITCS 2019: 43:1-43:17. Available as arxiv report 1803.04744.

  • Klaus Jansen, Lars Rohwedder: Compact LP Relaxations for Allocation Problems. SOSA@SODA 2018: 11:1-11:19. Openly accessible at dagstuhl.

  • Klaus Jansen, Lars Rohwedder: A Quasi-Polynomial Approximation for the Restricted Assignment Problem. IPCO 2017: 305-316. Available as arxiv report 1701.07208.

  • Klaus Jansen, Lars Rohwedder: On the Configuration-LP of the Restricted Assignment Problem. SODA 2017: 2670-2678. Available as arxiv report 1611.01934.


From my master's thesis:

  • Klaus Jansen, Lars Rohwedder: Structured Instances of Restricted Assignment with Two Processing Times. CALDAM 2017: 230-241.