Prof. Dr. Max Klimm

Technische Universität Berlin
Institut für Mathematik
Sekretariat MA 5-2
Straße des 17. Juni 136
10623 Berlin
Raum MA 502

Tel.: +49 - (0)30 - 314-29400

Email: klimm (at) tu-berlin.de
Sprechzeiten n.V.

Sekretariat MA 5-2
Dorothea Kiefer Raum MA 523

Tel.: +49 - (0)30 - 314-28641
Fax: +49 - (0)30 - 314-21117

Email: kiefer (at) math.tu-berlin.de

To appear

• Parametric Computation of Minimum Cost Flows with Piecewise Quadratic Costs
  (M. Klimm, P. Warode)
  Math. Oper. Res., to appear.
• Travelling on Graphs with Small Highway Dimension
  (Y. Disser, A.. E.. Feldmann, M. Klimm, J. Könemann)
  Algorithmica , to appear.

2020

• Hiring Secretaries over Time: The Benefit of Concurrent Employment
  (Y. Disser, J. Fearnley, M. Gairing, O. Göbel, M. Klimm, D. Schmand, A. Skopalik, A. Tönnis)
  Math. Oper. Res. 45(1): 323-352, 2020.
• Broadcasting a File in a Communication Network
  (K.-S. Goetzmann, T. Harks, M. Klimm)
  J. Sched. 23(2): 211-232, 2020.
  
• Complexity and Parametric Computation of Equilibria in Atomic Splittable Congestion Games via Weighted Graph Laplacians
  (M. Klimm, P. Warode)
  SODA 2020: 2728-2747.
• Packing Under Convex Quadratic Constraints
  (M. Klimm, M. E. Pfetsch, R. Raber, M. Skutella)
  IPCO 2020: 266-279.

2019

• Tight Bounds for Undirected Graph Exploration with Pebbles and Multiple Agents
  (Y. Disser, J. Hackfeld, M. Klimm)
  J. ACM 66(6): 40:1-40:41, 2019.
• Greedy Metric Minimum Online Matchings with Radom Arrivals
  (M. Garing, M. Klimm)
  Oper. Res. Lett. 47(2): 88-91, 2019.
• Distance-Preserving Graph Contractions
  (A. Bernstein, K. Däubel, Y. Disser, M. Klimm, T. Mütze, F. Smolny)
  SIAM J. Discret. Math 33(3): 1607-1636, 2019.
• Computing all Wardrop Equilibria Parametrized by the Flow Demand
  (M. Klimm, P. Warode)
  SODA 2019: 917-934.
  [extended version to appear in Math. Oper. Res.]
• Travelling on Graphs with Small Highway Dimension
  (Y. Disser, A. E. Feldmann, M. Klimm, J. Könemann)
  WG 2019: 175-189.
  [extended version to appear in Algorithmica]
• The Online Best Reply Algorithm for Resource Allocation Problems
  (M. Klimm, D. Schmand, A. Tönnis)
  SAGT 2019: 200-215.

2018

• Sensitivity Analysis for Convex Separable Optimization Over Integral Polymatroids
  (T. Harks, M. Klimm, B. Peis)
  SIAM J. Optim. 28(3): 2222-2245, 2018.
• Bottleneck Routing with Elastic Demands
  (T. Harks, M. Klimm, M. Schneider)
  Oper. Res. Lett. 46(1): 93-98, 2018.
• Demand-Independent Optimal Tolls
  (R. Colini-Baldeschi, M. Klimm, M. Scarsini)
  ICALP 2018: 151:1-151:14.
• Distance-Preserving Graph Contractions
  (A. Bernstein, K. Däubel, Y. Disser, M. Klimm, T. Mütze, F. Smolny)
  ITCS 2018: 51:1-51:14.
  [extended version in SIAM J. Discr. Math. 2019]

2017

• Packing a Knapsack of Unknown Capacity
  (Y. Disser, M. Klimm, N. Megow, S. Stiller)
  SIAM J. Discret. Math. 31(3): 1477-1497, 2017.
• Complexity and Approximation of the Continuous Network Design Problem
  (M. Gairing, T. Harks, M. Klimm)
  SIAM J. Optim. 27(3): 1554-1582, 2017.
• Impartial Selection and the Power of Up to Two Choices
  (A. Bjelde, F. A. Fischer, M. Klimm)
  ACM Trans. Economics and Comput. 5(4): 21:1-21:20, 2017.
• Brief Announcement: Approximation Algorithms for Unsplittable Resource Allocation Problems with Diseconomies of Scale
  (A. Bjelde, M. Klimm, D. Schmand)
  SPAA 2017: 227-229.

2016

• Congestion Games with Variable Demands
  (T. Harks, M. Klimm)
  Math. Oper. Res. 41(1):255-277, 2016.
• Undirected Graph Exploration with Θ(log log n) Pebbles
  (Y. Disser, J. Hackfeld, M. Klimm)
  SODA 2016: 25-30.
  [extended version in J. ACM 2019]
• Efficiency of Equilibria in Uniform Matroid Congestion Games
  (J. de Jong, M. Klimm, M. Uetz)
  SAGT 2016: 105-116.

2015

• Optimal Impartial Selection
  (F. A. Fischer, M. Klimm)
  SIAM J. Comput. 44(5): 1263-1285, 2015.
• Equilibria in a Class of Aggregative Location Games
  (T. Harks, M. Klimm)
  J. Math. Econ. 61:211-220.
  
• Computing Network Tolls with Support Constraints
  (T. Harks, I. Kleinert, M. Klimm, R. H. Möhring)
  Networks 65(3): 262-285, 2015.
• Improving the H_k-Bound on the Price of Stability in Undirected Shapley Network Design Games
  (Y. Disser, A. E. Feldmann, M. Klimm, M. Mihalak)
  Theor. Comput. Sci. 562: 557-564, 2015.
• Scheduling Bidirectional Traffic on a Path
  (Y. Disser, M. Klimm, El. Lübbecke)
  ICALP 2015 : 406-418.
• Impartial Selection and the Power of up to Two Choices
  (A. Bjelde, F. A. Fischer, M. Klimm)
  WINE 2015: 146-158.
  [extended version in ACM Trans. Economics and Comput. 2017]
• Bottleneck Routing with Elastic Demands
  (T. Harks, M. Klimm, M. Schneider)
  WINE 2015: 384-397.
  [extended version in Oper. Res. Lett. 2018]
• Linear, Exponential, but Nothing Else
  (M. Klimm)
  Gems of Combinatorial Optimization and Graph Algorithms (A. S. Schulz, M. Skutella, S. Stiller, D. Wagner, Eds.): 113-123, 2015.

2014

• Optimal Impartial Selection
  (F. A. Fischer, M. Klimm)
  EC 2014: 803-820.
  [extended version in SIAM J. Comput. 2015]
• Packing a Knapsack of Unknown Capacity
  (Y. Disser, M. Klimm, N. Megow, S. Stiller)
  STACS 2014: 276-287.
  [extended version in SIAM J. Discret. Math. 2017]
• Approximate Pure Nash Equilibria in Weighted Congestion Games
  (C. Hansknecht, M. Klimm, A. Skopalik)
  APPROX-RANDOM 2014: 242-257.
• Resource Competition on Integral Poymatroids
  (T. Harks, M. Klimm, B. Peis)
  WINE 2014: 189-202.
  [extended version in SIAM J. Optim. 2018]
• Congestion Games with Higher Demand Dimensions
  (M. Klimm, A. Schütz)
  WINE 2014: 453-459.
• Complexity and Approximation of the Continuous Network Design Problem
  (M. Gairing, T. Harks, M. Klimm)
  APPROX-RANDOM 2014: 226-241.
  [extended version in SIAM J. Optim. 2017]
• Multimarket Oligopolies with Restricted Market Access
  (T. Harks, M. Klimm)
  SAGT 2014: 182-193.

2013

• Computing Pure Nash and Strong Equilibria in Bottleneck Congestion Games
  (T. Harks, M. Hoefer, M. Klimm, A. Skopalik)
  Math. Program. 141(1-2): 193-215, 2013.
• Strong Equilibria in Games with the Lexicographical Improvement Property
  (T. Harks, M. Klimm, R. H. Möhring)
  Int. J. Game Theory 42(2): 461-482, 2013.
• Improving the H_k-Bound on the Price of Stability in Undirected Shapley Network Design Games
  (Y. Disser, A. E. Feldmann, M. Klimm, M. Mihalak)
  CIAC 2013: 158-169
  [extended version in Theor. Comput Sci. 2015]
• Congestion Games with Player-Specific Costs Revisitied
  (M. Gairing, M. Klimm)
  SAGT 2013 : 98-109
• Competition for Resources
  (M. Klimm)
  Operations Research Proceedings 2013: 249-254

2012

• On the Existence of Pure Nash Equilibria in Weighted Congestion Games
  (T. Harks, M. Klimm)
  Math. Oper. Res. 37(3): 419-436, 2012.
• Conflict-Free Vehicle Routing
  (E. Gawrilow, M. Klimm, R. H. Möhring, B. Stenzel)
  EURO J. Transp. Logist. 1(1-2): 87-111, 2012.

2011

• Characterizing the Existence of Potential Functions in Weighted Congestion Games
  (T. Harks, M. Klimm, R. H. Möhring)
  Theory Comput. Syst. 49(1): 46-70, 2011.
• Congestion Games with Variable Demands
  (T. Harks, M. Klimm)
  TARK 2011: 111-120.
  [extended version in Math. Oper. Res. 2016]
• Demand Allocation Games: Integrating Discrete and Continuous Strategy Spaces
  (T. Harks, M. Klimm)
  WINE 2011: 194-205.
  [extended version in J. Math. Econ. 2015]
• Optimal File Distribution in Peer-to-Peer Networks
  (K.-S. Goetzmann, T. Harks, M. Klimm, K. Mailler)
  ISAAC 2011: 210-219.
  [extended version in J. Sched. 2020]

2010

• On the Existence of Pure Nash Equilibria in Weighted Congestion Games
  (T. Harks, M. Klimm)
  ICALP 2010: 79-89.
  [extended version in Math. Oper. Res. 2012]
• Computing Pure Nash and Strong Equilibria in Bottleneck Congestion Games
  (T. Harks, M. Hoefer, M. Klimm, A. Skopalik)
  ESA 2010: 29-38
  [extended version in Math. Program. 2013]

2009

• Strong Nash Equilibria in Games with the Lexicigraphical Improvement Property
  (T. Harks, M. Klimm, R. H. Möhring)
  WINE 2009: 463-470.
  [extended version in Int. J. Game Theory 2013]
• Characterizing the Existence of Potential Functions in Weighted Congestion Games
  (T. Harks, M. Klimm, R. H. Möhring)
  SAGT 2009: 97-108.
  [extended version in Theory Comput. Syst. 2011]