Thomas Kesselheim

I am a postdoc fellow in the Department of Computer Science of Cornell University, where I work 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 and algorithmic game theory, which are mostly motivated by communication networks. In particular, my PhD thesis focussed on spectrum allocation problems in wireless networks with power control.

Contact

E-Mail: kesselheim (at) cs (dot) cornell (dot) edu Office: 488 Rhodes Hall Department of Computer Science Cornell University Ithaca, NY 14853

Publications

See also Google Scholar.

• 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, to appear
• 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)

Theses

• PhD Thesis (RWTH Aachen University, 2012): Approximation Algorithms for Spectrum Allocation and Power Control in Wireless Networks [PDF]
• Diploma Thesis (RWTH Aachen University, 2009): Packet Scheduling with Interference [PDF]
  

Teaching Assistance

• Summer 2012: Proseminar Network Algorithms
• Winter 2011/12: Proseminar Online Algorithms
• Summer 2011: Seminar Advanced Algorithms
• Winter 2010/11: Seminar Contention-Resolution Algorithms
• Summer 2010: Proseminar Randomized Algorithms
• Winter 2009/10: Lecture Berechenbarkeit und Komplexität
• Summer 2009: Seminar Algorithms for Wireless Networks

© 2013 Thomas Kesselheim, contact information: see above. Posted preliminary papers are for personal use. Not for redistribution. The definitive version was published in the respectively mentioned conference proceedings or journal.