Patrick Briest
	Address: 4141 Upson Hall Dept. of Computer Science Cornell University Ithaca, NY 14853 eMail: pbriestcs.cornell.edu Phone: +1 (607) 255-4107

Research Interests: Approximation Algorithms, Online Algorithms, Algorithmic Game Theory, Mechanism Design, Computational Complexity.

Currently employed on a postdoctoral scholarship by the German Academic Exchange Service (DAAD).

Publications

• Uniform Budgets and the Envy-Free Pricing Problem.
  In Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP), Reykjavik, 2008.
  Preliminary version available as ECCC technical report TR06-150.
  © [ps]  [pdf] 
   
  
• Approximate Equilibria in Games with Few Players.
  (Joint work with Paul W. Goldberg and Heiko Röglin.)
  Technical report arXiv:0804.4524, 2008.
   
  
• On the Approximability of Combinatorial Exchange Problems.
  (Joint work with Moshe Babaioff and Piotr Krysta.)
  In Proceedings of the 1st International Symposium on Algorithmic Game Theory (SAGT), Paderborn, 2008.
  Proceedings version available at "http://www.springerlink.com/". 
  © [ps]  [pdf] 
   
  
• Stackelberg Network Pricing Games.
  (Joint work with Martin Hoefer and Piotr Krysta.)
  In Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science (STACS), Bordeaux, 2008.
  Preliminary version available as ECCC technical report TR07-101.
  Proceedings version available via the Dagstuhl Research Online Publication Server DROPS.
   
  
• Who Should Pay for Forwarding Packets?
  (Joint work with Heiner Ackermann, Alexander Fanghänel, and Berthold Vöcking.)
  In Proceedings of the 3rd International Workshop on Internet and Network Economics (WINE), San Diego, 2007.
  Proceedings version available at "http://www.springerlink.com/". 
   
  
• Buying Cheap is Expensive: Hardness of Non-Parametric Multi-Product Pricing.
  (Joint work with Piotr Krysta.)
  In Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA), New Orleans, 2007.
  Preliminary version available as ECCC technical report TR06-068.
  © [ps]  [pdf] 
   
  
• Energy-Efficient Broadcast Scheduling for Speed-Controlled Transmission Channels.
  (Joint work with Christian Gunia.)
  In Proceedings of the 17th International Symposium on Algorithms and Computation (ISAAC), Kolkata, 2006.
  Proceedings version available at "http://www.springerlink.com/". 
  © [ps]  [pdf] 
   
  
• Single-Minded Unlimited Supply Pricing on Sparse Instances.
  (Joint work with Piotr Krysta.)
  In Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms (SODA), Miami, 2006.
  © [ps]  [pdf] 
   
  
• Approximation Techniques for Utilitarian Mechanism Design.
  (Joint work with Piotr Krysta and Berthold Vöcking.)
  In Proceedings of the 37th ACM Symposium on Theory of Computing (STOC), Baltimore, 2005.
  © [ps]  [pdf] 
   
  
• The Ising Model: Simple Evolutionary Algorithms as Adaptation Schemes.
  (Joint work with Dimo Brockhoff, Bastian Degener, Matthias Englert, Christian Gunia, Oliver Heering, Thomas Jansen, Michael Leifhelm, Kai Plociennik, Heiko Röglin, Andrea Schweer, Dirk Sudholt, Stefan Tannenbaum, and Ingo Wegener.)
  In Proceedings of the 8th International Conference on Parallel Problem Solving from Nature (PPSN), Birmingham, 2004.
  Proceedings version available at "http://www.springerlink.com/". 
   
  
• Experimental Supplements to the Theoretical Analysis of EAs on Problems from Combinatorial Optimization.
  (Joint work with Dimo Brockhoff, Bastian Degener, Matthias Englert, Christian Gunia, Oliver Heering, Thomas Jansen, Michael Leifhelm, Kai Plociennik, Heiko Röglin, Andrea Schweer, Dirk Sudholt, Stefan Tannenbaum, and Ingo Wegener.)
  In Proceedings of the 8th International Conference on Parallel Problem Solving from Nature (PPSN), Birmingham, 2004.
  Proceedings version available at "http://www.springerlink.com". 
   
  

Theses

• Computational Aspects of Combinatorial Pricing Problems.
  PhD Thesis, University of Dortmund (2007).
  Available online through Eldorado.
   
  Abstracts of this thesis in German have appeared as Algorithmische und Komplexitätstheoretische Aspekte Kombinatorischer Preisoptimierung in Ausgezeichnete Informatikdissertationen 2007, GI Lecture Notes in Informatics, 2008, and it - Information Technology, 51(1), pp. 62-65, 2009.
   
  
• Frugality and Truthfulness in Approximate Mechanism Design.
  Diploma Thesis, University of Dortmund (2004).
  © [ps]  [pdf] 
   
  

© Copyright Notice

The documents distributed by this server have been provided by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a noncommercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.