Arrow Research search

Author name cluster

Berthold Vöcking

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

30 papers
2 author rows

Possible papers

30

TCS Journal 2014 Journal Article

Comparative study of approximation algorithms and heuristics for SINR scheduling with power control

  • Lukas Belke
  • Thomas Kesselheim
  • Arie M.C.A. Koster
  • Berthold Vöcking

Various recent theoretical studies have achieved considerable progress in understanding combined link scheduling and power control in wireless networks with SINR constraints. These analyses were mainly focused on designing and analyzing approximation algorithms with provable approximation guarantees. While these studies revealed interesting effects from a theoretical perspective, so far there has not been a systematic evaluation of the theoretical results in simulations. In this paper, we examine the performance of various approximation algorithms and heuristics for the common scheduling problems on instances generated by different random network models, e. g. , taking clustering effects into account. Using (mixed) integer linear programming, we are able to compute the theoretical optima for some of these instances such that the performance of the different algorithms can be compared with these optima. The simulations support the practical relevance of the theoretical findings. For example, setting transmission powers by a square-root power assignment, the network's capacity increases significantly in comparison to uniform power assignments. Furthermore, the developed approximation algorithms are able to exploit this gap providing in general a better performance than any algorithm using uniform transmission powers, even with unlimited computational power. The obtained results are robust against changes in parameters and network generation models.

Details DOI

STOC Conference 2014 Conference Paper

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

  • Thomas Kesselheim
  • Klaus Radke
  • Andreas Tönnis
  • Berthold Vöcking

We study packing LPs in an online model where the columns are presented to the algorithm in random order. This natural problem was investigated in various recent studies motivated, e.g., by online ad allocations and yield management where rows correspond to resources and columns to requests specifying demands for resources. Our main contribution is a 1 -- O (√(log d/B))-competitive online algorithm. Here d denotes the column sparsity , i.e., the maximum number of resources that occur in a single column, and B denotes the capacity ratio B , i.e., the ratio between the capacity of a resource and the maximum demand for this resource. In other words, we achieve a (1--ε)-approximation if the capacity ratio satisfies B=Ω(logd/ε 2 ), which is known to be best-possible for any (randomized) online algorithms. Our result improves exponentially on previous work with respect to the capacity ratio. In contrast to existing results on packing LP problems, our algorithm does not use dual prices to guide the allocation of resources over time. Instead, the algorithm simply solves, for each request, a scaled version of the partially known primal program and randomly rounds the obtained fractional solution to obtain an integral allocation for this request. We show that this simple algorithmic technique is not restricted to packing LPs with large capacity ratio of order Ω(log d ), but it also yields close-to-optimal competitive ratios if the capacity ratio is bounded by a constant. In particular, we prove an upper bound on the competitive ratio of Ω( d --1/( B --1) ), for any B ≥ 2. In addition, we show that our approach can be combined with VCG payments and obtain an incentive compatible (1 -- ε)-competitive mechanism for packing LPs with B = Ω(log m /ε; 2 ), where m is the number of constraints. Finally, we apply our technique to the generalized assignment problem for which we obtain the first online algorithm with competitive ratio O (1).

Details

TCS Journal 2011 Journal Article

Improved algorithms for latency minimization in wireless networks

  • Alexander Fanghänel
  • Thomas Kesselheim
  • Berthold Vöcking

In the interference scheduling problem, one is given a set of n communication requests described by source–destination pairs of nodes from a metric space. The nodes correspond to devices in a wireless network. Each pair must be assigned a power level and a color such that the pairs in each color class can communicate simultaneously at the specified power levels. The feasibility of simultaneous communication within a color class is defined in terms of the Signal to Interference plus Noise Ratio (SINR) that compares the strength of a signal at a receiver to the sum of the strengths of other signals. The objective is to minimize the number of colors as this corresponds to the time needed to schedule all requests. We introduce an instance-based measure of interference, denoted by I, that enables us to improve on previous results for the interference scheduling problem. We prove the upper and lower bounds in terms of I on the number of steps needed for scheduling a set of requests. For general power assignments, we prove a lower bound of Ω ( I / ( log Δ log n ) ) steps, where Δ denotes the aspect ratio of the metric. When restricting to the two-dimensional Euclidean space (as in the previous work) the bound improves to Ω ( I / log Δ ). Alternatively, when restricting to linear power assignments, the lower bound improves even to Ω ( I ). The lower bounds are complemented by an efficient algorithm computing a schedule for linear power assignments using only O ( I log n ) steps. A more sophisticated algorithm computes a schedule using even only O ( I + log 2 n ) steps. For dense instances in the two-dimensional Euclidean space, this gives a constant factor approximation for scheduling under linear power assignments, which shows that the price for using linear (and, hence, energy-efficient) power assignments is bounded by a factor of O ( log Δ ). In addition, we extend these results for single-hop scheduling to multi-hop scheduling and combined scheduling and routing problems, where our analysis generalizes the previous results towards general metrics and improves on the previous approximation factors.

Details DOI

TCS Journal 2009 Journal Article

Adaptive routing with stale information

  • 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, each one of an infinite number of agents controls an infinitesimal amount of flow, thus contributing to a network flow which induces latency. In our dynamic extension of this model, agents are activated in a concurrent and asynchronous fashion and may reroute their flow with the aim of reducing their sustained latency. It is a well-known problem that in settings where latency information is not always up-to-date, such behaviour may lead to oscillation effects which seriously harm network performance. Two quantities determine the difficulty of avoiding oscillation: the steepness of the latency functions and the maximum possible age of the information T. In this work we ask for conditions that the rerouting policies must adhere to in order to converge to an equilibrium despite the information being stale. We consider simple policies which sample another path in a first step and then migrate from the current path to the new one with a probability that is a function of the anticipated latency gain. In fact we can show that our class of policies guarantees convergence if the latter migration probability function satisfies a certain smoothness condition that resembles Lipschitz continuity. It turns out that for smooth adaptation policies where the migration probability is chosen small enough relative to the inverse of the steepness of the latency functions and T, the population actually converges to an equilibrium. In addition, we analyse the speed of convergence towards approximate equilibria of two specific variants of smooth adaptive routing policies, e. g. , for a replication policy adopted from evolutionary game theory.

Details DOI

TCS Journal 2009 Journal Article

Pure Nash equilibria in player-specific and weighted congestion games

  • 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 exist pure equilibria for both of these variants in the case of singleton congestion games, i. e. , if the players’ strategy spaces contain only sets of cardinality one. In this paper, we investigate how far such a property on the players’ strategy spaces guaranteeing the existence of pure equilibria can be extended. We show that both weighted and player-specific congestion games admit pure equilibria in the case of matroid congestion games, i. e. , if the strategy space of each player consists of the bases of a matroid on the set of resources. We also show that the matroid property is the maximal property that guarantees pure equilibria without taking into account how the strategy spaces of different players are interweaved. Additionally, our analysis of player-specific matroid congestion games yields a polynomial time algorithm for computing pure equilibria. We also address questions related to the convergence time of such games. For player-specific matroid congestion games, in which the best response dynamics may cycle, we show that from every state there exists a short sequences of better responses to an equilibrium. For weighted matroid congestion games, we present a superpolynomial lower bound on the convergence time of the best response dynamics showing that players do not even converge in pseudopolynomial time.

Details DOI

TCS Journal 2007 Journal Article

Decision-making based on approximate and smoothed Pareto curves

  • 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 approach in which both criteria are combined into a single (usually nonlinear) objective function. Previous work by Papadimitriou and Yannakakis showed how to efficiently approximate the Pareto curve for problems like Shortest Path, Spanning Tree, and Perfect Matching. We wish to determine for which classes of combined objective functions the approximate Pareto curve also yields an approximate solution to the decision maker’s problem. We show that an FPTAS for the Pareto curve also gives an FPTAS for the decision-maker’s problem if the combined objective function is growth bounded like a quasi-polynomial function. If the objective function, however, shows exponential growth then the decision-maker’s problem is NP-hard to approximate within any polynomial factor. In order to bypass these limitations of approximate decision making, we turn our attention to Pareto curves in the probabilistic framework of smoothed analysis. We show that in a smoothed model, we can efficiently generate the (complete and exact) Pareto curve with a small failure probability if there exists an algorithm for generating the Pareto curve whose worst-case running time is pseudopolynomial. This way, we can solve the decision-maker’s problem w. r. t. any non-decreasing objective function for randomly perturbed instances of, e. g. Shortest Path, Spanning Tree, and Perfect Matching.

Details DOI

TCS Journal 2007 Journal Article

On the structure and complexity of worst-case equilibria

  • 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 by several authors that the fully mixed Nash equilibrium (FMNE) is the worst possible w. r. t. the expected maximum load over all machines. Assuming the validity of this conjecture, computing a worst-case Nash equilibrium for a given instance was trivial, and approximating the Price of Anarchy for this instance would be possible by approximating the expected social cost of the FMNE by applying a known FPRAS. We present a counter-example to this conjecture showing that fully mixed Nash equilibria cannot be used to approximate the Price of Anarchy. We show that the factor between the social cost of the worst Nash equilibrium and the social cost of the FMNE can be as large as the Price of Anarchy itself, up to a constant factor. In addition, we present an algorithm that constructs so-called concentrated equilibria that approximate the worst-case Nash equilibria within constant factors.

Details DOI

FOCS Conference 2006 Conference Paper

On the Impact of Combinatorial Structure on Congestion Games

  • 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 investigate which properties of the strategy spaces of individual players ensure a polynomial convergence time. We show, if the strategy space of each player consists of the bases of a matroid over the set of resources, then the lengths of all best response sequences are polynomially bounded in the number of players and resources. We can also prove that this result is tight, that is, the matroid property is a necessary and sufficient condition on the players' strategy spaces for guaranteeing polynomial time convergence to a Nash equilibrium. In addition, we present an approach that enables us to devise hardness proofs for various kinds of combinatorial games, including first results about the hardness of market sharing games and congestion games for overlay network design. Our approach also yields a short proof for the PLS-completeness of network congestion games. In particular, we can show that network congestion games are PLS-complete for directed and undirected networks even in case of linear latency functions

Details

STOC Conference 2005 Conference Paper

Approximation techniques for utilitarian mechanism design

  • Patrick Briest
  • Piotr Krysta
  • Berthold Vöcking

This paper deals with the design of efficiently computable incentive compatible, or truthful, mechanisms for combinatorial optimization problems with multi-parameter agents. We focus on approximation algorithms for NP-hard mechanism design problems. These algorithms need to satisfy certain monotonicity properties to ensure truthfulness. Since most of the known approximation techniques do not fulfill these properties, we study alternative techniques.Our first contribution is a quite general method to transform a pseudopolynomial algorithm into a monotone FPTAS. This can be applied to various problems like, e.g., knapsack , constrained shortest path , or job scheduling with deadlines . For example, the monotone FPTAS for the knapsack problem gives a very efficient, truthful mechanism for single-minded multi-unit auctions . The best previous result for such auctions was a 2-approximation. In addition, we present a monotone PTAS for the generalized assignment problem with any bounded number of parameters per agent.The most efficient way to solve packing integer programs (PIPs) is LP-based randomized rounding, which also is in general not monotone. We show that primal-dual greedy algorithms achieve almost the same approximation ratios for PIPs as randomized rounding. The advantage is that these algorithms are inherently monotone. This way, we can significantly improve the approximation ratios of truthful mechanisms for various fundamental mechanism design problems like single-minded combinatorial auctions (CAs) , unsplittable flow routing and multicast routing . Our approximation algorithms can also be used for the winner determination in CAs with general bidders specifying their bids through an oracle.

Details

STOC Conference 2004 Conference Paper

Typical properties of winners and losers in discrete optimization

  • René Beier
  • Berthold Vöcking

We present a probabilistic analysis for a large class of combinatorial optimization problems containing, e. g., all binary optimization problems defined by linear constraints and a linear objective function over (0,1) n . By parameterizing which constraints are of stochastic and which are of adversarial nature, we obtain a semi-random input model that enables us to do a general average-case analysis for a large class of optimization problems while at the same time taking care for the combinatorial structure of individual problems. Our analysis covers various probability distributions for the choice of the stochastic numbers and includes smoothed analysis with Gaussian and other kinds of perturbation models as a special case. In fact, we can exactly characterize the smoothed complexity of optimization problems in terms of their random worst-case complexity.A binary optimization problem has a polynomial smoothed complexity if and only if it has a pseudopolynomial complexity. Our analysis is centered around structural properties of binary optimization problems, called winner , loser , and feasibility gaps . We show, when the coefficients of the objective function and/or some of the constraints are stochastic, then there usually exist a polynomial n -Ω(1) gap between the best and the second best solution as well as a polynomial slack to the boundary of the constraints. Similar to the condition number for linear programming, these gaps describe the sensitivity of the optimal solution to slight perturbations of the input and can be used to bound the necessary accuracy as well as the complexity for solving an instance. We exploit the gaps in form of an adaptive rounding scheme increasing the accuracy of calculation until the optimal solution is found. The strength of our techniques is illustrated by applications to various NP-hard optimization problems from mathematical programming, network design, and scheduling for which we obtain the the first algorithms with polynomial average-case/smoothed complexity.

Details

MFCS Conference 2003 Conference Paper

Scheduling and Traffic Allocation for Tasks with Bounded Splittability

  • Piotr Krysta
  • Peter Sanders 0001
  • Berthold Vöcking

Abstract We investigate variants of the problem of scheduling tasks on uniformly related machines to minimize the makespan. In the k -splittable scheduling problem each task can be broken into at most k ≥ 2 pieces to be assigned to different machines. In a more general SAC problem each task j has its own splittability parameter k j ≥ 2. These problems are NP -hard and previous research focuses mainly on approximation algorithms. Our motivation to study these scheduling problems is traffic allocation for server farms based on a variant of the Internet Domain Name Service (DNS) that uses a stochastic splitting of request streams. We show that the traffic allocation problem with standard latency functions from Queueing Theory cannot be approximated in polynomial time within any finite factor because of the extreme behavior of these functions. Our main result is a polynomial time, exact algorithm for the k -splittable scheduling problem as well as the SAC problem with a fixed number of machines. The running time of our algorithm is exponential in the number of machines but is only linear in the number of tasks. This result is the first proof that bounded splittability reduces the complexity of scheduling as the unsplittable scheduling is known to be NP -hard already for two machines. Furthermore, since our algorithm solves the scheduling problem exactly, it also solves the traffic allocation problem.

Details

FOCS Conference 2000 Conference Paper

Randomized Rumor Spreading

  • Richard M. Karp
  • Christian Schindelhauer
  • Scott Shenker
  • Berthold Vöcking

Investigates the class of epidemic algorithms that are commonly used for the lazy transmission of updates to distributed copies of a database. These algorithms use a simple randomized communication mechanism to ensure robustness. Suppose n players communicate in parallel rounds in each of which every player calls a randomly selected communication partner. In every round, players can generate rumors (updates) that are to be distributed among all players. Whenever communication is established between two players, each one must decide which of the rumors to transmit. The major problem is that players might not know which rumors their partners have already received. For example, a standard algorithm forwarding each rumor form the calling to the called players for /spl Theta/(ln n) rounds needs to transmit the rumor /spl Theta/(n ln n) times in order to ensure that every player finally receives the rumor with high probability. We investigate whether such a large communication overhead is inherent to epidemic algorithms. On the positive side, we show that the communication overhead can be reduced significantly. We give an algorithm using only O(n ln ln n) transmissions and O(ln n) rounds. In addition, we prove the robustness of this algorithm. On the negative side, we show that any address-oblivious algorithm needs to send /spl Omega/(n ln ln n) messages for each rumor, regardless of the number of rounds. Furthermore, we give a general lower bound showing that time and communication optimality cannot be achieved simultaneously using random phone calls, i. e. every algorithm that distributes a rumor in O(ln n) rounds needs /spl omega/(n) transmissions.

Details

FOCS Conference 1999 Conference Paper

How Asymmetry Helps Load Balancing

  • Berthold Vöcking

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 placed without knowledge about the distribution of previously placed balls. The goal is to achieve an allocation that is as even as possible so that no bin gets much more balls than the average. A well known and good solution for this problem is to choose d possible locations for each ball at random, to look into each of these bins, and to place the ball into the least full among these bins. This class of algorithms has been investigated intensively in the past but almost all previous analyses assume that the d locations for each ball are chosen uniform and independently at random from the set of all bins. We investigate whether a non-uniform and possibly dependent choice of the d locations for a ball can improve the load balancing. Three types of selections are distinguished: 1) uniform and independent 2) non-uniform and independent 3) non-uniform and dependent. Our first result shows that choosing the locations in a non-uniform way (type 2) results in a better load balancing than choosing the locations uniformly (type 1). Surprising, this smooth load balancing is obtained by an algorithm called "Always-Go-Left" which creates an asymmetric assignment of the balls to the bins. Our second result is a lower bound on the smallest-possible maximum load that can be achieved by any allocation algorithm of type 1, 2, or 3.

Details

FOCS Conference 1997 Conference Paper

Exploiting Locality for Data Management in Systems of Limited Bandwidth

  • Bruce M. Maggs
  • Friedhelm Meyer auf der Heide
  • 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 objects that are read and written from the nodes in the network. These objects are, e. g. , global variables in a parallel program, pages or cache lines in a virtual shared memory system, shared files in a distributed file system, or pages in the World Wide Web. A data management strategy consists of a placement strategy that maps the objects (possibly dynamically and with redundancy) to the nodes, and an access strategy that describes how reads and writes are handled by the system (including the routing). We investigate static and dynamic data management strategies.

Details