We study packing linear programs (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(\sqrt{\nicefrac{(\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-\epsilon)$-approximation if the capacity ratio satisfies $B=\Omega(\frac{\log d}{\epsilon^2})$, which is known to be the 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 $\Omega(\log d)$, but 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 $\Omega(d^{\nicefrac{-1}{(B-1)}})$ for any $B\geq2$. In addition, we show that our approach can be combined with VCG payments and obtain an incentive-compatible $(1-\epsilon)$-competitive mechanism for packing LPs with $B=\Omega(\frac{\log m}{\epsilon^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)$.

2-Opt is a simple local search heuristic for the traveling salesperson problem that performs very well in experiments with respect to both running time and solution quality. In contrast to this, there are instances on which 2-Opt may need an exponential number of steps to reach a local optimum. To understand why 2-Opt usually finds local optima quickly in experiments, we study its expected running time in the model of smoothed analysis, which can be considered as a less-pessimistic variant of worst-case analysis in which the adversarial input is subject to a small amount of random noise. In our probabilistic input model, an adversary chooses an arbitrary graph G and a probability density function for each edge according to which its length is chosen. We prove that in this model the expected number of local improvements is O (mnϕ ċ 16 √ln m )= m 1+ o (1) nϕ , where n and m denote the number of vertices and edges of G , respectively, and ϕ denotes an upper bound on the density functions.

One of the most powerful algorithmic techniques for truthful mechanism design are maximal-in-distributional-range (MIDR) mechanisms. Unfortunately, many algorithms using this paradigm rely on heavy algorithmic machinery and require the ellipsoid method or (approximate) solution of convex programs. In this paper, we present a simple and natural correlated rounding technique for designing mechanisms that are truthful in expectation. Our technique is elementary and can be implemented quickly. The main property we rely on is that the domain offers fractional optimum solutions with a tree structure. In auctions based on the generalized assignment problem, each bidder has a publicly known knapsack constraint that captures the subsets of items that are of value to him. He has a private valuation for each item and strives to maximize the value of assigned items minus payment. For this domain we design a mechanism for social welfare maximization. Our technique gives a truthful 2-approximate MIDR mechanism without using the ellipsoid method or convex programming. In contrast to some previous work, our mechanism achieves exact truthfulness.

With the availability of advanced MPSoC and emerging Dynamic RAM (DRAM) interface technologies, an optimal allocation of logical data buffers to physical memory cannot be handled manually anymore due to the huge design space. An allocation does not only need to decide between an on-or off-chip memory, but also needs to take an increasing number of available memory channels, different bandwidth capacities and several routing possibilities into account. We formalize this problem and introduce a Mixed Integer Linear Programming (MILP) model based on two different optimization criteria. We implement the MILP model into a retargetable tool and present a case study with representative data of the Long-Term-Evolution (LTE) standard to show the real-life applicability of our approach.

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.

Abstract 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 approximation ratio. There are numerous experimental studies on the performance of 2-Opt. However, the theoretical knowledge about this heuristic is still very limited. Not even its worst case running time on 2-dimensional Euclidean instances was known so far. We clarify this issue by presenting, for every $p\in\mathbb{N}$ , a family of L p instances on which 2-Opt can take an exponential number of steps. Previous probabilistic analyses were restricted to instances in which n points are placed uniformly at random in the unit square [0,1] 2 , where it was shown that the expected number of steps is bounded by $\tilde{O}(n^{10})$ for Euclidean instances. We consider a more advanced model of probabilistic instances in which the points can be placed independently according to general distributions on [0,1] d , for an arbitrary d ≥2. In particular, we allow different distributions for different points. We study the expected number of local improvements in terms of the number n of points and the maximal density ϕ of the probability distributions. We show an upper bound on the expected length of any 2-Opt improvement path of $\tilde{O}(n^{4+1/3}\cdot\phi^{8/3})$ . When starting with an initial tour computed by an insertion heuristic, the upper bound on the expected number of steps improves even to $\tilde{O}(n^{4+1/3-1/d}\cdot\phi^{8/3})$ . If the distances are measured according to the Manhattan metric, then the expected number of steps is bounded by $\tilde{O}(n^{4-1/d}\cdot\phi)$ . In addition, we prove an upper bound of $O(\sqrt[d]{\phi})$ on the expected approximation factor with respect to all L p metrics. Let us remark that our probabilistic analysis covers as special cases the uniform input model with ϕ =1 and a smoothed analysis with Gaussian perturbations of standard deviation σ with ϕ ∼1/ σ d .

We study combinatorial auctions for secondary spectrum markets, where short-term communication licenses are sold to wireless nodes. Channels can be assigned to multiple bidders according to interference constraints captured by a conflict graph. We suggest a novel approach to such combinatorial auctions using a graph parameter called inductive independence number. We achieve good approximation results by showing that interference constraints for wireless networks imply a bounded inductive independence number. For example, in the physical model the factor becomes O (√ k log 2 n ) for n bidders and k channels. Our algorithms can be turned into incentive-compatible mechanisms for bidders with arbitrary valuations.

We consider truthfulness concepts for auctions with payments based on first- and second-order stochastic dominance. We assume bidders consider wealth in standard quasi-linear form as valuation minus payments. Additionally, they are sensitive to risk in the distribution of wealth stemming from randomized mechanisms. First- and second-order stochastic dominance are well-known to capture risk-sensitivity, and we apply these concepts to capture truth-telling incentives for bidders.

We present a randomized, polynomial-time approximation scheme for multi-unit auctions. Our mechanism is truthful in the universal sense, i.e., a distribution over deterministically truthful mechanisms. Previously known approximation schemes were truthful in expectation which is a weaker notion of truthfulness assuming risk neutral bidders. The existence of a universally truthful approximation scheme was questioned by previous work showing that multi-unit auctions with certain technical restrictions on their output do not admit a polynomial-time, universally truthful mechanism with approximation factor better than two. Our new mechanism employs VCG payments in a non-standard way: The deterministic mechanisms underlying our universally truthful approximation scheme are not maximal in range and do not belong to the class of affine maximizers which, on a first view, seems to contradict previous characterizations of VCG-based mechanisms. Instead, each of these deterministic mechanisms is composed of a collection of affine maximizers, one for each bidder. This yields a subjective variant of VCG in which payments for different bidders are defined on the basis of possibly different affine maximizers.

Abstract We consider the problem of computing ε ‐approximate Nash equilibria in network congestion games. The general problem is known to be PLS‐complete for every ε > 0, but the reductions are based on artificial and steep delay functions with the property that already two players using the same resource cause a delay that is significantly larger than the delay for a single player. We consider network congestion games with delay functions such as polynomials, exponential functions, and functions from queuing theory. We analyse which approximation guarantees can be achieved for such congestion games by the method of randomized rounding. Our results show that the success of this method depends on different criteria depending on the class of functions considered. For example, queuing theoretical functions admit good approximations if the equilibrium load of every resource is bounded away appropriately from its capacity. © 2011 Wiley Periodicals, Inc. NETWORKS, Vol. 2011

We study the existence and computational complexity of coalitional stability concepts based on social networks. Our concepts represent a natural and rich combinatorial generalization of a recent notion termed partition equilibrium [5]. We assume that players in a strategic game are embedded in a social (or, communication) network, and there are coordination constraints defining the set of coalitions that can jointly deviate in the game. A main feature of our approach is that players act in a fashion to ignore potentially profitable (group) deviations if the change in their strategy may cause a decrease of utility to their neighbors in the network. We explore the properties of such considerate equilibria in application to the celebrated class of resource selection games (RSGs). Our main result proves existence of a super-strong considerate equilibrium in all symmetric RSGs with strictly increasing delays, for any social network among the players and feasible coalitions represented by the set of cliques. The existence proof is constructive and yields an efficient algorithm. In fact, the computed considerate equilibrium is a Nash equilibrium for a standard RSG, thus showing that there exists a state that is stable against selfish and considerate behavior simultaneously. Furthermore, we provide results on convergence of considerate dynamics.

We study combinatorial auctions for the secondary spectrum market. In this market, short-term licenses shall be given to wireless nodes for communication in their local neighborhood. In contrast to the primary market, channels can be assigned to multiple bidders, provided that the corresponding devices are well separated such that the interference is sufficiently low. Interference conflicts are described in terms of a conflict graph in which the nodes represent the bidders and the edges represent conflicts such that the feasible allocations for a channel correspond to the independent sets in the conflict graph.

Various economic interactions can be modeled as two-sided markets. A central solution concept for these markets is stable matchings, introduced by Gale and Shapley. It is well known that stable matchings can be computed in polynomial time, but many real-life markets lack a central authority to match agents. In those markets, matchings are formed by actions of self-interested agents. Knuth introduced uncoordinated two-sided markets and showed that the uncoordinated better response dynamics may cycle. However, Roth and Vande Vate showed that the random better response dynamics converges to a stable matching with probability one, but they did not address the question of convergence time. In this paper, we give an exponential lower bound for the convergence time of the random better response dynamics in two-sided markets. We also extend the results for the better response dynamics to the best response dynamics; i.e., we present a cycle of best responses and prove that the random best response dynamics converges to a stable matching with probability one, but its convergence time is exponential. Additionally, we identify the special class of correlated matroid two-sided markets with real-life applications for which we prove that the random best response dynamics converges in expected polynomial time.

This paper deals with the design of efficiently computable incentive-compatible mechanisms for combinatorial optimization problems with single-minded agents each possibly having multiple private parameters. 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 fully polynomial time approximation scheme (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 multiunit auctions. The best previous result for such auctions was a 2-appro-xi-ma-tion. In addition, we present a monotone PTAS for the generalized assignment problem with any constant number of private parameters per agent. The most efficient way to solve packing integer programs (PIPs) is linear programming–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 primal-dual approximation algorithms can also be used for the winner determination in CAs with general bidders specifying their bids through an oracle.

We present and analyze simple distributed contention resolution protocols for wireless networks. In our setting, one is given n pairs of senders and receivers located in a metric space. Each sender wants to transmit a signal to its receiver at a prespecified power level, e.g., all senders use the same, uniform power level as it is typically implemented in practice. Our analysis is based on the physical model in which the success of a transmission depends on the Signal-to-Interference-plus-Noise-Ratio (SINR). The objective is to minimize the number of time slots until all signals are successfully transmitted.

In this paper we study a dynamic version of capacity maximization is the physical model of wireless communication. In our model, requests for connections between pairs of points in Euclidean space of constant dimension d arrive iteratively over time. When a new request arrives, an online algorithm needs to decide whether or not to accept the request and to assign one out of k channels and a transmission power to the channel. Accepted requests must satisfy constraints on the signal-to-interference-plus-noise (SINR) ratio. The objective is to maximize the number of accepted requests.

We study the price of selfish routing in noncooperative networks like the Internet. In particular, we investigate the price of selfish routing using the price of anarchy (a.k.a. the coordination ratio) and other (e.g., bicriteria) measures in the recently introduced game theoretic parallel links network model of Koutsoupias and Papadimitriou. We generalize this model toward general, monotone families of cost functions and cost functions from queueing theory. A summary of our main results for general, monotone cost functions is as follows: 1. We give an exact characterization of all cost functions having a bounded/unbounded price of anarchy. For example, the price of anarchy for cost functions describing the expected delay in queueing systems is unbounded. 2. We show that an unbounded price of anarchy implies an extremely high performance degradation under bicriteria measures. In fact, the price of selfish routing can be as high as a bandwidth degradation by a factor that is linear in the network size. 3. We separate the game theoretic (integral) allocation model from the (fractional) flow model by demonstrating that even a very small or negligible amount of integrality can lead to a dramatic performance degradation. 4. We unify recent results on selfish routing under different objectives by showing that an unbounded price of anarchy under the min-max objective implies an unbounded price of anarchy under the average cost objective and vice versa. Our special focus lies on cost functions describing the behavior of Web servers that can open only a limited number of Transmission Control Protocol (TCP) connections. In particular, we compare the performance of queueing systems that serve all incoming requests with servers that reject requests in case of overload. Our analysis indicates that all queueing systems without rejection cannot give any reasonable guarantee on the expected delay of requests under selfish routing even when the injected load is far away from the capacity of the system. In contrast, Web server farms that are allowed to reject requests can guarantee a high quality of service for every individual request stream even under relatively high injection rates.

We study the question of whether a large population of agents in a traffic network is able to converge to an equilibrium quickly. To that end, we consider a round-based variant of the Wardrop model. Every agent is allowed to reroute its traffic once in a while with the aim of finding a path with minimal latency. As a first result we find that using a replication policy which allows agents to imitate others gives rise to a bicriterial approximate equilibrium very quickly. In particular, the time bound depends logarithmically on the ratio between minimum and maximum latency but is otherwise independent of the network size. In the single-commodity case, this bicriteria approximate equilibrium has an intuitive interpretation as a state in which almost all agents are almost happy. This kind of approximate equilibrium, however, is transient. In order to reach a global approximation, we need to add an exploration component which enables the agents to explore the strategy space independently of the other agents. Although it can be shown that, when used exclusively, exploration policies imply an exponential lower bound, applying exploration carefully allows the population to approximate the global Wardrop equilibrium in polynomial time. Since the distributed and concurrent fashion of our policies bears the risk of oscillating behavior, we must take into account the steepness of the latency functions. We show that the relevant parameter is elasticity, a parameter closely related to the polynomial degree. This improves significantly over earlier results which depend on the absolute slope and therefore have a pseudopolynomial flavor.

In the interference scheduling problem, one is given a set of n communication requests described by pairs of points from a metric space. The points correspond to devices in a wireless network. In the directed version of the problem, each pair of points consists of a dedicated sending and a dedicated receiving device. In the bidirectional version the devices within a pair shall be able to exchange signals in both directions. In both versions, each pair must be assigned a power level and a color such that the pairs in each color class (representing pairs communicating in the same time slot) 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. This is commonly referred to as the "physical model" and is the established way of modelling interference in the engineering community. The objective is to minimize the number of colors as this corresponds to the time needed to schedule all requests.

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 matchings can be computed in polynomial time, but many real-life markets lack a central authority to match agents. In those markets, matchings are formed by actions of self-interested agents. Knuth introduced uncoordinated two-sided markets and showed that the uncoordinated better response dynamics may cycle. However, Roth and Vande Vate showed that the random better response dynamics converges to a stable matching with probability one, but did not address the question of convergence time.

The complexity of computing pure Nash equilibria in congestion games was recently shown to be PLS-complete. In this paper, we therefore study the complexity of computing approximate equilibria in congestion games. An alpha-approximate equilibrium, for α > 1, is a state of the game in which none of the players can make an α-greedy step, i.e., an unilateral strategy change that decreases the player's cost by a factor of at least α. Our main result shows that finding an α-approximate equilibrium of a given congestion game is sc PLS-complete, for any polynomial-time computable α > 1. Our analysis is based on a gap introducing PLS-reduction from FLIP, i.e., the problem of finding a local optimum of a function encoded by an arbitrary circuit. As this reduction is tight it additionally implies that computing an α-approximate equilibrium reachable from a given initial state by a sequence of α-greedy steps is PSPACE-complete. Our results are in sharp contrast to a recent result showing that every local search problem in PLS admits a fully polynomial time approximation scheme.

We study the problem of traffic routing in noncooperative networks. In such networks, users may follow selfish strategies to optimize their own performance measure and therefore, their behavior does not have to lead to optimal performance of the entire network. In this article we investigate the worst-case coordination ratio, which is a game-theoretic measure aiming to reflect the price of selfish routing.

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

We study rerouting policies in a dynamic round-based variant of a well known game theoretic traffic model due to Wardrop. Previous analyses (mostly in the context of selfish routing) based on Wardrop's model focus mostly on the static analysis of equilibria. In this paper, we ask the question whether the population of agents responsible for routing the traffic can jointly compute or better learn a Wardrop equilibrium efficiently. The rerouting policies that we study are of the following kind. In each round, each agent samples an alternative routing path and compares the latency on this path with its current latency. If the agent observes that it can improve its latency then it switches with some probability depending on the possible improvement to the better path.We can show various positive results based on a rerouting policy using an adaptive sampling rule that implicitly amplifies paths that carry a large amount of traffic in the Wardrop equilibrium. For general asymmetric games, we show that a simple replication protocol in which agents adopt strategies of more successful agents reaches a certain kind of bicriteria equilibrium within a time bound that is independent of the size and the structure of the network but only depends on a parameter of the latency functions, that we call the relative slope. For symmetric games, this result has an intuitive interpretation: Replication approximately satisfies almost everyone very quickly.In order to achieve convergence to a Wardrop equilibrium besides replication one also needs an exploration component discovering possibly unused strategies. We present a sampling based replication-exploration protocol and analyze its convergence time for symmetric games. For example, if the latency functions are defined by positive polynomials in coefficient representation, the convergence time is polynomial in the representation length of the latency functions. To the best of our knowledge, all previous results on the speed of convergence towards Wardrop equilibria, even when restricted to linear latency functions, were pseudopolynomial.In addition to the upper bounds on the speed of convergence, we can also present a lower bound demonstrating the necessity of adaptive sampling by showing that static sampling methods result in a slowdown that is exponential in the size of the network. A further lower bound illustrates that the relative slope is, in fact, the relevant parameter that determines the speed of convergence.

We present a probabilistic analysis of a large class of combinatorial optimization problems containing all binary optimization problems defined by linear constraints and a linear objective function over $\{0,1\}^n$. Our analysis is based on a semirandom input model that preserves the combinatorial structure of the underlying optimization problem by parameterizing which input numbers are of a stochastic and which are of an adversarial nature. This input model 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 binary optimization problems in terms of their worst-case complexity: A binary optimization problem has polynomial smoothed complexity if and only if it admits a (possibly randomized) algorithm with pseudo-polynomial worst-case complexity. Our analysis is centered around structural properties of binary optimization problems, called winner, loser, and feasibility gap. We show that if the coefficients of the objective function are stochastic, then the gap between the best and second best solution is likely to be of order $\Omega(1/n)$. Furthermore, we show that if the coefficients of the constraints are stochastic, then the slack of the optimal solution with respect to this constraint is typically of order $\Omega(1/n^2)$. We exploit these properties in an adaptive rounding scheme that increases the accuracy of calculation until the optimal solution is found. The strength of our techniques is illustrated by applications to various \npc-hard optimization problems from mathematical programming, network design, and scheduling for which we obtain the first algorithms with polynomial smoothed/average-case complexity.

We investigate balls-into-bins processes allocating m balls into n bins based on the multiple-choice paradigm. In the classical single-choice variant each ball is placed into a bin selected uniformly at random. In a multiple-choice process each ball can be placed into one out of $d \ge 2$ randomly selected bins. It is known that in many scenarios having more than one choice for each ball can improve the load balance significantly. Formal analyses of this phenomenon prior to this work considered mostly the lightly loaded case, that is, when $m \approx n$. In this paper we present the first tight analysis in the heavily loaded case, that is, when $m \gg n$ rather than $m \approx n$. The best previously known results for the multiple-choice processes in the heavily loaded case were obtained using majorization by the single-choice process. This yields an upper bound of the maximum load of bins of $m/n + {\mbox{$\cal O$}}(\sqrt{m \ln n \,/\, n})$ with high probability. We show, however, that the multiple-choice processes are fundamentally different from the single-choice variant in that they have "short memory." The great consequence of this property is that the deviation of the multiple-choice processes from the optimal allocation (that is, the allocation in which each bin has either $\lfloor m/n \rfloor$ or $\lceil m/n \rceil$ balls) does not increase with the number of balls as in the case of the single-choice process. In particular, we investigate the allocation obtained by two different multiple-choice allocation schemes, the greedy scheme due to Azar et al. and the always-go-left scheme due to Vöcking. We show that these schemes result in a maximum load of only $m/n + {\mbox{$\cal O$}}(\ln \ln n)$ with high probability. All our detailed bounds on the maximum load are tight up to an additive constant. Furthermore, we investigate the two multiple-choice algorithms in a comparative study. We present a majorization result showing that the always-go-left scheme obtains a better load balancing than the greedy scheme for any choice of n, m, and d.

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 service to a set of potential customers. Each customer has a particular demand of service and her behavior is determined by a utility function that is nonincreasing in the sum of demands that are served by the provider.Classical game theory assumes complete information : the provider has full knowledge of the behavior of all customers. We present a complete characterization of the complexity of computing optimal pricing strategies and of computing best/worst equilibria in this model. Basically, we show that most of these problems are inapproximable in the worst case but admit an FPAS in the average case. Our average case analysis covers large classes of distributions for customer utilities. We generalize our analysis to robust equilibria in which players change their strategies only when this promises a significant utility improvement.A more realistic model considers providers with incomplete information . Following the game theoretic framework of Bayesian games introduced by Harsanyi, the provider is aware of probability distributions describing the behavior of the customers and aims at estimating its expected revenue under best/worst equilibria. Somewhat counterintuitively, we obtain an FPRAS for the equilibria problem in the model with imperfect information although the problem with perfect information is inapproximable under the worst-case measures. In particular, the worst-case complexity of the considered problems increases with the precision of the available knowledge.

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 to undesirable oscillation effects resulting in poor performance. We investigate how adaptive routing policies should be designed such that these effects can be avoided.The network is represented by a general graph with latency functions on the edges. Traffic is managed by a large number of agents each of which is responsible for a negligible amount of traffic. Initially the agents' routing paths are chosen in an arbitrary fashion. From time to time each agent revises her routing strategy by sampling another path and switching with positive probability to this path if it promises smaller latencies. As the information on which the agent bases her decision might be stale, however, this does not necessarily lead to an improvement. The points of time at which agents revise their strategy are generated by a Poisson distribution. Stale information is modelled in form of a bulletin board that is updated periodically and lists the latencies on all edges.We analyze such a distributed routing process in the so-called fluid limit, that is, we use differential equations describing the fractions of traffic on different paths over time. In our model, we can show the following effects. Simple routing policies that always switch to the better alternative lead to oscillation, regardless at which frequency the bulletin board is updated. Oscillation effects can be avoided, however, when using smooth adaption policies that do not always switch to better alternatives but only with a probability depending on the advantage in the latency. In fact, such policies have dynamics that converge to a fixed point corresponding to a Nash equilibrium for the underlying routing game, provided the update periods are not too large.In addition, we also analyze the speed of convergence towards approximate equilibria of two specific variants of smooth adaptive routing policies, eg., for a replication policy adopted from evolutionary game theory.

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.

We present a probabilistic analysis of a large class of combinatorial\noptimization problems containing all {\\em binary optimization problems}\ndefined by linear constraints and a linear objective function over $\\{0,1\\}^n$.\nOur analysis is based on a semirandom input model that preserves the\ncombinatorial structure of the underlying optimization problem by\nparameterizing which input numbers are of a stochastic and which are of an\nadversarial nature. This input model covers various probability distributions\nfor the choice of the stochastic numbers and includes {\\em smoothed analysis}\nwith Gaussian and other kinds of perturbation models as a special case. In\nfact, we can exactly characterize the smoothed complexity of binary optimization\nproblems in terms of their worst-case complexity: A binary optimization\nproblem has polynomial smoothed complexity if and only if it admits a\n(possibly randomized) algorithm with pseudo-polynomial worst-case complexity.\n\nOur analysis is centered around structural properties of binary optimization\nproblems, called {\\em winner}, {\\em loser}, and {\\em feasibility gap}. We show\nthat if the coefficients of the objective function are stochastic, then the\ngap between the best and second best solution is likely to be of order\n$\\Omega(1/n)$. Furthermore, we show that if the coefficients of the constraints\nare stochastic, then the slack of the optimal solution with respect to this\nconstraint is typically of order $\\Omega(1/n^2)$. We exploit these properties\nin an adaptive rounding scheme that increases the accuracy of calculation\nuntil the optimal solution is found. The strength of our techniques is\nillustrated by applications to various \\npc-hard optimization problems from\nmathematical programming, network design, and scheduling for which we obtain\nthe first algorithms with polynomial smoothed/average-case complexity.

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 distributions, that the number of dominating solutions (i.e., Pareto-optimal knapsack fillings) to this problem is polynomially bounded in the number of available items. An algorithm by Nemhauser and Ullmann can enumerate these solutions very efficiently so that a polynomial upper bound on the number of dominating solutions implies an algorithm with expected polynomial running time.The random input model underlying our analysis is very general and not restricted to a particular input distribution. We assume adversarial weights and randomly drawn profits (or vice versa). Our analysis covers general probability distributions with finite mean, and, in its most general form, can even handle different probability distributions for the profits of different items. This feature enables us to study the effects of correlations between profits and weights. Our analysis confirms and explains practical studies showing that so-called strongly correlated instances are harder to solve than weakly correlated ones.

This article deals with randomized allocation processes placing sequentially n balls into n bins. We consider multiple-choice algorithms that choose d locations (bins) for each ball at random, inspect the content of these locations, and then place the ball into one of them, for example, in a location with minimum number of balls. The goal is to achieve a good load balancing. This objective is measured in terms of the maximum load, that is, the maximum number of balls in the same bin.Multiple-choice algorithms have been studied extensively in the past. Previous analyses typically assume that the d locations for each ball are drawn uniformly and independently from the set of all bins. We investigate whether a nonuniform or dependent selection of the d locations of a ball may lead to a better load balancing. Three types of selection, resulting in three classes of algorithms, are distinguished: (1) uniform and independent, (2) nonuniform and independent, and (3) nonuniform and dependent.Our first result shows that the well-studied uniform greedy algorithm (class 1) does not obtain the smallest possible maximum load. In particular, we introduce a nonuniform algorithm (class 2) that obtains a better load balancing. Surprisingly, this algorithm uses an unfair tie-breaking mechanism, called Always-Go-Left, resulting in an asymmetric assignment of the balls to the bins. Our second result is a lower bound showing that a dependent allocation (class 3) cannot yield significant further improvement.Our upper and lower bounds on the maximum load are tight up to additive constants, proving that the Always-Go-Left algorithm achieves an almost optimal load balancing among all sequential multiple-choice algorithm. Furthermore, we show that the results for the Always-Go-Left algorithm can be generalized to allocation processes with more balls than bins and even to infinite processes in which balls are inserted and deleted by an oblivious adversary.

We investigate the price of selfish routing in non-cooperative networks in terms of the coordination and bicriteria ratios in the recently introduced game theoretic network model of Koutsoupias and Papadimitriou. We present the first thorough study of this model for general, monotone families of cost functions and for cost functionsm from Queueing Theory. Our main results can be summarized as follows.

Consider an arbitrary distributed network in which large numbers of objects are continuously being created, replicated, and destroyed. A basic problem arising in such an environment is that of organizing a data tracking scheme for locating object copies. In this paper, we present a new tracking scheme for locating nearly copies of replicated objects in arbitrary distributed environments.

This paper deals with permutation routing on hypercube networks in the store-and-forward model. We introduce the first (on-line and off-line) algorithms routing any permutation on the d-dimensional hypercube in d+o(d) steps. The best previously known results were 2d+o(d) (oblivious on-line) and 2d-3 (off-line). In particular, we present

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.

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 placed simply into a randomly selected bin.In a multiple-choice process each ball can be placed into one out of d _> 2 randomly selected bins.It is well known that having more than one choice for each ball can improve the load balance significantly.In contrast to previous work on multiple-choice processes, we investigate the heavily loaded case, that is, we assume m >> n rather than m ,.~ n.The best previously known results for the multiple-choice processes in the heavily loaded case were obtained by majorization from the single-choice process.This yields an upper bound of m/n + O(~n).We show, however, that the multiplechoice processes are fundamentally different from the singlechoice variant in that they have "short memory".The great consequence of this property is that the deviation of the multiple-choice processes from the optimal allocation (i.e., at most [m/n] balls in every bin) does not increase with the number of balls as in case of the single-choice process.In particular, we investigate the allocation obtained by two different multiple-choice allocation schemes, the original greedy scheme and the recently presented always-go-left scheme.We show that

We investigate how static store-and-forward routing algorithms can be transformed into efficient dynamic algorithms, that is, how algorithms that have been designed for the case that all packets are injected at the same time can be adapted to more realistic scenarios in which packets are continuously injected into the network. Besides describing specific transformations for well-known static routing algorithms, we present a black box transformation scheme applicable to every static, oblivious routing algorithm. We analyze the performance of our protocols under a stochastic and an adversarial model of packet injections. One result of our specific transformations is the first dynamic routing algorithm for leveled networks that is stable for arbitrary admissible injection rates and that works with packet buffers of size depending solely on the injection rate and the node degree, but not on the size of the network. Furthermore, we prove strong delay bounds for the packets. Our results imply, for example, that a throughput of 99% can be achieved on an n-input butterfly network with buffers of constant size while each packet is delivered in time O(log n), with high probability. Our black box transformation ensures that if the static algorithm is pure (i.e., no extra packets apart from the original packets are routed), its dynamic variant is stable up to a maximum possible injection rate. Furthermore, in the stochastic model, the routing time of a packet depends on local parameters such as the length of its routing path, rather than on the maximum possible path length, even if the static algorithm chosen for the transformation does not provide this locality feature and is not pure. In the adversarial model, the delay bound of the packets is closely related to the time bound given for the static algorithm.

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.

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 network. The current implementations are based on mesh-connected massively parallel computers. Our algorithms dynamically create and discard copies of the data objects in order to reduce the communication overhead. We use a non-standard approach based on a randomized but locality preserving embedding of ``access trees'' into the network.

We investigate how static store-and-forward routing algorithms can be transformed into efficient dynamic algorithms, that is, how algorithms that have been designed for the case that all packets are injected at the same time can be adapted to more realistic scenarios in which packets are continuously injected into the network. Besides describing specific transformations for well-known static routing algorithms, we present a black box transformation scheme applicable to every static, oblivious routing algorithm. We analyze the performance of our protocols under a stochastic and an adversarial model of packet injections. One result of our specific transformations is the first dynamic routing algorithm for leveled networks that is stable for arbitrary admissible injection rates and that works with packet buffers of size depending solely on the injection rate and the node degree, but not on the size of the network. Furthermore, we prove strong delay bounds for the packets. Our results imply, for example, that a throughput of 99% can be achieved on an n-input butterfly network with buffers of constant size while each packet is delivered in time O(log n), with high probability. Our black box transformation ensures that if the static algorithm is pure (i.e., no extra packets apart from the original packets are routed), its dynamic variant is stable up to a maximum possible injection rate. Furthermore, in the stochastic model, the routing time of a packet depends on local parameters such as the length of its routing path, rather than on the maximum possible path length, even if the static algorithm chosen for the transformation does not provide this locality feature and is not pure. In the adversarial model, the delay bound of the packets is closely related to the time bound given for the static algorithm.

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 the messages with small congestion, dilation, and setup time. Our algorithms are based on the idea of having each message choose a route from two possibilities, a technique that has previously proven successful in simpler load balancing settings. As an application of our techniques, we propose a novel design for a data server.

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.

IntroductionThis paper shows that an N-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 several implications, including the first deterministic algorithms for sorting and finding the median of n logn keys on an n-input multibuttertly in O(log n) time, a work-efficient deterministic algorithm for finding the median of n logz n log log n keys on an n-input multibutterfly in O(log n log log n) time, and a three-dimensional VLSI layout for the n-input AKS network with volume 0(n3/2).While these algorithms are not practical, they provide further evidence of the robustness of multibutterfly networks.We also present a separate, and more practical, deterministic algorithm for routing h relations on an n-input multibutterfly in O(h + log n) time.Previously, only algorithms for solving h one-to-one routing problems were known.Finally, we show that a 2-folded butterfly, whose individual splitters do not exhibit expansion, can emulate a bounded-degree multibutterfly with (CS, ,@-expansion, for any a ./3 < 1/4.

In this paper we present routing protocols that are universal results to continuous routing m node-symmetric networks, butterfhes, and meshes 1 ' ema,l {chrsch,voecking}

In this paper we present routing algorithms that are tmiversal in the sense that they route messages along arbitrary (simple) paths in arbitrary networks.The algorithms are analyzed in terms of the number of messages being routed, the maximum number of messages that must cross any edge in the network (edge congestion), the maximum number of edges that a message must cross (dilation), the bufler size, and the bandwidth of the links.We present two main results, both of which have applications to ttnivexsal storeand-forwwd routing and universal wormhole routing.Our results yield significant performance improvements over all previously known universal routing algorithms for a wide range of parameters, and they even improve many time bounds for standard networks.In addition, we present adaptations of our main results for routing along shortest paths in arbitrary networks, and for routing in leveled networks, node-symmetric networks, edge-symmetric networks, expanders, butterflies, and meshes.