Faculties
DE/ EN

## Prof. Dr. Max Klimm

Fakultät II - Mathematik und Naturwissenschaften
Institut für Mathematik, Sekr. MA 5-2
Technische Universität Berlin
Straße des 17. Juni 136
10623 Berlin

Office: MA 502
Telephone: +49 30 314 29400
Email: (lastname)@math.tu-berlin.de

### Publications

#### to appear

• On the Robustness of Potential-Based Flow Networks (, , and )
Mathematical Programming, .
• Equilibria in Multi-Class and Multi-Dimensional Atomic Congestion Games ( and )
Mathematics of Operations Research, .
• Competitive Algorithms for Symmetric Rendezvous on the Line (, , and )
SODA 2022 – Proc. 33rd ACM-SIAM Symposium on Discrete Algorithms.
• Multi-Leader Congestion Games with an Adversary (, , , and )
AAAI 2022 – Proc. 36th Conference on Artificial Intelligence.

#### 2021

• Parametric Computation of Minimum Cost Flows with Piecewise Quadratic Costs ( and )
Mathematics of Operations Research, .
• Packing Under Convex Quadratic Constraints (, , and )
Mathematical Programming, .
• Pure Nash Equilibria in Resource Graph Games (, and )
Journal of Artificial Intelligence Research, 72:185–213, .
• Travelling on Graphs with Small Highway Dimension (, , and )
Algorithmica, 83(5):1352–1370, .
• Fractionally Subadditive Maximization under an Incremental Knapsack Constraint (, and )
WAOA 2021 – Proc. 19th Workshop on Approximation and Online Algorithms.

#### 2020

• Hiring Secretaries over Time: The Benefit of Concurrent Employment (, , , , , , and )
Mathematics of Operations Research, 45(1):323–352, .
• Broadcasting a File in a Communication Network (, and )
Journal of Scheduling, 23(2):211–232, .
• Complexity and Parametric Computation of Equilibria in Atomic Splittable Congestion Games via Weighted Block Laplacians ( and )
SODA 2020 – Proc. 31st ACM-SIAM Symposium on Discrete Algorithms, pp. 2728–2747.
[doi]
• Packing Under Convex Quadratic Constraints (, , and )
IPCO 2020 – Proc. 21st Conference on Integer Programming and Combinatorial Optimization, pp. 266–279.
[doi]
Extended version appeared in Math. Program. 2021
• SAGT 2020 – Proc. 13th International Symposium on Algorithmic Game Theory (Harks T, Klimm M, eds.), Springer, . [doi]
• Nobel, Milgrom und Wilson ()
Chapter in Mitteilungen der Deutschen Mathematiker-Vereinigung, .
[doi]

#### 2019

• Tight Bounds for Undirected Graph Exploration with Pebbles and Multiple Agents (, and )
Journal of the ACM, 66(6):40:1–40:41, .
• Distance-Preserving Graph Contractions (, , , , and )
SIAM Journal on Discrete Mathematics, 33(3):1607–1636, .
[doi]
• Greedy Metric Minimum Online Matchings with Random Arrivals ( and )
Operations Research Letters, 47(2):88–91, .
[doi]
• Computing all Wardrop Equilibria parametrized by the Flow Demand ( and )
SODA 2019 – Proc. 30th ACM-SIAM Symposium on Discrete Algorithms, pp. 917–934.
[doi]
Extended version "Parametric Computation of Minimum Cost Flows with Piecewise Quadratic Costs" appeared in Math. Oper Res. 2021
• Travelling on Graphs with Small Highway Dimension (, , and )
WG 2019 – Proc. 45th Workshop on Graph-Theoretic Concepts in Computer Science, pp. 175–189.
[doi]
Extended version appeared in Algorithmica 2021
• The Online Best Reply Algorithm for Resource Allocation Problems (, and )
SAGT 2019 – Proc. 12th International Symposium on Algorithmic Game Theory, pp. 200–215.
[doi]

#### 2018

• Sensitivity Analysis for Convex Separable Optimization Over Integral Polymatroids (, and )
SIAM Journal on Optimization, 28(3):2222–2245, .
[doi]
• Bottleneck Routing with Elastic Demands (, and )
Operations Research Letters, 46(1):93–98, .
[doi]
• Demand-Independent Optimal Tolls (, and )
ICALP 2018 – Proc. 45th International Colloquium on Automata, Languages and Programming, pp. 151:1–151:14.
[doi]
• Distance-Preserving Graph Contractions (, , , , and )
ITCS 2018 – Proc. 9th Innovations in Computer Science Conference, pp. 51:1–51:14.
[doi]
Extended version appeared in SIAM. J. Discr. Math. 2019

#### 2017

• Complexity and Approximation of the Continuous Network Design Problem (, and )
SIAM Journal on Optimization, 27(3):1554–1582, .
[doi]
• Packing a Knapsack of Unknown Capacity (, , and )
SIAM Journal on Discrete Mathematics, 31(3):1477–1497, .
[doi]
• Impartial Selection and the Power of Up to Two Choices (, and )
ACM Transactions on Economics and Computation, 5(4):21:1–21:20, .
[doi]
• Brief Announcement: Approximation Algorithms for Unsplittable Resource Allocation Problems with Diseconomies of Scale (, and )
SPAA 2017 – Proc. 29th ACM Symposium on Parallelism in Algorithms and Architectures, pp. 227–229.
[doi]

#### 2016

• Congestion Games with Variable Demands ( and )
Mathematics of Operations Research, 41(1):255–277, .
[doi]
• Undirected Graph Exploration with \ensuremath\Theta(log log n) Pebbles (, and )
SODA 2016 – Proc. 27th ACM-SIAM Symposium on Discrete Algorithms, pp. 25–39.
[doi]
Extended version "Tight Bounds for Undirected Graph Exploration with Pebbles and Multiple Agents" appeared in J. ACM 2019
• Efficiency of Equilibria in Uniform Matroid Congestion Games (, and )
SAGT 2016 – Proc. 9th International Symposium on Algorithmic Game Theory, pp. 105–116.
[doi]

#### 2015

• Optimal Impartial Selection ( and )
SIAM Journal on Computing, 44(5):1263–1285, .
[doi]
• Equilibria in a Class of Aggregative Location Games ( and )
Journal of Mathematical Economics, 61(1):211–220, .
[doi]
• Computing Network Tolls with Support Constraints (, , and )
Networks, 65(3):262–285, .
[doi]
• Improving the Hk-Bound on the Price of Stability in Undirected Shapley Network Design Games (, , and )
Theoretical Computer Science, 562:557–564, .
[doi]
• Scheduling Bidirectional Traffic on a Path (, and )
ICALP 2015 – Proc. 42nd International Colloquium on Automata, Languages and Programming, pp. 406–418.
[doi]
• Impartial Selection and the Power of up to Two Choices (, and )
WINE 2015 – Proc. 11th Conference on Web and Internet Economics, pp. 146–158.
[doi]
Extended version appeared in ACM Trans. Econ. Comput. 2017
• Sharing Non-anonymous Costs of Multiple Resources Optimally ( and )
CIAC 2015 – Proc. 9th International Conference on Algorithms and Complexity, pp. 274–287.
[doi]
• Bottleneck Routing with Elastic Demands (, and )
WINE 2015 – Proc. 11th Conference on Web and Internet Economics, pp. 384–397.
[doi]
Extended version appeared in Oper. Res. Lett. 2018
• Linear, Exponential, but Nothing Else ()
Chapter in Gems of Combinatorial Optimization and Graph Algorithms (Schulz AS, Skutella M, Stiller S, Wagner D, eds.), Springer, .
[doi]

#### 2014

• Optimal Impartial Selection ( and )
EC 2014 – Proc. 15th ACM Conference on Economics and Computation, pp. 803–820.
[doi]
Extended version appeared in SIAM J. Comput. 2015
• Packing a Knapsack of Unknown Capacity (, , and )
STACS 2014 – Proc. 31st International Symposium on Theoretical Aspects of Computer Science, pp. 276–287.
[doi]
Extended version appeared in SIAM J. Disc. Math. 2017
• Approximate Pure Nash Equilibria in Weighted Congestion Games (, and )
APPROX 2014 – Proc. 17th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, pp. 242–257.
[doi]
• Complexity and Approximation of the Continuous Network Design Problem (, and )
APPROX 2014 – Proc. 17th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, pp. 226–241.
[doi]
Extended version appeared in SIAM J. Optim. 2017
• Congestion Games with Higher Demand Dimensions ( and )
WINE 2014 – Proc. 10th Conference on Web and Internet Economics, pp. 453–459.
[doi]
Extended version "Equilibria in Multi-Class and Multi-Dimensional Atomic Congestion Games" to appear in Math. Oper. Res.
• Multimarket Oligopolies with Restricted Market Access ( and )
SAGT 2014 – Proc. 7th International Symposium on Algorithmic Game Theory, pp. 182–193.
[doi]
• Resource Competition on Integral Polymatroids (, and )
WINE 2014 – Proc. 10th Conference on Web and Internet Economics, pp. 189–202.
[doi]
Extended version "Senstitivity Analysis of Convex Separable Optimization Over Integral Polymatroids" appeared in SIAM J. Optim. 2018

#### 2013

• Computing Pure Nash and Strong Equilibria in Bottleneck Congestion Games (, , and )
Mathematical Programming, 141(1-2):193–215, .
[doi]
• Strong Equilibria in Games with the Lexicographical Improvement Property (, and )
International Journal of Game Theory, 42(2):461–482, .
[doi]
• Improving the Hk-Bound on the Price of Stability in Undirected Shapley Network Design Games (, , and )
CIAC 2013 – Proc. 8th International Conference on Algorithms and Complexity, pp. 158–169.
[doi]
Extended version appeared in Theor. Comput Sci. 2015
• Congestion Games with Player-Specific Costs Revisited ( and )
SAGT 2013 – Proc. 6th International Symposium on Algorithmic Game Theory, pp. 98–109.
[doi]

#### 2012

• On the Existence of Pure Nash Equilibria in Weighted Congestion Games ( and )
Mathematics of Operations Research, 37(3):419–436, .
[doi]
• Conflict-Free Vehicle Routing (, , and )
EURO Journal on Transportation and Logistics, 1(1-2):87–111, .
[doi]

#### 2011

• Characterizing the Existence of Potential Functions in Weighted Congestion Games (, and )
Theory of Computing Systems, 49(1):46–70, .
[doi]
• Congestion Games with Variable Demands ( and )
TARK 2011 – Proc. 13th Conference on Theoretical Aspects of Rationality and Knowledge, pp. 111–120.
[doi]
Extended version appeared in Math. Oper. Res. 2016
• Optimal File Distribution in Peer-to-Peer Networks (, , and )
ISAAC 2011 – Proc. 22nd International Symposium on Algorithms and Computation, pp. 210–219.
[doi]
Extended version "Broadcasting a File in a Communication Network" appeared in J. Sched. 2020
• Demand Allocation Games: Integrating Discrete and Continuous Strategy Spaces ( and )
WINE 2011 – Proc. 7th Conference on Web and Internet Economics, pp. 194–205.
[doi]

#### 2010

• On the Existence of Pure Nash Equilibria in Weighted Congestion Games ( and )
ICALP 2010 – Proc. 37th International Colloquium on Automata, Languages and Programming, pp. 79–89.
[doi]
Extended version appeared in Math. Oper. Res. 2012
• Computing Pure Nash and Strong Equilibria in Bottleneck Congestion Games (, , and )
ESA 2010 – Proc. 18th European Symposium on Algorithms, pp. 29–38.
[doi]
Extended version appeared in Math. Program. 2013

#### 2009

• Strong Nash Equilibria in Games with the Lexicographical Improvement Property (, and )
WINE 2009 – Proc. 5th Conference on Web and Internet Economics, pp. 463–470.
[doi]
Extended version "Strong equilibria in games with the lexicographical improvement property" appeared in Int. J. Game Theory 2013
• Characterizing the Existence of Potential Functions in Weighted Congestion Games (, and )
SAGT 2009 – Proc. 2nd International Symposium on Algorithmic Game Theory, pp. 97–108.
[doi]
Extended version appeared in Theory Comput. Syst. 2011