Lehrstuhl Informatik 1 - Publications

Publications 2008

Conference Publications
- Uncoordinated Two-Sided Matching Markets.
  
  Heiner Ackermann, Paul Goldberg, Vahab Mirrokni, Heiko Röglin, Berthold Vöcking
  
  In Proc. of the 9th EC, Outstanding Paper Award
  
  Chicago, USA, 2008, pp. 256-263.
- An optimal algorithm for the k-fixed-endpoint path cover on proper interval graphs.
  
  George B. Mertzios , Walter Unger
  
  In Proc. of the 19th International Workshop on Combinatorial Algorithms (IWOCA 2008)
  
  Nagoya, Japan, 2008, pp. 197-211.
- The friendship problem on graphs.
  
  George B. Mertzios , Walter Unger
  
  In Proc. of the 1st International Conference on Relations, Orders and Graphs: Interaction with Computer Science (ROGICS 2008)
  
  Mahdia, Tunisia, 2008, pp. 152-158.
- Load Balancing for Dynamic Spectrum Assignment with Local Information for Secondary Users.
  
  Simon Fischer, Petri Mähönen, Marcel Schöngens, Berthold Vöcking
  
  In Proc. of the IEEE International Dynamic Access Spectrum Access Networks (DySPAN) symposium
  
  Chicago, Illinois, USA, 2008.
- Inapproximability of Pure Nash Equilibria.
  
  Alexander Skopalik, Berthold Vöcking
  
  In Proc. of the 40th ACM Symposium on Theory of Computing (STOC)
  
  Victoria, Canada, 2008.
- Fast Convergence to Nearly Optimal Solutions in Potential Games.
  
  Amir Epstein, Baruch Awerbuch, Yossi Azar, Vahab Mirrokni, Alexander Skopalik
  
  In Proc. of the ACM Conferencee on Electronic Commerce (EC)
  
  Chicago, USA, 2008.
Journal Publications
- Approximating Wardrop Equilibria with Finitely Many Agents.
  
  Simon Fischer, Lars Olbrich, Berthold Vöcking
  
  Distributed Computing, Volume 21 (2), 2008 (Special Issue DISC 2007.)
- Adaptive Routing with Stale Information.
  
  Simon Fischer, Berthold Vöcking
  
  Theoretical Computer Science, 2008 (Invited paper. To appear.)
- A matrix characterization of interval and proper interval graphs.
  
  George B. Mertzios
  
  Applied Mathematics Letters, Volume 21 (4), pp. 332-337, 2008.

Publications 2007

Conference Publications
- A Unified Approach to Congestion Games and Two- Sided Markets
  
  Heiner Ackermann, Paul Goldberg, Vahab Mirrokni, Heiko Röglin, Berthold Vöcking
  
  In Proc. of the 3rd International Workshop on Internet and Network Economics (WINE)
  
  San Diego, USA, 2007, Pages 30-41.
- Who Should Pay for Forwarding Packets?
  
  Heiner Ackermann, Patrick Briest, Alexander Fanghänel, Berthold Vöcking
  
  In Proc. of the 3rd International Workshop on Internet and Network Economics (WINE)
  
  San Diego, USA, 2007, Pages 208-219.
- On the Complexity of Pure Nash Equilibria in Player-Specific Network Congestion Games
  
  Heiner Ackermann, Alexander Skopalik
  
  In Proc. of the 3rd International Workshop on Internet and Network Economics (WINE)
  
  San Diego, USA, 2007, Pages 419-430.
- Approximating Wardrop Equilibria with Finitely Many Agents
  
  Simon Fischer, Lars Olbrich, Berthold Vöcking
  
  In Proc. of the 21st International Symposium on Distributed Computing (DISC)
  
  Lemesos, Cyprus, 2007, Pages 238-252.
- Distributed Load Balancing Algorithm for Adaptive Channel Allocation for Cognitive Radios
  
  Simon Fischer, Marina Petrova, Petri Mähönen, Berthold Vöcking
  
  In Proc. of the 2nd Conference on Cognitive Radio Oriented Wireless Networks and Communications (CrownCom)
  
  Orlando, USA, 2007, to appear.
- A First Step towards Analyzing the Convergence Time in Player-Specific Singleton Congestion Games
  
  Heiner Ackermann
  
  In Proc. of the 4th Symposium on Stochastic Algorithms, Foundations, and Applications (SAGA)
  
  Zürich, Switzerland, 2007, Pages 58-69.
- On the Complexity of the Traffic Grooming Problem in Optical Networks
  
  Mordechai Shalom, Walter Unger, Shmuel Zaks
  
  In Proc. of the 4th International Conference on Fun With Algorithms (FUN)
  
  Castiglioncello, Italy, 2007, to appear.
- Reordering Buffers for General Metric Spaces
  
  Matthias Englert, Harald Räcke, Matthias Westermann
  
  In Proc. of the 39th Annual ACM Symposium on Theory of Computing (STOC)
  
  San Diego, USA, 2007, Pages 556-564.
- The Smoothed Number of Pareto Optimal Solutions in Bicriteria Integer Optimization
  
  Rene Beier, Heiko Röglin, Berthold Vöcking
  
  In Proc. of the 12th Conference on Integer Programming and Combinatorial Optimization (IPCO)
  
  Ithaca, USA, 2007, Pages 53-67.
- Considering Suppressed Packets Improves Buffer Management in QoS Switches
  
  Matthias Englert, Matthias Westermann
  
  In Proc. of the 18th Symposium on Discrete Algorithms (SODA)
  
  New Orleans, USA, 2007, Pages 209-218.
- Worst Case and Probabilistic Analysis of the 2-Opt Algorithm for the TSP
  
  Matthias Englert, Heiko Röglin, Berthold Vöcking
  
  In Proc. of the 18th Symposium on Discrete Algorithms (SODA)
  
  New Orleans, USA, 2007, Pages 1295-1304. (BibTeX)
Journal Publications
- Decision-Making Based on Approximate and Smoothed Pareto Curves
  
  Heiner Ackermann, Alantha Newman, Heiko Röglin, Berthold Vöcking
  
  Theoretical Computer Science, Volume 378 (3), 2007, Pages 253-270.
- On the Structure and Complexity of Worst-Case Equilibria
  
  Simon Fischer, Berthold Vöcking
  
  Theoretical Computer Science, Volume 378 (2), 2007, Pages 165-174.
- On-line Load Balancing made Simple: Greedy Strikes Back.
  
  Pilu Crescenzi, Giorgio Gambosi, Gaia Nicosia, Paolo Penna, Walter Unger
  
  Journal of Discrete Algorithms, Volume 5 (1), 2007, Pages 162-175.
- Smoothed Analysis of Integer Programming
  
  Heiko Röglin, Berthold Vöcking
  
  Mathematical Programming, Volume 110 (1), 2007, Pages 21-56.
- Tight bounds for Worst-Case Equilibria
  
  Artur Czumaj, Berthold Vöcking
  
  ACM Transactions on Algorithms, Volume 3 (1), 2007.

Publications 2006

Conference Publications
- Congestion Games: Optimization in Competition (Survey Paper)
  
  Berthold Vöcking
  
  In Proc. of the 2nd Algorithms and Complexity in Durham Workshop (ACiD)
  
  Durham, UK, 2006, Pages 9-20. (BibTeX)
- REPLEX — Dynamic Traffic Engineering Based on Wardrop Routing Policies
  
  Simon Fischer, Nils Kammenhuber, Anja Feldmann
  
  In Proc. of the 2nd Conference on Future Networking Technologies (CoNext)
  
  Lisboa, Portugal, 2006, Pages 6-17. (BibTeX)
- Pure Nash Equilibria in Player-Specific and Weighted Congestion Games
  
  Heiner Ackermann, Heiko Röglin, Berthold Vöcking
  
  In Proc. of the 2nd International Workshop on Internet and Network Economics (WINE)
  
  Patras, Greece, 2006, Pages 50-61. (BibTeX)
- On the Impact of Combinatorial Structure on Congestion Games
  
  Heiner Ackermann, Heiko Röglin, Berthold Vöcking
  
  In Proc. of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS)
  
  Berkeley, USA, 2006, Pages 613-622. (BibTeX)
- Lower and Upper Bounds on FIFO Buffer Management in QoS Switches
  
  Matthias Englert, Matthias Westermann
  
  In Proc. of the 14th Annual European Symposium on Algorithms (ESA)
  
  Zürich, Switzerland, 2006, Pages 352-363. (BibTeX)
- Fast Convergence to Wardrop Equilibria by Adaptive Sampling Methods
  
  Simon Fischer, Harald Räcke, Berthold Vöcking
  
  In Proc. of the 38th Annual ACM Symposium on Theory of Computing (STOC)
  
  Seattle, USA, 2006, Pages 653 - 662. (BibTeX)
- Evaluation of Online Strategies for Reordering Buffers
  
  Matthias Englert, Heiko Röglin, Matthias Westermann
  
  In Proc. of the 5th Workshop on Experimental and Efficient Algorithms (WEA)
  
  Menorca Island, Spain, 2006, Pages 183-194. (BibTeX)
Journal Publications
- Balanced Allocations: The Heavily Loaded Case
  
  Petra Berenbrink, Artur Czumaj, Angelika Steger, Berthold Vöcking
  
  SIAM Journal on Computing, Volume 35 (6), 2006, Pages 1350-1385. (BibTeX)
- Typical Properties of Winners and Losers in Discrete Optimization
  
  Rene Beier, Berthold Vöcking
  
  SIAM Journal on Computing, Volume 35 (4), 2006, Pages 855-881. (BibTeX)
- An Experimental Study of Random Knapsack Problems
  
  Rene Beier, Berthold Vöcking
  
  Algorithmica, Volume 45 (1), 2006, Pages 121-136. (BibTeX)
- Computing Equilibria for a Service Provider Game with (Im)perfect Information
  
  Rene Beier, Artur Czumaj, Piotr Krysta, Berthold Vöcking
  
  ACM Transactions on Algorithms, Volume 2 (4), 2006, Pages 679-706.

Publications 2005

Conference Publications
- Decision Making Based on Approximate and Smoothed Pareto Curves
  
  Heiner Ackermann, Alantha Newman, Heiko Röglin, Berthold Vöcking
  
  In Proc. of the 16th Annual International Symposium on Algorithms and Computation (ISAAC)
  
  Sanya, China, 2005, Pages 675-684. (BibTeX)
- A 1.5-Approximation of the Minimal Manhattan Network Problem
  
  Sebastian Seibert, Walter Unger
  
  In Proc. of the 16th Annual International Symposium on Algorithms and Computation (ISAAC)
  
  Sanya, China, 2005, Pages 246-255. (BibTeX)
- On the Structure and Complexity of Worst-Case Equilibria
  
  Simon Fischer, Berthold Vöcking
  
  In Proc. of the 1st Workshop on Internet and Network Economics (WINE)
  
  Hong Kong, China, 2005, Pages 151-160. (BibTeX)
- Adaptive routing with stale information
  
  Simon Fischer, Berthold Vöcking
  
  In Proc. of the 24th Annual ACM Symposium on Principles of Distributed Computing (PODC)
  
  Las Vegas, USA, 2005, Pages 276-283. (BibTeX)
- Reordering Buffer Management for Non-uniform Cost Models
  
  Matthias Englert, Matthias Westermann
  
  In Proc. of the 32nd International Colloquium on Automata, Languages and Programming (ICALP)
  
  Lisbon, Portugal, 2005, Pages 627-638. (BibTeX)
- Smoothed Analysis of Integer Programming
  
  Heiko Röglin, Berthold Vöcking
  
  In Proc. of the 11th Conference on Integer Programming and Combinatorial Optimization (IPCO)
  
  Berlin, Germany, 2005, Pages 276-290. (BibTeX)
- Aggregating inconsistent information: ranking and clustering
  
  Nir Ailon, Moses Charikar, Alantha Newman
  
  In Proc. of the 37th Annual ACM Symposium on Theory of Computing (STOC)
  
  Baltimore, USA, 2005, Pages 684-693. (BibTeX)
- Approximation Techniques for Utilitarian Mechanims Design
  
  Patrick Briest, Piotr Krysta, Berthold Vöcking
  
  In Proc. of the 37th Annual ACM Symposium on Theory of Computing (STOC)
  
  Baltimore, USA, 2005, Pages 39-48. (BibTeX)
Journal Publications
- The one-dimensional Ising model: Mutation versus recombination
  
  Simon Fischer, Ingo Wegener
  
  Theoretical Computer Science, Volume 344 (2-3), 2005, Pages 208-225. (BibTeX)
Annual Report 2005 [pdf]

Previous annual reports

2004 [ps], 2003 [ps], 2002 [ps], 2001 [ps], 2000 [ps], 1999 [ps], 1998 [ps], 1997 [ps]

Computer Science i1

Research

Teaching

Links

Miscellaneous

Publications 2008