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.

I include links to on-line papers and software, when appropriate, to ensure timely dissemination on a noncommercial basis. Technical reports are most likely to be available on-line. 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 the copyrights. These works may not be reposted without the explicit permission of the copyright holder.

2010

• Kshipra Bhawalkar , Martin Gairing , Tim Roughgarden
  Weighted Congestion Games: Price of Anarchy, Universal Worst-Case Examples, and Tightness
  Proc. of the 18th Annual European Symposium on Algorithms (ESA 2010),Part II, LNCS 6347, pp. 17-28, 2010.
  [PDF]
• Martin Gairing , Thomas Lücking , Marios Mavronicolas , Burkhard Monien
  Computing Nash Equilibria for Scheduling on Restricted Parallel Links
  Theory of Computing Systems, 47 (2), pp. 405-432, 2010.
  [PDF]
• Tobias Friedrich , Martin Gairing , Thomas Sauerwald
  Quasirandom Load Balancing
  Proc. of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010), pp. 1620-1629, 2010.
  [PDF]

2009

• Martin Gairing
  Covering Games: Approximation Through Non-Cooperation
  Proc. of the 5th Workshop on Internet and Network Economics
  (WINE 2009), LNCS 5929, pp. 184-195, 2009.
  (c) Springer Verlag
  [PDF]

2008

• Martin Gairing
  Malicious Bayesian Congestion Games
  Proc. of the 6th Workshop on Approximation and Online Algorithms
  (WAOA 2008), LNCS 5426, pp. 119-132, 2009.
  (c) Springer Verlag
  [PDF]
• Martin Gairing , Thomas Lücking , Marios Mavronicolas , Burkhard Monien , Manuel Rode
  Nash Equilibria in Discrete Routing Games with Convex Latency Functions
  Journal of Computer and System Sciences, 74, pp. 1199-1225, 2008.
  [PDF]
• Martin Gairing , Burkhard Monien , Karsten Tiemann
  Selfish Routing with Incomplete Information
  Theory of Computing Systems, 42(1), pp. 91-130, 2008.
  [PDF]

2007

• Martin Gairing , Florian Schoppmann
  Total Latency in Singleton Congestion Games
  Proc. of the 3rd Workshop on Internet and Network Economics
  (WINE 2007), LNCS 4858, pp. 381-387, 2007.
  (c) Springer Verlag
  [PDF]
• Martin Gairing , Burkhard Monien , Andreas Woclaw
  A Faster Combinatorial Approximation Algorithm for Scheduling Unrelated Parallel Machines
  Theoretical Computer Science, 380, pp. 87-99, 2007.
  [PDF]

2006

• Martin Gairing
  Selfish Routing in Networks
  PhD thesis, University of Paderborn, 2006
  [PDF]
• Dominic Dumrauf , Martin Gairing
  Price of Anarchy for Polynomial Wardrop Games
  Proc. of the 2nd Workshop on Internet and Network Economics
  (WINE 2006), LNCS 4286, pp. 319-330, 2006.
  (c) Springer Verlag
  [PDF]
• Martin Gairing , Thomas Lücking , Marios Mavronicolas , Burkhard Monien
  The Price of Anarchy for Polynomial Social Cost
  Theoretical Computer Science, 369, pp. 116-135, 2006.
  [PDF]
• Martin Gairing , Burkhard Monien , Karsten Tiemann
  Routing (Un-) Splittable Flow in Games with Player-Specific Linear Latency Functions
  Proc. of the 33rd International Colloquium on Automata, Languages and Programming
  (ICALP 2006), LNCS 4051, pp. 501-512, 2006.
  (c) Springer Verlag
  [PDF]
• Martin Gairing , Thomas Lücking , Marios Mavronicolas , Burkhard Monien
  The Price of Anarchy for Restricted Parallel Links
  Parallel Processing Letters (PPL), 16(1), pp. 117-131, 2006.
  [PDF]
• Sebastian Aland , Dominic Dumrauf , Martin Gairing , Burkhard Monien , Florian Schoppmann
  Exact Price of Anarchy for Polynomial Congestion Games
  Proc. of the 23rd International Symposium on Theoretical Aspects of Computer Science
  (STACS 2006), LNCS 3884, pp. 218-229, 2006.
  (c) Springer Verlag
  [PDF]
• Marcin Bienkowski , Martin Gairing , Georg Kliewer , Friedhelm Meyer auf der Heide , Burkhard Monien
  Universal Basic Services for Parallel Systems
  New Trends in Parallel & Distributed Computing, Proc. of the 6th International Heinz-Nixdorf Symposium,
  HNI-Verlagschriftenreihe, Vol. 181, pp. 154-170, 2006.
  [PDF]

2005

• Robert Elsässer , Martin Gairing , Thomas Lücking , Marios Mavronicolas , Burkhard Monien
  A Simple Graph-Theoretic Model for Selfish Restricted Scheduling
  Proc. of the 1st Workshop on Internet and Network Economics
  (WINE 2005), LNCS 3828, pp. 195-209, 2005.
  (c) Springer Verlag
  [PDF]
• Martin Gairing , Thomas Lücking , Marios Mavronicolas , Burkhard Monien , Paul Spirakis
  The Structure and Complexity of Extreme Nash Equilibria
  Theoretical Computer Science, 343, pp. 133-157, 2005
  [PDF]
• Martin Gairing , Burkhard Monien , Karsten Tiemann
  Selfish Routing with Incomplete Information
  Proc. of the 17th ACM Symposium on Parallelism in Algorithms and Architectures
  (SPAA 2005), pp. 203-212 2005
  [PDF]
• Martin Gairing , Thomas Lücking , Burkhard Monien , Karsten Tiemann
  Nash Equilibria, the Price of Anarchy and the Fully Mixed Nash Equilibrium Conjecture
  Proc. of the 32nd International Colloquium on Automata, Languages and Programming
  (ICALP 2005), LNCS 3580, pp. 51-65, 2005.
  (c) Springer Verlag
  [PDF]
• Martin Gairing , Burkhard Monien , Andreas Woclaw
  A Faster Combinatorial Approximation Algorithm for Scheduling Unrelated Parallel Machines
  Proc. of the 32nd International Colloquium on Automata, Languages and Programming
  (ICALP 2005), LNCS 3580, pp. 828-839, 2005.
  (c) Springer Verlag
  [PDF]

2004

• Martin Gairing, Wayne Goddard, Steven T. Hedetniemi, Petter Kristiansen, Alice A. McRae
  Distance-Two Information in Self-Stabilizing Algorithms
  Parallel Processing Letters (PPL), 14(3), pp. 387-398, 2004
  [PDF]
• Martin Gairing , Thomas Lücking , Marios Mavronicolas , Burkhard Monien
  The Price of Anarchy for Polynomial Social Cost
  Proc. of the 29th International Symposium on Mathematical Foundations of Computer Science
  (MFCS 2004), LNCS 3153, pp. 574-585, 2004.
  (c) Springer Verlag
  [PDF]
• Martin Gairing, Robert M. Geist, Steven T. Hedetniemi, Petter Kristiansen,
  A Self-Stabilizing Algorithm for maximal 2-packing
  Nordic Journal of Computing, 11(1), pp. 1-11, 2004
  [Postscript] [PDF]
• Martin Gairing , Thomas Lücking , Marios Mavronicolas , Burkhard Monien , Manuel Rode
  Nash Equilibria in Discrete Routing Games with Convex Latency Functions
  Proc. of the 31st International Colloquium on Automata, Languages and Programming
  (ICALP 2004), LNCS 3142, pp. 645-657, 2004.
  (c) Springer Verlag
  [PDF]
• Martin Gairing , Thomas Lücking , Marios Mavronicolas , Burkhard Monien
  Computing Nash Equilibria for Scheduling on Restricted Parallel Links
  36th ACM Symposium on Theory of Computing
  (STOC 2004), pp. 613-622, 2004
  [PDF]
• Martin Gairing, Wayne Goddard, Steven T. Hedetniemi, David P. Jacobs,
  Self-Stabilizing Maximal k-Dependent Sets in Linear Time
  Parallel Processing Letters (PPL), 14(1), pp. 75-82, 2004
  [PDF]

• Rainer Feldmann, Martin Gairing, Thomas Lücking, Burkhard Monien, Manuel Rode
  Selfish Routing in Non-Cooperative Networks: A Survey
  In Current Trends in Theoretical Computer Science: The Challenge of the New Century,
  Vol. 1, pp. 373-402, World Scientific, 2004.
  [Postscript]

2003

• Martin Gairing , Thomas Lücking , Marios Mavronicolas , Burkhard Monien , Paul Spirakis
  Extreme Nash Equilibria
  Proc. of the 8th Italian Conference on Theoretical Computer Science
  (ICTCS 2003), LNCS 2841, pp. 1-20, 2003.
  (c) Springer Verlag
  [PDF]
• Rainer Feldmann, Martin Gairing, Thomas Lücking, Burkhard Monien, Manuel Rode
  Selfish Routing in Non-Cooperative Networks: A Survey
  Bulletin of the EATCS, 81, pp. 1137-164, 2003.
  [Postscript]
• Rainer Feldmann, Martin Gairing, Thomas Lücking, Burkhard Monien, Manuel Rode
  Selfish Routing in Non-Cooperative Networks: A Survey
  Proc. of the 28th International Symposium on Mathematical Foundations of Computer Science (MFCS 2003),
  LNCS 2741, pp 21-45, 2003.
  (c) Springer Verlag
  [Postscript]
• Rainer Feldmann, Martin Gairing, Thomas Lücking, Burkhard Monien, Manuel Rode
  Nashification and the Coordination Ratio for a Selfish Routing Game
  Proc. of the 30th International Colloquium on Automata, Languages and Programming (ICALP 2003),
  LNCS 2719, pp 514-526, 2003.
  (c) Springer Verlag
  [PDF]
• Martin Gairing, Steven T. Hedetniemi, Petter Kristiansen, Alice A. McRae
  Self-Stabilizing Algorithms for {k}-domination
  Proceedings of the 6th Symposium on Self-Stabilization (SSS 2003),
  LNCS 2704, pp. 49-60, 2003.
  (c) Springer Verlag
  [PDF]

2002

• S. Balasubramanian, K. Bernasconi, J. Farr, M. Gairing, S. T. Hedetniemi, K. Hutson,
  R. Laskar, G. Stevens, J. Villalpando
  Gallai Theorems Involving Domination Parameters
  Congressus Numerantium, 157, pp. 149-157, 2002.
  [PDF]