I am a Professor in the Insitute of Computer Science at University of Bonn. Before, I was a Junior Professor in the Department of Computer Science at TU Dortmund, a postdoc at Max-Planck-Institut für Informatik and before that I was a postdoc in the Department of Computer Science of Cornell University, where I worked with Eva Tardos and Bobby Kleinberg. I graduated from RWTH Aachen University in 2012. My advisor was Berthold Vöcking.
In my research, I consider problems of approximation algorithms, online algorithms, and algorithmic game theory. My PhD thesis focussed on spectrum allocation problems in wireless networks with power control.
Contact
|
|
Publications
See also Google Scholar.- Multi-Agent Combinatorial Contracts
Paul Duetting, Tomer Ezra, Michal Feldman, Thomas Kesselheim
SODA 2025, accepted to appear
arXiv preprint - Sample Complexity of Posted Pricing for a Single Item
Billy Jin, Thomas Kesselheim, Will Ma, Sahil Singla
NeurIPS 2024, accepted to appear
arXiv preprint - Online Combinatorial Allocations and Auctions with Few Samples
Paul Dütting, Thomas Kesselheim, Brendan Lucier, Rebecca Reiffenhauser, Sahil Singla
FOCS 2024, accepted to appear
arXiv preprint - Approximating Optimum Online for Capacitated Resource Allocation
Alexander Braun, Thomas Kesselheim, Tristan Pollner, Amin Saberi
EC 2024
arXiv preprint - Supermodular Approximation of Norms and Applications
Thomas Kesselheim, Marco Molinaro, Sahil Singla
STOC 2024: 1841-1852
arXiv preprint - Bandit Algorithms for Prophet Inequality and Pandora's Box
Khashayar Gatmiry, Thomas Kesselheim, Sahil Singla, Yifan Wang
SODA 2024: 462-500
arXiv preprint - Multi-Agent Contracts
Paul Dütting, Tomer Ezra, Michal Feldman, Thomas Kesselheim
STOC 2023
arXiv preprint - Online and Bandit Algorithms Beyond ℓp Norms
Thomas Kesselheim, Marco Molinaro, Sahil Singla
SODA 2023
arXiv preprint - Simplified Prophet Inequalities for Combinatorial Auctions
Alexander Braun, Thomas Kesselheim
SOSA 2023
arXiv preprint - Asymptotically Optimal Welfare of Posted Pricing for Multiple Items with MHR Distributions
Alexander Braun, Matthias Buttkus, Thomas Kesselheim
ESA 2021: 22:1-22:16 - Combinatorial Contracts
Paul Dütting, Tomer Ezra, Michal Feldman, Thomas Kesselheim
FOCS 2021: 815-826
arXiv preprint - Truthful Mechanisms for Two-Sided Markets via Prophet Inequalities
Alexander Braun, Thomas Kesselheim
EC 2021: 202-203 - Improved Truthful Mechanisms for Subadditive Combinatorial Auctions: Breaking the Logarithmic Barrier
Sepehr Assadi, Thomas Kesselheim, Sahil Singla
SODA 2021: 653-661 - Online Learning with Vector Costs and Bandits with Knapsacks
Thomas Kesselheim, Sahil Singla
COLT 2020: 2286-2305 - An O(log log m) Prophet Inequality for Subadditive Combinatorial Auctions
Paul Dütting, Thomas Kesselheim, Brendan Lucier
FOCS 2020: 306-317 - Knapsack Secretary with Bursty Adversary
Thomas Kesselheim, Marco Molinaro
ICALP 2020: 72:1-72:15 - How to Hire Secretaries with Stochastic Departures
Thomas Kesselheim, Alexandros Psomas, Shai Vardi.
WINE 2019. - Posted Pricing and Prophet Inequalities with Inaccurate Priors
Paul Dütting and Thomas Kesselheim.
EC 2019: 111-129 - Price of Anarchy for Mechanisms with Risk-Averse Agents
Thomas Kesselheim, Bojana Kodric.
ICALP 2018: 155:1-155:14 - Prophet Secretary for Combinatorial Auctions and Matroids
Soheil Ehsani, MohammadTaghi Hajiaghayi, Thomas Kesselheim, Sahil Singla.
In Proc. of 29th ACM-SIAM Symposium on Discrete Algorithms (SODA 2018),
pp. 700-714 - Prophet Inequalities Made Easy: Stochastic Optimization by Pricing Non-Stochastic Inputs
Paul Dütting, Michal Feldman, Thomas Kesselheim, and Brendan Lucier.
In Proc. of 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS 2017),
Berkeley, CA, USA, 2017, pp. 540-551, arXiv preprint. - Submodular Secretary Problems: Cardinality, Matching, and Linear Constraints
Thomas Kesselheim and Andreas Tönnis.
In Proc. of APPROX 2017,
Berkeley, CA, USA, 2017, pp. 16:1-16:22, arXiv preprint
- Best-Response Dynamics in Combinatorial Auctions with Item Bidding
Paul Dütting and Thomas Kesselheim.
In Proc. of 28th ACM-SIAM Symposium on Discrete Algorithms (SODA 2017),
Barcelona, Spain, 2017, pp. 521-533, arXiv preprint
- Smoothness for Simultaneous Composition of Mechanisms with Admission
Martin Hoefer, Thomas Kesselheim, and Bojana Kodric.
In Proc. of the 12th Conference on Web and Internet Economics (WINE 2016)
Montréal, QC, Canada, 2016, pp. 294-308, arXiv preprint
- Think Eternally: Improved Algorithms for the Temp Secretary Problem and Extensions
Thomas Kesselheim and Andreas Tönnis.
In Proc. of the 24th European Symposium on Algorithms (ESA 2016),
Aarhus, Denmark, 2016, pp. 54:1-54:17, arXiv preprint
- Online Appointment Scheduling in the Random Order Model
Oliver Göbel, Thomas Kesselheim, and Andreas Tönnis.
In Proc. of the 23rd European Symposium on Algorithms (ESA 2015),
Patras, Greece, 2015, pp. 680-692, [PDF, full version]
- Algorithms against anarchy: Understanding non-truthful mechanisms
Paul Dütting and Thomas Kesselheim.
In Proc. of the 16th ACM Conference on Economics and Computation (EC 2015),
Portland, OR, USA, 2015, pp. 239-255. - Algorithms as mechanisms: The price of anarchy of relax-and-round
Paul Dütting, Thomas Kesselheim, and Eva Tardos.
In Proc. of the 16th ACM Conference on Economics and Computation (EC 2015),
Portland, OR, USA, 2015, pp. 187-201. - Smooth online mechanisms: A game-theoretic problem in renewable energy markets
Thomas Kesselheim, Robert Kleinberg, and Eva Tardos.
In Proc. of the 16th ACM Conference on Economics and Computation (EC 2015),
Portland, OR, USA, 2015, pp. 203-220. - Secretary Problems with Non-Uniform Arrival Order
Thomas Kesselheim, Robert Kleinberg, and Rad Niazadeh.
In Proc. of the 47th ACM Symposium on Theory of Computing (STOC 2015),
Portland, OR, USA, 2015, pp. 879-888. - Jamming-Resistant Learning in Wireless Networks
Johannes Dams, Martin Hoefer, and Thomas Kesselheim.
In Proc. of 41st International Colloquium on Automata, Languages and Programming (ICALP 2014),
Copenhagen, Denmark, 2014, pp. 447-458.
arXiv preprint arXiv:1307.5290 - Online Independent Set Beyond the Worst-Case: Secretaries, Prophets, and Periods
Oliver Göbel, Martin Hoefer, Thomas Kesselheim, Thomas Schleiden, and Berthold Vöcking.
In Proc. of 41st International Colloquium on Automata, Languages and Programming (ICALP 2014),
Copenhagen, Denmark, 2014, pp. 508-519.
arXiv preprint arXiv:1307.3192
(Best Paper Award, ICALP Track C) - Mechanisms with Unique Learnable Equilibria
Paul Dütting, Thomas Kesselheim, and Eva Tardos.
In Proc. of the 15th ACM Conference on Economics and Computation (EC 2014),
Palo Alto, CA, USA, 2014, pp. 877-894. - Primal Beats Dual on Online Packing LPs in the Random-Order Model
Thomas Kesselheim, Klaus Radke, Andreas Tönnis, and Berthold Vöcking.
In Proc. of the 46th ACM Symposium on Theory of Computing (STOC 2014),
New York, NY, USA, 2014, pp. 303-312.
arXiv preprint arXiv:1311.2578 - Sleeping Experts in Wireless Networks
Johannes Dams, Martin Hoefer, and Thomas Kesselheim.
In Proc. of the 27th International Symposium on Distributed Computing (DISC 2013),
Jerusalem, Israel, 2013, pp. 344-357. - An optimal online algorithm for weighted bipartite matching and extensions to combinatorial auctions
Thomas Kesselheim, Klaus Radke, Andreas Tönnis, and Berthold Vöcking.
In Proc. of the 21st European Symposium on Algorithms (ESA 2013),
Sophia Antipolis, France, 2013, pp. 589-600. [PDF, full version] - Truthfulness and Stochastic Dominance with Monetary Transfers
Martin Hoefer, Thomas Kesselheim, and Berthold Vöcking.
In Proc. of the 14th ACM Conference on Electronic Commerce (EC 2013),
Philadelphia, Pennsylvania, USA, 2013, pp. 567-582. - Approximation Algorithms for Wireless Link Scheduling with Flexible Data Rates
Thomas Kesselheim.
In Proc. of the 20th European Symposium on Algorithms (ESA 2012),
Ljubljana, Slovenia, pp. 659-670.
Preprint: CoRR abs/1205.1331 - Dynamic Packet Scheduling in Wireless Networks
Thomas Kesselheim.
In Proc. of 31st Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC 2012),
Madeira, Portugal, pp. 281-290.
Preprint CoRR abs/1203.1226 (2012) - Scheduling in Wireless Networks with Rayleigh-Fading Interference
Johannes Dams, Martin Hoefer, and Thomas Kesselheim.
In Proc. of the 24th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2012),
Pittsburgh, Pennsylvania, USA, 2012, pp. 327-335. - Secondary Spectrum Auctions for Symmetric and Submodular Bidders
Martin Hoefer, and Thomas Kesselheim.
In Proc. of the 13th ACM Conference on Electronic Commerce (EC 2012),
Valencia, Spain, 2012, pp. 657-671.
Preprint: CoRR abs/1110.5753: (2011) - Convergence Time of Power-Control Dynamics
Johannes Dams, Martin Hoefer, and Thomas Kesselheim.
In Proc. of 38th International Colloquium on Automata, Languages and Programming (ICALP 2011),
Zürich, Switzerland, 2011, pp. 637-649. [ DOI ], [PDF, full version] - Approximation Algorithms for Secondary Spectrum Auctions
Martin Hoefer, Thomas Kesselheim, and Berthold Vöcking.
In Proc. of 23rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2011),
San José, California, USA, 2011, pp. 177-186
Preprint: CoRR abs/1007.5032: (2010) - Transmission Probability Control Game with Limited Energy
Johannes Dams, Thomas Kesselheim, and Berthold Vöcking.
In Proc. of IEEE Symposium on New Frontiers in Dynamic Spectrum Access Networks (DySPAN), 2011,
Aachen, Germany, 2011, pp. 420-430 - A Constant-Factor Approximation for Wireless Capacity Maximization with Power Control in the SINR Model
Thomas Kesselheim
In Proc. of 22nd ACM-SIAM Symposium on Discrete Algorithms (SODA 2011),
San Francisco, California, USA, 2011, pp. 1549-1559
Preprint: CoRR abs/1007.1611: (2010) - Distributed Contention Resolution in Wireless Networks
Thomas Kesselheim, and Berthold Vöcking.
In Proc. of 24th International Symposium on Distributed Computing (DISC 2010),
Cambridge, Massachusetts, USA, 2010, p. 149-163 [PDF, full version]
- Oblivious Interference Scheduling
Alexander Fanghänel, Thomas Kesselheim, Harald Räcke, and Berthold Vöcking.
In Proc. of 28th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC 2009),
Calgary, Alberta, Canada, 2009, p. 220-229. [ DOI ], [PDF, full version] - Improved Algorithms for Latency Minimization in Wireless
Networks
Alexander Fanghänel, Thomas Kesselheim, and Berthold Vöcking.
In Proc. of 36th International Colloquium on Automata, Languages and Programming (ICALP 2009),
Rhodos, Greece, 2009, p. 447-458. [ DOI ], [PDF, full version]
(Best Paper Award, ICALP Track C)