Informatik Und Naturwissenschaften, Simon Fischer, Berthold Vöcking, ...
This thesis deals with dynamic, load-adaptive rerouting policies in game theoretic settings. In the Wardrop model, which forms the basis of our dynamic population model, each of an infinite number of...
Dynamic Selfish Routing and Traffic Optimisation (2009)
Simon Fischer, Berthold Vöcking
Abstract This work surveys results from [18,19,20,21,22,23]. Recently, the Wardrop model has attracted a lot of attention as a model of selfish behaviour in routing scenarios. In this model, an...
20 Selfish Load Balancing (2009)
Suppose that a set of weighted tasks shall be assigned to a set of machines with possibly different speeds such that the load is distributed evenly among the machines. In computer science, this...
Approximating Wardrop Equilibria with Finitely Many Agents (2009)
Simon Fischer, Lars Olbrich, Berthold Vöcking
the date of receipt and acceptance should be inserted later Abstract We present efficient algorithms for computing approximate Wardrop equilibria in a distributed and concurrent fashion. Our...
Symmetric vs. Asymmetric Multiple-Choice Algorithms (2009)
Multiple-choice allocation algorithms have been studied intensively over the last decade. These algorithms have several applications in the areas of load balancing, routing, resource allocation and...
Adaptive Routing with Stale Information 1,2 Abstract (2009)
Simon Fischer, Berthold Vöcking
We investigate the behaviour of load-adaptive rerouting policies in the Wardrop model where decisions must be made on the basis of stale information. In this model, an infinite number of agents...
Matthias Englert, Heiko Röglin, Berthold Vöcking
2-Opt is probably the most basic and widely used local search heuristic for the TSP. This heuristic achieves amazingly good results on “real world ” Euclidean instances both with respect to...
Englert, Matthias, Röglin, Heiko, Spönemann, Jacob, Vöcking, Berthold
We study the management of buffers and storages in environments with unpredictably varying prices in a competitive analysis. In the economical caching problem, there is a storage with a certain...
Englert, Matthias, Röglin, Heiko, Spönemann, Jacob, Vöcking, Berthold
We study the management of buffers and storages in environments with unpredictably varying prices in a competitive analysis. In the economical caching problem, there is a storage with a certain...
Englert, Matthias, Röglin, Heiko, Spönemann, Jacob, Vöcking, Berthold
We study the management of buffers and storages in environments with unpredictably varying prices in a competitive analysis. In the economical caching problem, there is a storage with a certain...
DFG-Sonderforschungsbereich 376 and the IST Programme of the EU under contract number (2008)
Christof Krick, Friedhelm Meyer Heide, Harald Räcke, Berthold Vöcking, Matthias Westermann
This paper deals with data management for parallel and distributed systems. We present the DIVA (Distributed Variables) library that provides direct access to shared data objects from each node in a...
Richard Cole, Bruce M. Maggs, Friedhelm Meyer, Heide Michael Mitzenmacher, Andréa W. Richa, Klaus Schröder, ...
In this paper we study randomized algorithms for circuit switching on multistage networks related to the butterfly. We devise algorithms that route messages by constructing circuits (or paths) for...
ABSTRACT Random Knapsack in Expected Polynomial Time (2008)
In this paper, we present the first average-case analysis proving an expected polynomial running time for an exact algorithm for the 0/1 knapsack problem. In particular, we prove, for various input...
Abstract Computing Equilibria for Congestion Games with (Im)perfect Information ∗ (2008)
Rene Beier, Artur Czumaj, Piotr Krysta, Berthold Vöcking
We study algorithmic questions concerning a basic microeconomic congestion game in which there is a single provider that offers a service to a set of potential customers. Each customer has a...
Journal of Algorithms, Vol 31(1), 1999 Shortest Path Routing in Arbitrary Networks ∗ (2008)
We introduce an on-line protocol which routes any set of N packets along shortest paths with congestion C and dilation D through an arbitrary network in O(C +D +log N) steps, with high probability....
Tail bounds and expectations for random arc allocation and applications (2008)
The paper considers a generalization of the well known random placement of balls into bins. Given n circular arcs of lengths αi, 0 ¡ ¢ i n we study the maximum number of overlapping arcs on a...
Abstract Improved Routing and Sorting on Multibutterflies (2008)
Bruce M. Maggs, Berthold Vöcking
This paper shows that an ¢-node AKS network (as ¤ described by Paterson) can be embedded £ ¥ in a-node degree-8 multibutterfly network with load 1, congestion 1, and dilation 2. The result has...
Work Package 3.1: Approximation Theory for Large-Scale Optimization (2008)
Deliverable D, Berthold Vöcking, Ingmar Weber, Christos Zaroliagis
Re-evaluation of important nonlinear continuous optimization techniques Start date of the project: January 2004 Duration: 48 months Project Coordinator: Prof. Dr. math. Friedhelm Meyer auf der Heide
Computing Equilibria for a Service Provider Game with (Im)perfect Information ∗ (2008)
Rene Beier, Artur Czumaj, Piotr Krysta, Berthold Vöcking
We study fundamental algorithmic questions concerning the complexity of market equilibria under perfect and imperfect information by means of a basic microeconomic game. Suppose a provider offers a...
Richard Cole, Bruce M. Maggs, Friedhelm Meyer, Heide Michael Mitzenmacher, Andréa W. Richa, Klaus Schröder, ...
In this paper we study randomized algorithms for circuit switching on multistage networks related to the butterfly. We devise algorithms that route messages by constructing circuits (or paths) for...
A Counterexample to the Fully Mixed Nash Equilibrium Conjecture (2008)
Simon Fischer, Simon Fischer, Berthold Vöcking, Berthold Vöcking
Abstract. We study a well-known resource allocation game introduced by Koutsoupias and Papadimitriou. It was conjectured by Gairing et al. that the fully mixed Nash equilibrium is the worst Nash...
Evolutionary Game Theory with Applications to Adaptive Routing ∗ (2008)
Simon Fischer, Berthold Vöcking
One of the most important problems in large communication networks like the Internet is the problem of routing traffic through the network. Current Internet technology based on the TCP protocol does...
Approximating Wardrop Equilibria with Finitely Many Agents (2008)
Simon Fischer, Lars Olbrich, Berthold Vöcking
Abstract. We study adaptive routing algorithms in a round-based model. Suppose we are given a network equipped with load-dependent latency functions on the edges and a set of commodities each of...
Abstract On the Structure and Complexity of Worst-Case Equilibria 1 (2008)
Simon Fischer, Berthold Vöcking
In the resource allocation game introduced by Koutsoupias and Papadimitriou, n jobs of different weights are assigned to m identical machines by selfish agents. For this game it has been conjectured...
Abstract On the Structure and Complexity of Worst-Case Equilibria 1 (2008)
Simon Fischer, Berthold Vöcking
In the resource allocation game introduced by Koutsoupias and Papadimitriou, n jobs of different weights are assigned to m identical machines by selfish agents. For this game it has been conjectured...
A Counterexample to the Fully Mixed Nash Equilibrium Conjecture (2008)
Simon Fischer, Simon Fischer, Berthold Vöcking, Berthold Vöcking
Abstract. We study a well-known resource allocation game introduced by Koutsoupias and Papadimitriou. It was conjectured by Gairing et al. that the fully mixed Nash equilibrium is the worst Nash...
Evolutionary Game Theory with Applications to Adaptive Routing (2008)
Simon Fischer, Berthold Vöcking
One of the most important problems in large communication networks like the Internet is the problem of routing traffic through the network. Current Internet technology based on the TCP protocol does...
Computing Equilibria for Congestion Games (2008)
With Im Perfect, Rene Beier, Artur Czumaj, Piotr Krysta, Berthold Vöcking
We study algorithmic questions concerning a basic microeconomic congestion game in which there is a single provider that offers a service to a set of potential customers. Each customer has a...
Uncoordinated twosided markets (2008)
Heiner Ackermann, Heiner Ackermann, Paul W. Goldberg, Paul W. Goldberg, Vahab S. Mirrokni, Vahab S. Mirrokni, ...
Abstract. Various economic interactions can be modeled as two-sided markets. A central solution concept to these markets are stable matchings, introduced by Gale and Shapley. It is well known that...
Heiner Ackermann, Vahab S. Mirrokni, Berthold Vöcking, Paul W. Goldberg, Heiko Röglin
Various economic interactions can be modeled as two-sided markets. A central solution concept to these markets are stable matchings, introduced by Gale and Shapley. It is well known that stable...
Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP (2007)
Matthias Englert, Heiko Röglin, Berthold Vöcking
2-Opt is probably the most basic local search heuristic for the TSP. This heuristic achieves amazingly good results on “real world ” Euclidean instances both with respect to running time and...
A Unified Approach to Congestion Games and Two-Sided Markets (2007)
Heiner Ackermann, Vahab S. Mirrokni, Paul W. Goldberg, Heiko Röglin, Berthold Vöcking
Congestion games are a well-studied model for resource sharing among uncoordinated selfish agents. Usually, one assumes that the resources in a congestion game do not have any preferences over the...
The smoothed number of Pareto optimal solutions in bicriteria integer optimization (2007)
Rene Beier, Heiko Röglin, Berthold Vöcking
Abstract. A well established heuristic approach for solving various bicriteria optimization problems is to enumerate the set of Pareto optimal solutions, typically using some kind of dynamic...
Dynamic Selfish Routing (2007)
Informatik Und Naturwissenschaften, Simon Fischer, Dr. Berthold Vöcking, ...
iv This thesis deals with dynamic, load-adaptive rerouting policies in game theoretic settings. In the Wardrop model, which forms the basis of our dynamic population model, each of an infinite number...
Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP (2007)
Matthias Englert, Heiko Röglin, Berthold Vöcking
2-Opt is probably the most basic and widely used local search heuristic for the TSP. This heuristic achieves amazingly good results on “real world ” Euclidean instances both with respect to...
A Unified Approach to Congestion Games and Two-Sided Markets (2007)
Heiner Ackermann, Paul W. Goldberg, Vahab S. Mirrokni, Heiko Röglin, Berthold Vöcking
Abstract. Congestion games are a well-studied model for resource sharing among uncoordinated selfish agents. Usually, one assumes that the resources in a congestion game do not have any preferences...
A unified approach to congestion games and two-sided markets (2007)
Heiner Ackermann, Paul W. Goldberg, Vahab S. Mirrokni, Heiko Röglin, Berthold Vöcking
Abstract. Congestion games are a well-studied model for resource sharing among uncoordinated selfish agents. Usually, one assumes that the resources in a congestion game do not have any preferences...
Approximating Wardrop equilibria with finitely many agents (2007)
Simon Fischer, Lars Olbrich, Berthold Vöcking
We present efficient algorithms for computing approximate Wardrop equilibria in a distributed and concurrent fashion. Our algorithms are exexuted by a finite number of agents each of which controls...
07391 Abstracts Collection -- Probabilistic Methods in the Design and Analysis of Algorithms (2007)
Dietzfelbinger, Martin, Teng, Shang-Hua, Upfal, Eli, Vöcking, Berthold
From 23.09.2007 to 28.09.2007, the Dagstuhl Seminar 07391 "Probabilistic Methods in the Design and Analysis of Algorithms''was held in the International Conference and Research Center (IBFI), Schloss...
Algorithmic Aspects of Some Combinatorial Problems in Bioinformatics (2006)
Dirk Bongartz, Aus Viersen, ...
Diese Dissertation ist auf den Internetseiten der Hochschulbibliothek online verfügbar. ii The consistently growing field of bioinformatics exhibits the success of cooperative work in biology and...
On the Impact of Combinatorial Structure on Congestion Games (2006)
Heiner Ackermann, Heiko Röglin, Berthold Vöcking
We study the impact of combinatorial structure in congestion games on the complexity of computing pure Nash equilibria and the convergence time of best response sequences. In particular, we...
Mathematical Programming manuscript No. (will be inserted by the editor) (2006)
Heiko Röglin, Berthold Vöcking
Abstract We present a probabilistic analysis of integer linear programs (ILPs). More specifically, we study ILPs in a so-called smoothed analysis in which it is assumed that first an adversary...
Pure Nash equilibria in player-specific and weighted congestion games (2006)
Heiner Ackermann, Heiko Röglin, Berthold Vöcking
Unlike standard congestion games, weighted congestion games and congestion games with player-specific delay functions do not necessarily possess pure Nash equilibria. It is known, however, that there...
Congestion games: Optimization in competition (2006)
abstract. In a congestion game, several players simultaneously aim at allocating sets of resources, e.g., each player aims at allocating a shortest path between a source/destination pair in a given...
Computing Equilibria for a Service Provider Game with (Im)perfect Information (2006)
Beier, René, Czumaj, Artur, Krysta, Piotr, Vöcking, Berthold
We study fundamental algorithmic questions concerning the complexity of market equilibria under perfect and imperfect information by means of a basic microeconomic game. Suppose a provider offers a...
Typical Properties of Winners and Losers in Discrete Optimization (2006)
Beier, René, Vöcking, Berthold
We present a probabilistic analysis of a large class of combinatorial optimization problems containing all {\em binary optimization problems} defined by linear constraints and a linear objective...
An Experimental Study of Random Knapsack Problems (2006)
Beier, René, Vöcking, Berthold
The size of the Pareto curve for the bicriteria version of the knapsack problem is polynomial on average. This has been shown for various random input distributions. We experimentally investigate the...
Smoothed analysis of integer programming (2005)
Heiko Röglin, Berthold Vöcking
Abstract. We present a probabilistic analysis of integer linear programs (ILPs). More specifically, we study ILPs in a so-called smoothed analysis in which it is assumed that first an adversary...
Decision making based on approximate and smoothed pareto curves (2005)
Heiner Ackermann, Alantha Newman, Heiko Röglin, Berthold Vöcking
We consider bicriteria optimization problems and investigate the relationship between two standard approaches to solving them: (i) computing the Pareto curve and (ii) the so-called decision maker’s...
Adaptive Routing with Stale Information (2005)
Simon Fischer, Berthold Vöcking
We investigate adaptive routing policies for large networks in which agents reroute tra#c based on old information. It is a well known and practically relevant problem that old information can lead...
A Counterexample to the Fully Mixed Nash Equilibrium Conjecture (2005)
Simon Fischer, Simon Fischer, Berthold Vöcking, Berthold Vöcking
We study a well-known resource allocation game introduced by Koutsoupias and Papadimitriou. It was conjectured by Gairing et al. that the fully mixed Nash equilibrium is the worst Nash equilibrium...
A Counterexample to the Fully Mixed Nash Equilibrium Conjecture (2005)
Simon Fischer, Simon Fischer, Berthold Vöcking, Berthold Vöcking
We study a well-known resource allocation game introduced by Koutsoupias and Papadimitriou. It was conjectured by Gairing et al. that the fully mixed Nash equilibrium is the worst Nash equilibrium...
Adaptive Routing with Stale Information (2005)
Simon Fischer, Simon Fischer, Berthold Vöcking, Berthold Vöcking
We investigate adaptive routing policies for large networks in which agents reroute tra#c based on old information. It is a well known and practically relevant problem that old information can lead...
On the Structure and Complexity (2005)
Simon Fischer, Berthold Vöcking
We study an intensively studied resource allocation game introduced by Koutsoupias and Papadimitriou where n weighted jobs are allocated to m identical machines. It was conjectured by Gairing et al....
Decision making based on approximate and smoothed pareto curves (2005)
Decision Making Based, Heiner Ackermann, Heiner Ackermann, Alantha Newman, Alantha Newman, Heiko Röglin, ...
We consider bicriteria optimization problems and investigate the relationship between two standard approaches to solving them: (i) computing the Pareto curve and (ii) the so-called decision...
On the Structure and Complexity of Worst-case Equilibria (2005)
Simon Fischer, Berthold Vöcking
Abstract. We study an intensively studied resource allocation game introduced by Koutsoupias and Papadimitriou where n weighted jobs are allocated to m identical machines. It was conjectured by...
Decision making based on approximate and smoothed pareto curves (2005)
Heiner Ackermann, Heiner Ackermann, Alantha Newman, Alantha Newman, Heiko Röglin, Heiko Röglin, ...
Abstract. We consider bicriteria optimization problems and investigate the relationship between two standard approaches to solving them: (i) computing the Pareto curve and (ii) the so-called decision...
Adaptive routing with stale information (2005)
Simon Fischer, Simon Fischer, Berthold Vöcking, Berthold Vöcking
Abstract. We investigate adaptive routing policies for large networks in which agents reroute traffic based on old information. It is a well known and practically relevant problem that old...
Decision making based on approximate and smoothed pareto curves (2005)
Heiner Ackermann, Alantha Newman, Heiko Röglin, Berthold Vöcking
Abstract. We consider bicriteria optimization problems and investigate the relationship between two standard approaches to solving them: (i) computing the Pareto curve and (ii) the so-called decision...
Decision making based on approximate and smoothed pareto curves (2005)
Heiner Ackermann, Alantha Newman, Heiko Röglin, Berthold Vöcking
We consider bicriteria optimization problems and investigate the relationship between two standard approaches to solving them: (i) computing the Pareto curve and (ii) the so-called decision maker’s...
Adaptive routing with stale information (2005)
Simon Fischer, Berthold Vöcking
We investigate adaptive routing policies for large networks in which agents reroute traffic based on old information. It is a well known and practically relevant problem that old information can lead...
Computing Equilibria for Congestion Games with (Im)perfect Information (2004)
Beier,Rene, Krysta,Piotr, Czumaj,Artur, Vöcking,Berthold
We study algorithmic questions concerning a basic microeconomic congestion game in which there is a single provider that offers a service to a set of potential customers. Each customer has a...
Typical Properties of Winners and Losers in Discrete Optimization (2004)
We present a probabilistic analysis for a large class of combinatorial optimization problems containing, e.g., all {\em binary optimization problems} defined by linear constraints and a linear...
Probabilistic Analysis of Knapsack Core Algorithms (2004)
We study the average-case performance of algorithms for the binary knapsack problem. Our focus lies on the analysis of so-called {\em core algorithms}, the predominant algorithmic concept used in...
Computing Equilibria for Congestion Games with (Im)perfect Information (2004)
Beier, Rene, Krysta, Piotr, Czumaj, Artur, Vöcking, Berthold
We study algorithmic questions concerning a basic microeconomic congestion game in which there is a single provider that offers a service to a set of potential customers. Each customer has a...
Typical Properties of Winners and Losers in Discrete Optimization (2004)
Beier, Rene, Vöcking, Berthold
We present a probabilistic analysis for a large class of combinatorial optimization problems containing, e.g., all {\em binary optimization problems} defined by linear constraints and a linear...
Probabilistic Analysis of Knapsack Core Algorithms (2004)
Beier, Rene, Vöcking, Berthold
We study the average-case performance of algorithms for the binary knapsack problem. Our focus lies on the analysis of so-called {\em core algorithms}, the predominant algorithmic concept used in...
Frugality and Truthfulness in Approximate Mechanism Design (2004)
Patrick Briest, Prof Dr, Berthold Vöcking, Patrick Briest, Patrick Briest
der Naturwissenschaftlich-Technischen Fakultäten (2004)
René Beier, Dekan Prof, Dr. Jörg Eschmeier, Vorsitzender Prof, Dr. Raimund Seidel, Erstgutachter Prof, ...
We investigate the performance of exact algorithms for hard optimization problems under random inputs. In particular, we prove various structural properties that lead to two general average-case...
On the Evolution of Selfish Routing (2004)
Simon Fischer, Berthold Vöcking
We introduce a model to study the temporal behaviour of selfish agents in networks. So far, most of the analysis of selfish routing is concerned with static properties of equilibria which is one of...
On the evolution of selfish routing (2004)
Simon Fischer, Berthold Vöcking
Abstract. We introduce a model to study the temporal behaviour of selfish agents in networks. So far, most of the analysis of selfish routing is concerned with static properties of equilibria which...
B.: An experimental study of random knapsack problems (2004)
Rene Beier, Rene Beier, Berthold Vöcking, Berthold Vöcking
Abstract. The size of the Pareto curve for the bicriteria version of the knapsack problem is polynomial on average. This has been shown for various random input distributions. We experimentally...
Probabilistic Analysis of Knapsack Core Algorithms (2004)
We study the average-case performance of algorithms for the binary knapsack problem. Our focus lies on the analysis of so-called core algorithms, the predominant algorithmic concept used in practice....
B.: An experimental study of random knapsack problems (2004)
Abstract. The size of the Pareto curve for the bicriteria version of the knapsack problem is polynomial on average. This has been shown for various random input distributions. We experimentally...
Computing Equilibria for Congestion Games with (Im)perfect Information (2004)
Beier, Rene, Krysta, Piotr, Czumaj, Artur, Vöcking, Berthold
We study algorithmic questions concerning a basic microeconomic congestion game in which there is a single provider that offers a service to a set of potential customers. Each customer has a...
Probabilistic Analysis of Knapsack Core Algorithms (2004)
Beier, Rene, Vöcking, Berthold
We study the average-case performance of algorithms for the binary knapsack problem. Our focus lies on the analysis of so-called {\em core algorithms}, the predominant algorithmic concept used in...
Typical Properties of Winners and Losers in Discrete Optimization (2004)
Beier, Rene, Vöcking, Berthold
We present a probabilistic analysis for a large class of combinatorial optimization problems containing, e.g., all {\em binary optimization problems} defined by linear constraints and a linear...
Data Management in Networks: Experimental Evaluation of a Provably Good Strategy (2003)
Krick,Christof, Räcke,Harald, Vöcking,Berthold, Westermann,Matthias
An experimental study of k-splittable scheduling for DNS-based traffic allocation (2003)
Agarwal,Amit, Agarwal,Tarun, Chopra,Sumit, Feldmann,Anja, Kammenhuber,Nils, Krysta,Piotr, ...
Random Knapsack in Expected Polynomial Time (2003)
In this paper, we present the first average-case analysis proving an expected polynomial running time for an exact algorithm for the 0/1 knapsack problem. In particular, we prove, for various input...
Randomized Pursuit-Evasion in Graphs (2003)
Adler,Micah, Räcke,Harald, Sivadasan,Naveen, Sohler,Christian, Vöcking,Berthold
Scheduling and Traffic Allocation for Tasks with Bounded Splittability (2003)
Krysta, Piotr, Sanders, Peter, Vöcking, Berthold, Rovan, Branislav, Vojtáš, Peter
Data Management in Networks: Experimental Evaluation of a Provably Good Strategy (2003)
Krick, Christof, Räcke, Harald, Vöcking, Berthold, Westermann, Matthias
An experimental study of k-splittable scheduling for DNS-based traffic allocation (2003)
Agarwal, Amit, Agarwal, Tarun, Chopra, Sumit, Feldmann, Anja, Kammenhuber, Nils, Krysta, Piotr, ...
Random Knapsack in Expected Polynomial Time (2003)
Beier, Rene, Vöcking, Berthold
In this paper, we present the first average-case analysis proving an expected polynomial running time for an exact algorithm for the 0/1 knapsack problem. In particular, we prove, for various input...
Randomized Pursuit-Evasion in Graphs (2003)
Adler, Micah, Räcke, Harald, Sivadasan, Naveen, Sohler, Christian, Vöcking, Berthold
An Experimental Study of k-Splittable Scheduling for DNS-Based Traffic Allocation (2003)
Amit Agarwal, Tarun Agarwal, Sumit Chopra, Anja Feldmann, Nils Kammenhuber, Piotr Krysta, ...
Abstract. The Internet domain name system (DNS) uses rotation of address lists to perform load distribution among replicated servers. We model this kind of load balancing mechanism in form of a set...
Random knapsack in expected polynomial time (2003)
In this paper, we present the first average-case analysis proving an expected polynomial running time for an exact algorithm for the 0/1 knapsack problem. In particular, we prove, for various input...
An Experimental Study of k-Splittable Scheduling for DNS-Based Traffic Allocation (2003)
Amit Agarwal, Tarun Agarwal, Sumit Chopra, Anja Feldmann, Nils Kammenhuber, Piotr Krysta, ...
Abstract. The Internet domain name system (DNS) uses rotation of address lists to perform load distribution among replicated servers. We model this kind of load balancing mechanism in form of a set...
Randomized Pursuit-Evasion in Graphs (2002)
Adler,Micah, Räcke,Harald, Sivadasan,Naveen, Sohler,Christian, Vöcking,Berthold
{ We analyze a randomized pursuit-evasion game on graphs. This game is played by two players, a {\em hunter} and a {\em rabbit}. Let $G$ be any connected, undirected graph with $n$ nodes. The game is...
Random Arc Allocation and Applications to Disks, Drums and DRAMs (2002)
Sanders, Peter, Vöcking, Berthold, Penttonen, Martti, Meineche Schmidt, Erik
Randomized Pursuit-Evasion in Graphs (2002)
Adler, Micah, Räcke, Harald, Sivadasan, Naveen, Sohler, Christian, Vöcking, Berthold, Widmayer, Peter, ...
{ We analyze a randomized pursuit-evasion game on graphs. This game is played by two players, a {\em hunter} and a {\em rabbit}. Let $G$ be any connected, undirected graph with $n$ nodes. The game is...
Randomized pursuit-evasion in graphs (2002)
Micah Adler, Harald Räcke, Naveen Sivadasan, Christian Sohler, Berthold Vöcking
We analyze a randomized pursuit-evasion game on graphs. This game is played by two players, a hunter and a rabbit. Let G be any connected, undirected graph with n nodes. The game is played in rounds...
Tight Bounds for Worst-Case Equilibria (2002)
Artur Czumaj New, Artur Czumaj, Berthold Vöcking
We study the problem of traffic routing in non-cooperative networks. In such networks, users may follow selfish strategies to optimize their own performance measure and therefore their behavior does...
Tight Bounds for Worst-Case Equilibria (2002)
Artur Czumaj, Berthold Vöcking
We study the problem of traffic routing in non-cooperative networks. In such networks, users may follow selfish strategies to optimize their own performance measure and therefore their behavior does...
Randomized pursuit-evasion in graphs (2002)
Micah Adler, Harald Räcke, Naveen Sivadasan, Christian Sohler, Berthold Vöcking
Abstract. We analyze a randomized pursuit-evasion game on graphs. This game is played by two players, a hunter and a rabbit. Let G be any connected, undirected graph with n nodes. The game is played...
Randomized pursuit-evasion in graphs (2002)
Micah Adler, Harald Räcke, Naveen Sivadasan, Christian Sohler, Berthold Vöcking
ns,voecking� Abstract. We analyze a randomized pursuit-evasion game on graphs. This game is played by two players, a hunter and a rabbit. Let � be any connected, undirected graph with � nodes....
Randomized pursuit-evasion in graphs (2002)
Micah Adler, Harald Räcke, Naveen Sivadasan, Christian Sohler, Berthold Vöcking
Abstract. We analyze a randomized pursuit-evasion game on graphs. This game is played by two players, a hunter and a rabbit. Let G be any connected, undirected graph with n nodes. The game is played...
Randomized pursuit-evasion in graphs (2002)
Micah Adler, Harald Räcke, Naveen Sivadasan, Christian Sohler, Berthold Vöcking
We analyze a randomized pursuit-evasion game on graphs. This game is played by two players, a hunter and a rabbit. Let be any connected, undirected graph with nodes. The game is played in rounds and...
Balanced Allocations: The Heavily Loaded Case (2000)
Petra Berenbrink, Artur Czumaj, Angelika Steger, Berthold Vöcking
We investigate load balancing processes based on the multiplechoice paradigm. In these randomized processes m balls are inserted into n bins. In the classical single-choice variant each ball is...
How Asymmetry Helps Load Balancing (1999)
This paper deals with balls and bins processes related to randomized load balancing, dynamic resource allocation, and hashing. Suppose ¡ balls have to be assigned to ¡ bins, where each ball has to...
Provably Good and Practical Strategies for Non-Uniform Data Management in Networks (1999)
Berthold Vöcking, Matthias Westermann
Abstract. This paper deals with the on-line allocation of shared data objects to the local memory modules of the nodes in a network. We assume that the data is organized in indivisible objects such...
Provably Good and Practical Strategies for Non-Uniform Data Management in Networks (1999)
Berthold Vöcking, Matthias Westermann
. This paper deals with the on-line allocation of shared data objects to the local memory modules of the nodes in a network. We assume that the data is organized in indivisible objects such as files,...
Data Management in Networks: Experimental Evaluation of a Provably Good Strategy (1999)
Christof Krick, Harald Räcke, Berthold Vöcking, Matthias Westermann
This paper deals with data management for parallel and distributed systems in which the computing nodes are connected by a relatively sparse network. We present the DIVA (Distributed Variables)...
How Asymmetry Helps Load Balancing (1999)
This paper deals with balls and bins processes related to randomized load balancing, dynamic resource allocation, and hashing. Suppose n balls have to be assigned to n bins, where each ball has to be...
Approximating Multicast Congestion (1999)
Santosh Vempala, Berthold Vöcking
. We present a randomized algorithm for approximating multicast congestion (a generalization of path congestion) to within O(log n) times the best possible. Our main tools are a linear programming...
Provably Good and Practical Strategies for Non-Uniform Data Management in Networks (1999)
Berthold Vöcking, Matthias Westermann
. This paper deals with the on-line allocation of shared data objects to the local memory modules of the nodes in a network. We assume that the data is organized in indivisible objects such as files,...
Richard Cole, Bruce M. Maggs, Michael Mitzenmacher, Andréa W. Richa, Klaus Schröder, ...
In this paper we study randomized algorithms for circuit switching on multistage networks related to the butterfly. We devise algorithms that route messages by constructing circuits (or paths) for...
Richard Cole, Bruce M. Maggs, Michael Mitzenmacher, Friedhelm Meyer, Heide Michael Mitzenmacher, ...
In this paper we study randomized algorithms for circuit switching on multistage networks related to the butterfly. We devise algorithms that route messages by constructing circuits (or paths) for...
Universal Continuous Routing Strategies (1997)
Christian Scheideler, Berthold Vöcking
We analyze universal routing protocols, that is, protocols that can be used for any communication pattern in any network, under a stochastic model of continuous message generation. In particular, we...
Exploiting Locality for Data Management in Systems of Limited Bandwidth (1997)
Bruce M. Maggs, Berthold Vöcking, Matthias Westermann
This paper deals with data management in computer systems in which the computing nodes are connected by a relatively sparse network. We consider the problem of placing and accessing a set of shared...
Static and Dynamic Data Management in Networks (1997)
. We survey strategies for distributing shared objects in large parallel and distributed systems. Examples of such objects are global variables in a parallel program, pages or cache lines in a...
Improved Routing and Sorting on Multibutterflies (1997)
Bruce M. Maggs, Berthold Vöcking
This paper shows that an N-node AKS network (as described by Paterson) can be embedded in a 3N 2 -node twinbutterfly network (i.e., a multibutterfly constructed by superimposing two butterfly...
Improved Routing and Sorting on Multibutterflies (1997)
Bruce M. Maggs, Berthold Vöcking
This paper shows that an N-node AKS network (as described by Paterson) can be embedded in a 3N 2 -node degree-8 multibutterfly network with load 1, congestion 1, and dilation 2. The result has...
Exploiting Locality for Data Management in Systems of Limited Bandwidth (1997)
Bruce M. Maggs, Berthold Vöcking, Matthias Westermann
This paper deals with data management in computer systems in which the computing nodes are connected by a relatively sparse network. We consider the problem of placing and accessing a set of shared...
Improved Routing and Sorting on Multibutterflies (1996)
Bruce M. Maggs, Berthold Vöcking
This paper shows that an N-node AKS network (as described by Paterson) can be embedded in a 3N 2 -node degree-8 multibutterfly network with load 1, congestion 1, and dilation 2. The result has...
Universal Algorithms for Store-and-Forward and Wormhole Routing (1996)
Robert Cypher, Christian Scheideler, Berthold Vöcking
In this paper we present routing algorithms that are universal in the sense that they route messages along arbitrary (simple) paths in arbitrary networks. The algorithms are analyzed in terms of the...
Universal Store-and-Forward Routing (1996)
We introduce an on-line protocol which routes any set of N packets along shortest paths with congestion C through an arbitrary network G in O(C + diam(G) + log N) steps, with high probability. This...