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
Co-Organisator einer Frühlingsschule für Masterandinnen und Doktorandinnen der Mathematik zum Thema "Diskret-kontinuierliche Optimierung am Beispiel von Versorgungsnetzwerken" (26.-30. April 2021)
Information Design for Bayesian Networks Math+ Projekt AA3-9, 1 Stelle, 36 Monate
Evolution Models for Historical Networks (seit 04/2021) Math+ Projekt EF5-6, 1 Stelle, 36 Monate, mit Guillaume Sagnol
Tropical Mechanism Design (seit 10/2019) Math+ Projekt AA3-5, 1 Stelle, 36 Monate, mit Michael Joswig
Flow-Preserving Graph Contractions with Applications to Logistics Networks (seit 01/2019) Math+ Projekt AA3-4, 1 Stelle, 36 Monate, mit Torsten Mütze, Guillaume Sagnol und Martin Skutella
Combinatorial Network Flow Methods for Instationary Gas Flows and Gas Market Problems DFG Projekt im TRR 154, 36 Monate, mit Marc Pfetsch und Martin Skutella
Abgeschlossene Projekte
LogiScale - BigData in Logistics: Multiscale and Combinatorial Optimization Methods (2016-2019) EU EFRE Projekt, 2 Stellen, 36 Monate, mit Yann Disser und Martin Skutella
Competitive Exploration of Large Networks (2014-2017) Projekt im SPP "Algorithms for Big Data", 1 Stelle, 36 Monate, mit Yann Disser
Optimization under Informational and Strategic Uncertainty (2015-2016) Einstein International Postdoctoral Fellowship, 1 Stelle, 36 Monate (endete vorzeitig wegen Wechsels an die HU Berlin)
Network and Mechanism Design for Metropolitan Infrastructures (2014-2017) ECMath Projekt, 1 Stelle, 36 Monate
Publikationen
Zur Veröffentlichung Angenommen
Parametric Computation of Minimum Cost Flows with Piecewise Quadratic Costs (M. Klimm, P. Warode) Mathematics of Operations Research, 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) Mathematics of Operations Research 45(1): 323-352, 2020. [pdf]
Broadcasting a File in a Communication Network (K.-S. Goetzmann, T. Harks, M. Klimm) Journal of Scheduling 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 (Proceedings of the 31st Symposium on Discrete Algorithms): 2728-2747, 2020.
Packing Under Convex Quadratic Constraints (M. Klimm, M. E. Pfetsch, R. Raber, M. Skutella) IPCO (Proceedings of the 21st Conference on Integer Programming and Combinatorial Optimization): 266-279, 2020.
SAGT 2020 (T. Harks, M. Klimm, Eds.) Proceedings of the 13 International Symposium on Algorithmic Game Theory, Springer, 2020. [doi: 10.1007/978-3-030-57980-7]
2019
Tight Bounds for Undirected Graph Exploration with Pebbles and Multiple Agents (Y. Disser, J. Hackfeld, M. Klimm) Journal of the 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 Journal on Discrete Mathematics 33(3): 1607-1636, 2019
Computing all Wardrop Equilibria Parametrized by the Flow Demand (M. Klimm, P. Warode) SODA (Proceedings of the 30th Symposium on Discrete Algorithms) 917-934, 2019. [erweiterte Version in Math. Oper. Res. zur Veröffentlichung angenommen]
Travelling on Graphs with Small Highway Dimension (Y. Disser, A. E. Feldmann, M. Klimm, J. Könemann) WG (Proceedings of the 45th International Workshop on Graph-Theoretic Concepts in Computer Science) 175-189, 2019. [erweiterte Version in Algorithmica zur Veröffentlichung angenommen]
The Online Best Reply Algorithm for Resource Allocation Problems (M. Klimm, D. Schmand, A. Tönnis) SAGT (Proceedings 12th International Symposium on Algorithmic Game Theory): 200-215, 2019.
2018
Sensitivity Analysis for Convex Separable Optimization Over Integral Polymatroids (T. Harks, M. Klimm, B. Peis) SIAM Journal on Optimization 28(3): 2222-2245, 2018.
Bottleneck Routing with Elastic Demands (T. Harks, M. Klimm, M. Schneider) Operations Research Letters 46(1): 93-98, 2018.
Demand-Independent Optimal Tolls (R. Colini-Baldeschi, M. Klimm, M. Scarsini) ICALP (Proceedings of the 45th International Colloquium on Automata, Languagtes and Programming) 151:1-151:14, 2018.
Distance-Preserving Graph Contractions (A. Bernstein, K. Däubel, Y. Disser, M. Klimm, T. Mütze, F. Smolny) ITCS (Proceedings of the 9th Innovations in Theoretical Computer Science Conference): 51:1-51:14, 2018. [erweiterte Version in SIAM J. Discr. Math. 2019]
2017
Packing a Knapsack of Unknown Capacity (Y. Disser, M. Klimm, N. Megow, S. Stiller) SIAM Journal on Discrete Mathematics 31(3): 1477-1497, 2017. [pdf]
Complexity and Approximation of the Continuous Network Design Problem (M. Gairing, T. Harks, M. Klimm) SIAM Journal on Optimization 27(3): 1554-1582, 2017.
Impartial Selection and the Power of Up to Two Choices (A. Bjelde, F. A. Fischer, M. Klimm) ACM Transactions on Economics and Computation 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 (Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures): 227-229, 2017.
2016
Congestion Games with Variable Demands (T. Harks, M. Klimm) Mathematics of Operations Research 41(1): 255-277, 2016.
Undirected Graph Exploration with ⊝(log log n) Pebbles (Y. Disser, J. Hackfeld, M. Klimm) SODA (Proceedings of the 27th Symposium on Discrete Algorithms): 25-39, 2016.
Efficiency of Equilibria in Uniform Matroid Congestion Games (J. de Jong, M. Klimm, M. Uetz) SAGT (Proceedings of the 9th International Symposium on Algorithmic Game Theory): 105-116, 2016.
2015
Optimal Impartial Selection (F. A. Fischer, M. Klimm) SIAM Journal on Computing 44(5): 1263-1285, 2015.
Equilibria in a Class of Aggregative Location Games (T. Harks, M. Klimm) Journal of Mathematical Economics 61: 211-220, 2015.
Computing Network Tolls with Support Constraints (T. Harks, I. Kleinert, M. Klimm, R. H. Möhring) Networks 65(3): 262-285, 2015.
Improving the Hk-Bound on the Price of Stability in Undirected Shapley Network Design Games (Y. Disser, A. E. Feldmann, M. Mihalak) Theoretical Computer Science 562: 557-564, 2015.
Scheduling Bidirectional Traffic on a Path (Y. Disser, M. Klimm, E. Lübbecke) ICALP (Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming): 406-418, 2015.
Impartial Selection and the Power of Up to Two Choices (A. Bjelde, F. A. Fischer, M. Klimm) WINE (Proceedings of the 11th International Conference on Web and Internet Economics): 146-158, 2015. [erweiterte Version in ACM Trans. Economics and Comput. 2017]
Bottleneck Routing with Elastic Demands (T. Harks, M. Klimm, M. Schneider) WINE (Proceedings of the 11th International Conference on Web and Internet Economics): 384-397, 2015. [erweiterte Version in Oper. Res. Lett. 2018]
Linear, Exponential, but Nothing Else (M. Klimm) In Gems of Combinatorial Optimization and Graph Algorithms (A. S. Schulz, M. Skutella, S. Stiller, D. Wagner, Eds.): 113-123, 2015.
2014
Optimal Impartial Selction (F. A. Fischer, M. Klimm) EC (Proceedings of the 15th Conference on Economics and Computation): 803-820, 2014. [erweiterte Version in SIAM. J. Comput. 2015]
Packing a Knapsack with Unknown Capacity (Y. Disser, M. Klimm, N. Megow, S. Stiller) STACS (Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science): 276-287, 2014. [erweiterte Version in SIAM J. Discret. Math. 2017]
Complexity and Approximation of the Continuous Network Design Problem (M. Gairing, T. Harks, M. Klimm) APPROX (Proceedings of the 17th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems): 2226-241, 2014. [erweiterte Version in SIAM J. Optim. 2018]
Approximate Pure Nash Equilibria in Weighted Congestion Games (C. Hansknecht, M. Klimm, A. Skopalik) APPROX (Proceedings of the 17th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems): 242-257, 2014.
Resource Competition on Integral Polymatroids (T. Harks, M. Klimm, B. Peis) WINE (Proceedings of the 10th Workshop on Internet and Network Economics): 189-202, 2014. [erweiterte Version in SIAM J. Optim. 2018]
Congestion Games with Higer Demand Dimensions (M. Klimm, A. Schütz) WINE (Proceedings of the 10th Workshop on Internet and Network Economics): 453-459, 2014.
2013
Computing Pure Nash and Strong Equilibria in Bottleneck Congestion Games (T. Harks, M. Hoefer, M. Klimm, A. Skopalik) Mathematical Programming 141(1-2): 193-215, 2013.
Strong Equilibria in Games with the Lexicographical Improvement Property (T. Harks, M. KLimm, R. H. Möhring) International Journal on Game Theory 42(2): 461-482, 2013.
Improving the Hk-Bound in the Price of Stability in Undirected Shapley Network Design Games (Y. Disser, A. E. Feldmann, M. Mihalak) CIAC (Proceedings of the 8th International Conference on Algorithms and Complexity): 158-169, 2013.
Congestion Games with Player-Specific Costs Revisited (M. Gairing, M. Klimm) SAGT (Proceedings of the 6th International Symposium on Algorithmic Game Theory): 98-109, 2013.
Competition for Resources (M. Klimm) Operations Research Proceedings: 249, 254, 2013.
2012
On the Existence of Pure Nash Equilibria in Weighted Congestion Games (T. Harks, M. Klimm) Mathematics of Operations Research 37(3): 419-436, 2012 [pdf]
Conflict-Free Vehicle Routing (E. Gawrilow, M. Klimm, R. H. Möhring, B. Stenzel) EURO Journal on Transpation and Logistics 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 of Computing Systems 49(1): 46-70, 2011
Congestion Games with Variable Demands (T. Harks, M. Klimm) TARK (Proceedings of the 13th Conference on Theoretical Aspects of Rationality and Knowledge): 111-120, 2011 [erweiterte Version in Math. Oper. Res. 2016]
Demand Allocation Games: Integrating Discrete and Continuous Strategy Spaces (T. Harks, M. Klimm) WINE (Proceedings of the 11th International Workshop on Internet and Network Economics): 194-205, 2011 [erweiterte Version in J. Math. Econ. 2015]
Optimal File Distribution in Peer-to-Peer Networks (K.-S. Goetzmann, T. Harks, M. Klimm, K. Miller) ISAAC (Proceedings of the 22nd International Symposium on Algorithms and Computation): 210-219, 2011 [erweiterte Version in J. Sched. 2020]
2010
On the Existence of Pure Nash Equilibria in Weighted Congestion Games (T. Harks, M. Klimm) ICALP (Proceedings of the 37th International Symposium on Algorithms, Languages and Programming): 79-89, 2010. [erweiterte 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 (Proceedings of the 18th Annual Euopean Symposium on Algorithms): 29-38, 2010. [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 (Proceedings of the 5th International Workshop on Internet and Network Economics): 463-470, 2009. [erweiterte 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 (Proceedings of the 2nd International Symposium on Algorithmic Game Theory): 97-108, 2009. [erweiterete Version in Theory Comput. Syst. 2011]