Berthold Vöcking

Encyclopedia of Algorithms, 2016

Price of Anarchy for Machines Models.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

Smoothed Analysis of the 2-Opt Algorithm for the General TSP.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2016

2015

Truthful Mechanism Design via Correlated Tree Rounding.

[BibT_eX]

[DOI]

Yossi Azar

Idan Maor

Rebecca Reiffenhäuser

Proceedings of the Sixteenth ACM Conference on Economics and Computation, 2015

2014

Worst Case and Probabilistic Analysis of the 2-Opt Algorithm for the TSP.

[BibT_eX]

[DOI]

Algorithmica, 2014

Primal beats dual on online packing LPs in the random-order model.

[BibT_eX]

[DOI]

Proceedings of the Symposium on Theory of Computing, 2014

Thorp Shuffling, Butterflies, and Non-Markovian Couplings.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Online Independent Set Beyond the Worst-Case: Secretaries, Prophets, and Periods.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Optimized buffer allocation in multicore platforms.

[BibT_eX]

[DOI]

Proceedings of the Design, Automation & Test in Europe Conference & Exhibition, 2014

2013

Electronic Markets and Auctions (Dagstuhl Seminar 13461).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2013

Truthfulness and stochastic dominance with monetary transfers.

[BibT_eX]

[DOI]

Proceedings of the fourteenth ACM Conference on Electronic Commerce, 2013

An Optimal Online Algorithm for Weighted Bipartite Matching and Extensions to Combinatorial Auctions.

[BibT_eX]

[DOI]

Proceedings of the Algorithms - ESA 2013, 2013

2012

A universally-truthful approximation scheme for multi-unit auctions.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Randomized Mechanisms for Multi-unit Auctions - (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

Online Packing with Gradually Improving Capacity Estimations and Applications to Network Lifetime Maximization.

[BibT_eX]

[DOI]

Marcel Ochel

Klaus Radke

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

Online Mechanism Design (Randomized Rounding on the Fly).

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

Comparative Study of Approximation Algorithms and Heuristics for SINR Scheduling with Power Control.

[BibT_eX]

[DOI]

Proceedings of the Algorithms for Sensor Systems, 2012

2011

Scheduling and Power Assignments in the Physical Model.

[BibT_eX]

[DOI]

Alexander Fanghänel

Proceedings of the Theoretical Aspects of Distributed Computing in Sensor Networks, 2011

Approximation algorithms for secondary spectrum auctions.

[BibT_eX]

[DOI]

Proceedings of the SPAA 2011: Proceedings of the 23rd Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2011

Considerate Equilibrium.

[BibT_eX]

[DOI]

Proceedings of the IJCAI 2011, 2011

The Knapsack Problem.

[BibT_eX]

[DOI]

Proceedings of the Algorithms Unplugged, 2011

2010

Berechnung von Nash-Gleichgewichten.

[BibT_eX]

[DOI]

Inform. Spektrum, 2010

Distributed Contention Resolution in Wireless Networks.

[BibT_eX]

[DOI]

Proceedings of the Distributed Computing, 24th International Symposium, 2010

Online capacity maximization in wireless networks.

[BibT_eX]

[DOI]

Proceedings of the SPAA 2010: Proceedings of the 22nd Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2010

Brief announcement: distributed contention resolution in wireless networks.

[BibT_eX]

[DOI]

Proceedings of the 29th Annual ACM Symposium on Principles of Distributed Computing, 2010

10211 Abstracts Collection - Flexible Network Design.

[BibT_eX]

[DOI]

Proceedings of the Flexible Network Design, 24.05. - 28.05.2010, 2010

Regret Minimization for Online Buffering Problems Using the Weighted Majority Algorithm.

[BibT_eX]

[DOI]

Sascha Geulen

Melanie Winkler

Proceedings of the COLT 2010, 2010

2009

Economical Caching.

[BibT_eX]

[DOI]

Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science, 2009

Economical Caching with Stochastic Prices.

[BibT_eX]

[DOI]

Melanie Winkler

Proceedings of the Stochastic Algorithms: Foundations and Applications, 2009

Oblivious interference scheduling.

[BibT_eX]

[DOI]

Proceedings of the 28th Annual ACM Symposium on Principles of Distributed Computing, 2009

Improved Algorithms for Latency Minimization in Wireless Networks.

[BibT_eX]

[DOI]

Alexander Fanghänel

Thomas Keßelheim

Proceedings of the Automata, Languages and Programming, 36th Internatilonal Colloquium, 2009

Congestion games: Equilibria, convergence and complexity.

[BibT_eX]

[DOI]

Proceedings of the 1st International Conference on Game Theory for Networks, 2009

Approximability of OFDMA Scheduling.

[BibT_eX]

[DOI]

Marcel Ochel

Proceedings of the Algorithms, 2009

Management of Variable Data Streams in Networks.

[BibT_eX]

[DOI]

Proceedings of the Algorithmics of Large and Complex Networks - Design, 2009

2008

Utilitarian Mechanism Design for Single-Minded Agents.

[BibT_eX]

[DOI]

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Price of Anarchy for Machines Models.

[BibT_eX]

[DOI]

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Das Rucksackproblem.

[BibT_eX]

[DOI]

Proceedings of the Taschenbuch der Algorithmen, 2008

Inapproximability of pure nash equilibria.

[BibT_eX]

[DOI]

Alexander Skopalik

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

Computing Approximate Nash Equilibria in Network Congestion Games.

[BibT_eX]

[DOI]

Andreas Emil Feldmann

Proceedings of the Structural Information and Communication Complexity, 2008

Uncoordinated two-sided matching markets.

[BibT_eX]

[DOI]

Proceedings of the Proceedings 9th ACM Conference on Electronic Commerce (EC-2008), 2008

2007

A Unified Approach to Congestion Games and Two-Sided Markets.

[BibT_eX]

[DOI]

Proceedings of the Internet and Network Economics, Third International Workshop, 2007

Who Should Pay for Forwarding Packets?

[BibT_eX]

[DOI]

Proceedings of the Internet and Network Economics, Third International Workshop, 2007

Approximating Wardrop Equilibria with Finitely Many Agents.

[BibT_eX]

[DOI]

Lars Olbrich

Proceedings of the Distributed Computing, 21st International Symposium, 2007

Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP: extended abstract.

[BibT_eX]

[DOI]

Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

The Smoothed Number of Pareto Optimal Solutions in Bicriteria Integer Optimization.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 2007

07391 Abstracts Collection - Probabilistic Methods in the Design and Analysis of Algorithms.

[BibT_eX]

[DOI]

Martin Dietzfelbinger

Shang-Hua Teng

Eli Upfal

Proceedings of the Probabilistic Methods in the Design and Analysis of Algorithms, 23.09., 2007

Distributed Load Balancing Algorithm for Adaptive Channel Allocation for Cognitive Radios.

[BibT_eX]

[DOI]

Proceedings of the 2nd International ICST Conference on Cognitive Radio Oriented Wireless Networks and Communications, 2007

2006

Computing equilibria for a service provider game with (Im)perfect information.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2006

Foreword.

[BibT_eX]

[DOI]

Aravind Srinivasan

Theory Comput. Syst., 2006

Pure Nash Equilibria in Player-Specific and Weighted Congestion Games.

[BibT_eX]

[DOI]

Heiner Ackermann

Proceedings of the Internet and Network Economics, Second International Workshop, 2006

Fast convergence to Wardrop equilibria by adaptive sampling methods.

[BibT_eX]

[DOI]

Harald Räcke

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

On the Impact of Combinatorial Structure on Congestion Games.

[BibT_eX]

[DOI]

Heiner Ackermann

Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, 2006

Congestion Games: Optimization in Competition.

[BibT_eX]

Proceedings of the Algorithms and Complexity in Durham 2006, 2006

2005

On the Structure and Complexity of Worst-Case Equilibria.

[BibT_eX]

[DOI]

Proceedings of the Internet and Network Economics, First International Workshop, 2005

Approximation techniques for utilitarian mechanism design.

[BibT_eX]

[DOI]

Patrick Briest

Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

Adaptive routing with stale information.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fourth Annual ACM Symposium on Principles of Distributed Computing, 2005

Decision Making Based on Approximate and Smoothed Pareto Curves.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation, 16th International Symposium, 2005

Smoothed Analysis of Integer Programming.

[BibT_eX]

[DOI]

Proceedings of the Integer Programming and Combinatorial Optimization, 2005

2004

Foreword.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2004

Typical properties of winners and losers in discrete optimization.

[BibT_eX]

[DOI]

Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

Probabilistic analysis of knapsack core algorithms.

[BibT_eX]

[DOI]

Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Computing equilibria for congestion games with (im)perfect information.

[BibT_eX]

[DOI]

Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

On the Evolution of Selfish Routing.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2004

An Experimental Study of Random Knapsack Problems.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2004

2003

Tail Bounds And Expectations For Random Arc Allocation And Applications.

[BibT_eX]

[DOI]

Comb. Probab. Comput., 2003

Random knapsack in expected polynomial time.

[BibT_eX]

[DOI]

Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

Scheduling and Traffic Allocation for Tasks with Bounded Splittability.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2003, 2003

An Experimental Study of <i>k</i>-Splittable Scheduling for DNS-Based Traffic Allocation.

[BibT_eX]

[DOI]

Proceedings of the Euro-Par 2003. Parallel Processing, 2003

2002

Random Arc Allocation and Applications.

[BibT_eX]

[DOI]

Proceedings of the Algorithm Theory, 2002

Selfish traffic allocation for server farms.

[BibT_eX]

[DOI]

Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

Tight bounds for worst-case equilibria.

[BibT_eX]

[DOI]

Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

Randomized Pursuit-Evasion in Graphs.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 29th International Colloquium, 2002

Routing and Communication in Interconnection Networks.

[BibT_eX]

[DOI]

Proceedings of the Euro-Par 2002, 2002

2001

Almost optimal permutation routing on hypercubes.

[BibT_eX]

[DOI]

Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

A data tracking scheme for general networks.

[BibT_eX]

[DOI]

Proceedings of the Thirteenth Annual ACM Symposium on Parallel Algorithms and Architectures, 2001

2000

Balanced allocations: the heavily loaded case.

[BibT_eX]

[DOI]

Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

Caching in networks (extended abstract).

[BibT_eX]

[DOI]

Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

Randomized Rumor Spreading.

[BibT_eX]

[DOI]

Richard M. Karp

Christian Schindelhauer

Scott Shenker

Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

1999

Shortest-Path Routing in Arbitrary Networks.

[BibT_eX]

[DOI]

J. Algorithms, 1999

From Static to Dynamic Routing: Efficient Transformations of Store-and-Forward Protocols.

[BibT_eX]

[DOI]

Christian Scheideler

Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Data Management in Networks: Experimental Evaluation of a Provably Good Strategy.

[BibT_eX]

[DOI]

Christof Krick

Harald Räcke

Proceedings of the Eleventh Annual ACM Symposium on Parallel Algorithms and Architectures, 1999

Approximating Multicast Congestion.

[BibT_eX]

[DOI]

Santosh S. Vempala

Proceedings of the Algorithms and Computation, 10th International Symposium, 1999

How Asymmetry Helps Load Balancing.

[BibT_eX]

[DOI]

Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

Provably Good and Practical Strategies for Non-Uniform Data Management in Networks.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 1999

1998

Static and dynamic data Management in networks.

[BibT_eX]

[DOI]

PhD thesis, 1998

Randomized Protocols for Low Congestion Circuit Routing in Multistage Interconnection Networks.

[BibT_eX]

[DOI]

Richard Cole

Bruce M. Maggs

Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

1997

Improved Routing and Sorting on Multibutterflies.

[BibT_eX]

[DOI]

Bruce M. Maggs

Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

Exploiting Locality for Data Management in Systems of Limited Bandwidth.

[BibT_eX]

[DOI]

Bruce M. Maggs

Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997

Static and Dynamic Data Management in Networks.

[BibT_eX]

[DOI]

Proceedings of the Euro-Par '97 Parallel Processing, 1997

1996

Universal Algorithms for Store-and-Forward and Wormhole Routing.

[BibT_eX]

[DOI]

Robert Cypher

Christian Scheideler

Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996

Universal Continuous Routing Strategies.

[BibT_eX]

[DOI]

Christian Scheideler

Proceedings of the 8th Annual ACM Symposium on Parallel Algorithms and Architectures, 1996

1995

A Packet Routing Protocol for Arbitrary Networks.

[BibT_eX]

[DOI]