The Impact of Social Ignorance on Weighted Congestion Games

We consider weighted linear congestion games, and investigate how social ignorance, namely lack of information about the presence of some players, affects the inefficiency of pure Nash equilibria (PNE) and the convergence rate of the ε-Nash dynamics. To this end, we adopt the model of graphical linear congestion games with weighted players, where the individual cost and the strategy selection of each player only depends on his neighboring players in the social graph. We show that such games admit a potential function, and thus a PNE. Next, we investigate the Price of Anarchy (PoA) and the Price of Stability (PoS) of graphical linear congestion games with respect to the players’ total actual cost. Our main result is that the impact of social ignorance on the PoA and on the PoS is naturally quantified by the independence number α(G) of the social graph G. In particular, we show that the PoA grows roughly as α(G)(α(G)+2), which is essentially tight as long as α(G) does not exceed half the number of players, and that the PoS lies between α(G) and 2α(G). Moreover, we show that the ε-Nash dynamics reaches an α(G)(α(G)+2)-approximate configuration in polynomial time that does not directly depend on the social graph. For unweighted graphical linear games with symmetric strategies, we show that the ε-Nash dynamics reaches an ε-approximate PNE in polynomial time that exceeds the corresponding time for symmetric linear games by a factor at most as large as the number of players.     

Non-Cooperative Tree Creation

In this paper we consider the connection game, a simple network design game with independent selfish agents that was introduced by Anshelevich et al. (Proc. 35th Ann. ACM Symp. Theo. Comp. (STOC), pp. 511–520, 2003). Our study concerns an important subclass of tree games, in which every feasible network is guaranteed to be connected. It generalizes the class of single-source games considered by Anshelevich et al. We focus on the existence, quality, and computability of pure-strategy exact and approximate Nash equilibria. For tree connection games, in which every player holds two terminals, we show that there is a Nash equilibrium as cheap as the optimum network. In contrast, for single-source games, in which every player has at most three terminals, the price of stability is at least k−2, and it is -complete to decide the existence of a Nash equilibrium. Hence, we propose polynomial time algorithms for computing approximate Nash equilibria, which provide relaxed stability and cost efficiency guarantees. For the case of two terminals per player, there is an algorithm to find a (2+ε,1.55)-approximate Nash equilibrium. It can be generalized to an algorithm to find a (3.1+ε,1.55)-approximate Nash equilibrium for general tree connection games. This improves the guarantee of the only previous algorithm for the problem, which returns a (4.65+ε,1.55)-approximate Nash equilibrium. Tightness results for the analysis of all algorithms are derived. Our algorithms use a novel iteration technique for trees that might be of independent interest. This work has appeared in part as an extended abstract at the 31st Symposium on Mathematical Foundations of Computer Science (MFCS 2006) and the 17th International Symposium on Algorithms and Computation (ISAAC 2006). Supported by DFG Research Training Group 1042 “Explorative Analysis and Visualization of Large Information Spaces”.     

A randomized clustering of anonymous wireless ad hoc networks with an application to the initialization problem

The Distributed Mobility-Adaptive Clustering (DMAC) due to Basagni partitions the nodes of a mobile ad hoc network into clusters, thus giving the network a hierarchical organization. This algorithm supports the mobility of the nodes, even during the cluster formation. The main feature of DMAC is that in a weighted network (in which two or more nodes cannot have the same weight), nodes have to choose the clusterheads taking into account only the node weight, i.e. the mobility when a node weight is the inverse of its speed. In our approach many nodes may have the same speed and hence the same weight. We assume that nodes have no identities and the number of nodes, say n, is the only known parameter of the network. After the randomized clustering, we show that the initialization problem can be solved in a multi-hop ad hoc wireless network of n stations in O(k ^1/2log ^1/2 k)+D _b −1+O(log (max (P _i )+log ²max (P _i )) broadcast rounds with high probability, where k is the number of clusters, D _b is the blocking diameter and max (P _i ), 1≤i≤k, is the maximum number of nodes in a cluster. Thus the initialization protocol presented here uses less broadcast rounds than the one in Ravelemanana (IEEE Trans. Parallel Distributed Syst. 18(1):17–28 2007).     

Applying Approximate Counting for Computing the Frequency Moments of Long Data Streams

This paper takes up a remark in the well-known paper of Alon, Matias, and Szegedy (J. Comput. Syst. Sci. 58(1):137–147, 1999) about the computation of the frequency moments of data streams and shows in detail how any F _k with k≥1 can be approximately computed using space O(km ^1−1/k (k+log m+log log  n)) based on approximate counting. An important building block for this, which may be interesting in its own right, is a new approximate variant of reservoir sampling using space O(log log  n) for constant error parameters.     

Space Efficient Dynamic Orthogonal Range Reporting

In this paper we present new space efficient dynamic data structures for orthogonal range reporting. The described data structures support planar range reporting queries in time O(log n+klog log (4n/(k+1))) and space O(nlog log n), or in time O(log n+k) and space O(nlog  ^ε n) for any ε>0. Both data structures can be constructed in O(nlog n) time and support insert and delete operations in amortized time O(log ² n) and O(log nlog log n) respectively. These results match the corresponding upper space bounds of Chazelle (SIAM J. Comput. 17, 427–462, 1988) for the static case. We also present a dynamic data structure for d-dimensional range reporting with search time O(log  ^d−1 n+k), update time O(log  ^d n), and space O(nlog  ^d−2+ε n) for any ε>0. The model of computation used in our paper is a unit cost RAM with word size log n. A preliminary version of this paper appeared in the Proceedings of the 21st Annual ACM Symposium on Computational Geometry 2005. Work partially supported by IST grant 14036 (RAND-APX).     

Dynamic Hotlinks

Consider a directed rooted tree T=(V,E) representing a collection V of n web pages connected via a set E of links all reachable from a source home page, represented by the root of T. Each web page i carries a weight w _i representative of the frequency with which it is visited. By adding hotlinks, shortcuts from a node to one of its descendants, we are interested in minimizing the expected number of steps needed to visit pages from the home page. We give the first linear time algorithm for assigning hotlinks so that the number of steps to access a page i from the root of the tree reaches the entropy bound, i.e. is at most O(log (W/w _i )) where W=∑ _i∈T w _i . The best previously known algorithm for this task runs in time O(n ²). We also give the first efficient data structure for maintaining hotlinks when nodes are added, deleted or their weights modified, in amortized time O(log (W/w _i )) per update. The data structure can be made adaptive, i.e. reaches the entropy bound in the amortized sense without knowing the weights w _i in advance.     

Choosing a Random Peer in Chord

We present two new algorithms, Arc Length and Peer Count, for choosing a peer uniformly at random from the set of all peers in Chord (Proceedings of the ACM SIGCOMM 2001 Technical Conference, 2001). We show analytically that, in expectation, both algorithms have latency O(log n) and send O(log n) messages. Moreover, we show empirically that the average latency and message cost of Arc Length is 10.01log n and that the average latency and message cost of Peer Count is 20.02log n. To the best of our knowledge, these two algorithms are the first fully distributed algorithms for choosing a peer uniformly at random from the set of all peers in a Distributed Hash Table (DHT). Our motivation for studying this problem is threefold: to enable data collection by statistically rigorous sampling methods; to provide support for randomized, distributed algorithms over peer-to-peer networks; and to support the creation and maintenance of random links, and thereby offer a simple means of improving fault-tolerance. Research of S. Lewis, J. Saia and M. Young was partially supported by NSF grant CCR-0313160 and Sandia University Research Program grant No. 191445.     

Parallel integer sorting and simulation amongst CRCW models

 In this paper a general technique for reducing processors in simulation without any increase in time is described. This results in an O(√log n) time algorithm for simulating one step of PRIORITY on TOLERANT with processor-time product of O(n log log n); the same as that for simulating PRIORITY on ARBITRARY. This is used to obtain an O(log n/log log n+√log n (log log m− log log n)) time algorithm for sorting n integers from the set {0,…, m−1}, m≧n, with a processor-time product of O(n log log m log log n) on a TOLERANT CRCW PRAM. New upper and lower bounds for ordered chaining problem on an allocated COMMON CRCW model are also obtained. The algorithm for ordered chaining takes O(log n/log log n) time on an allocated PRAM of size n. It is shown that this result is best possible (upto a constant multiplicative factor) by obtaining a lower bound of Ω(r log n/(log r+log log n)) for finding the first (leftmost one) live processor on an allocated-COMMON PRAM of size n of r-slow virtual processors (one processor simulates r processors of allocated PRAM). As a result, for ordered chaining problem, “processor-time product” has to be at least Ω(n log n/log log n) for any poly-logarithmic time algorithm. Algorithm for ordered-chaining problem results in an O(log N/log log N) time algorithm for (stable) sorting of n integers from the set {0,…, m−1} with n-processors on a COMMON CRCW PRAM; here N=max(n, m). In particular if, m=n ^O(1) , then sorting takes Θ(log n/log log n) time on both TOLERANT and COMMON CRCW PRAMs. Processor-time product for TOLERANT is O(n(log log n)²). Algorithm for COMMON uses n processors. Received August 13, 1992/June 30, 1995     

Approximation Algorithms for Requirement Cut on Graphs

In this paper, we unify several graph partitioning problems including multicut, multiway cut, and k-cut, into a single problem. The input to the requirement cut problem is an undirected edge-weighted graph G=(V,E), and g groups of vertices X ₁,…,X _g ⊆V, with each group X _i having a requirement r _i between 0 and |X _i |. The goal is to find a minimum cost set of edges whose removal separates each group X _i into at least r _i disconnected components. We give an O(log n⋅log (gR)) approximation algorithm for the requirement cut problem, where n is the total number of vertices, g is the number of groups, and R is the maximum requirement. We also show that the integrality gap of a natural LP relaxation for this problem is bounded by O(log n⋅log (gR)). On trees, we obtain an improved guarantee of O(log (gR)). There is an Ω(log g) hardness of approximation for the requirement cut problem, even on trees.     

Fast Algorithms for the Density Finding Problem

We study the problem of finding a specific density subsequence of a sequence arising from the analysis of biomolecular sequences. Given a sequence A=(a ₁,w ₁),(a ₂,w ₂),…,(a _n ,w _n ) of n ordered pairs (a _i ,w _i ) of numbers a _i and width w _i >0 for each 1≤i≤n, two nonnegative numbers ℓ, u with ℓ≤u and a number δ, the Density Finding Problem is to find the consecutive subsequence A(i ^*,j ^*) over all O(n ²) consecutive subsequences A(i,j) with width constraint satisfying ℓ≤w(i,j)=∑ _r=i ^j w _r ≤u such that its density is closest to δ. The extensively studied Maximum-Density Segment Problem is a special case of the Density Finding Problem with δ=∞. We show that the Density Finding Problem has a lower bound Ω(nlog n) in the algebraic decision tree model of computation. We give an algorithm for the Density Finding Problem that runs in optimal O(nlog n) time and O(nlog n) space for the case when there is no upper bound on the width of the sequence, i.e., u=w(1,n). For the general case, we give an algorithm that runs in O(nlog ² m) time and O(n+mlog m) space, where and w _min=min  _r=1 ⁿ w _r . As a byproduct, we give another O(n) time and space algorithm for the Maximum-Density Segment Problem. Grants NSC95-2221-E-001-016-MY3, NSC-94-2422-H-001-0001, and NSC-95-2752-E-002-005-PAE, and by the Taiwan Information Security Center (TWISC) under the Grants NSC NSC95-2218-E-001-001, NSC95-3114-P-001-002-Y, NSC94-3114-P-001-003-Y and NSC 94-3114-P-011-001.     

A Sequential Algorithm for Generating Random Graphs

We present a nearly-linear time algorithm for counting and randomly generating simple graphs with a given degree sequence in a certain range. For degree sequence (d _i ) _i=1 ⁿ with maximum degree d _max?=O(m ^1/4?τ ), our algorithm generates almost uniform random graphs with that degree sequence in time O(md _max?) where $m=\frac{1}{2}\sum_{i}d_{i}We present a nearly-linear time algorithm for counting and randomly generating simple graphs with a given degree sequence in a certain range. For degree sequence (d _i ) _i=1 ⁿ with maximum degree d _max=O(m ^1/4−τ ), our algorithm generates almost uniform random graphs with that degree sequence in time O(md _max) where m=\frac12?_id_im=\frac{1}{2}\sum_{i}d_{i} is the number of edges in the graph and τ is any positive constant. The fastest known algorithm for uniform generation of these graphs (McKay and Wormald in J. Algorithms 11(1):52–67, 1990) has a running time of O(m ² d _max²). Our method also gives an independent proof of McKay’s estimate (McKay in Ars Combinatoria A 19:15–25, 1985) for the number of such graphs.     

Approximating Buy-at-Bulk and Shallow-Light <Emphasis Type="Italic">k</Emphasis>-Steiner Trees

We study two related network design problems with two cost functions. In the buy-at-bulk k-Steiner tree problem we are given a graph G(V,E) with a set of terminals T⊆V including a particular vertex s called the root, and an integer k≤|T|. There are two cost functions on the edges of G, a buy cost b:E→ℝ⁺ and a distance cost r:E→ℝ⁺. The goal is to find a subtree H of G rooted at s with at least k terminals so that the cost ∑ _e∈H b(e)+∑ _t∈T−s dist(t,s) is minimized, where dist(t,s) is the distance from t to s in H with respect to the r cost. We present an O(log ⁴ n)-approximation algorithm for the buy-at-bulk k-Steiner tree problem. The second and closely related one is bicriteria approximation algorithm for Shallow-light k-Steiner trees. In the shallow-light k-Steiner tree problem we are given a graph G with edge costs b(e) and distance costs r(e), and an integer k. Our goal is to find a minimum cost (under b-cost) k-Steiner tree such that the diameter under r-cost is at most some given bound D. We develop an (O(log n),O(log ³ n))-approximation algorithm for a relaxed version of Shallow-light k-Steiner tree where the solution has at least terminals. Using this we obtain an (O(log ² n),O(log ⁴ n))-approximation algorithm for the shallow-light k-Steiner tree and an O(log ⁴ n)-approximation algorithm for the buy-at-bulk k-Steiner tree problem. Our results are recently used to give the first polylogarithmic approximation algorithm for the non-uniform multicommodity buy-at-bulk problem (Chekuri, C., et al. in Proceedings of 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06), pp. 677–686, 2006). A preliminary version of this paper appeared in the Proceedings of 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) 2006, LNCS 4110, pp. 153–163, 2006. M.T. Hajiaghayi supported in part by IPM under grant number CS1383-2-02. M.R. Salavatipour supported by NSERC grant No. G121210990, and a faculty start-up grant from University of Alberta.     

Approximating Minimum-Power Degree and Connectivity Problems

Power optimization is a central issue in wireless network design. Given a graph with costs on the edges, the power of a node is the maximum cost of an edge incident to it, and the power of a graph is the sum of the powers of its nodes. Motivated by applications in wireless networks, we consider several fundamental undirected network design problems under the power minimization criteria. Given a graph G=(V,E)\mathcal{G}=(V,\mathcal{E}) with edge costs {c(e):e∈ℰ} and degree requirements {r(v):v∈V}, the Minimum-Power Edge-Multi-Cover\textsf{Minimum-Power Edge-Multi-Cover} (MPEMC\textsf{MPEMC} ) problem is to find a minimum-power subgraph G of G\mathcal{G} so that the degree of every node v in G is at least r(v). We give an O(log n)-approximation algorithms for MPEMC\textsf{MPEMC} , improving the previous ratio O(log ⁴ n). This is used to derive an O(log n+α)-approximation algorithm for the undirected $\textsf{Minimum-Power $\textsf{Minimum-Power ($\textsf{MP$\textsf{MP ) problem, where α is the best known ratio for the min-cost variant of the problem. Currently, _boxclosen-k)\alpha=O(\log k\cdot \log\frac{n}{n-k}) which is O(log k) unless k=n−o(n), and is O(log ² k)=O(log ² n) for k=n−o(n). Our result shows that the min-power and the min-cost versions of the $\textsf{$\textsf{ problem are equivalent with respect to approximation, unless the min-cost variant admits an o(log n)-approximation, which seems to be out of reach at the moment.     

A randomized algorithm for the on-line weighted bipartite matching problem

We study the on-line minimum weighted bipartite matching problem in arbitrary metric spaces. Here, n not necessary disjoint points of a metric space M are given, and are to be matched on-line with n points of M revealed one by one. The cost of a matching is the sum of the distances of the matched points, and the goal is to find or approximate its minimum. The competitive ratio of the deterministic problem is known to be Θ(n), see (Kalyanasundaram, B., Pruhs, K. in J. Algorithms 14(3):478–488, 1993) and (Khuller, S., et al. in Theor. Comput. Sci. 127(2):255–267, 1994). It was conjectured in (Kalyanasundaram, B., Pruhs, K. in Lecture Notes in Computer Science, vol. 1442, pp. 268–280, 1998) that a randomized algorithm may perform better against an oblivious adversary, namely with an expected competitive ratio Θ(log n). We prove a slightly weaker result by showing a o(log ³ n) upper bound on the expected competitive ratio. As an application the same upper bound holds for the notoriously hard fire station problem, where M is the real line, see (Fuchs, B., et al. in Electonic Notes in Discrete Mathematics, vol. 13, 2003) and (Koutsoupias, E., Nanavati, A. in Lecture Notes in Computer Science, vol. 2909, pp. 179–191, 2004). The authors were partially supported by OTKA grants T034475 and T049398.     

Combining Markov-Chain Analysis and Drift Analysis

In their seminal article Droste, Jansen, and Wegener (Theor. Comput. Sci. 276:51–82, 2002) consider a basic direct-search heuristic with a global search operator, namely the so-called (1+1) Evolutionary Algorithm ((1+1) EA). They present the first theoretical analysis of the (1+1) EA’s expected runtime for the class of linear functions over the search space {0,1} ⁿ . In a rather long and involved proof they show that, for any linear function, the expected runtime is O(nlog n), i.e., that there are two constants c and n′ such that, for n≥n′, the expected number of iterations until a global optimum is generated is bounded above by c⋅nlog ₂ n. However, neither c nor n′ are specified—they would be pretty large. Here we reconsider this optimization scenario to demonstrate the potential of an analytical method that makes use of the distribution of the evolving candidate solution over the search space {0,1} ⁿ . Actually, an invariance property of this distribution is proved, which is then used to obtain a significantly improved bound on the drift, namely the expected change of a potential function, here the number of bits set correctly. Finally, this better estimate of the drift enables an upper bound on the expected number of iterations of 3.8nlog ₂ n+7.6log ₂ n for n≥2.     

Speed Scaling of Processes with Arbitrary Speedup Curves on a Multiprocessor

We consider the setting of a multiprocessor where the speeds of the m processors can be individually scaled. Jobs arrive over time and have varying degrees of parallelizability. A nonclairvoyant scheduler must assign the processes to processors, and scale the speeds of the processors. We consider the objective of energy plus flow time. We assume that a processor running at speed s uses power s ^α for some constant α>1. For processes that may have side effects or that are not checkpointable, we show an W(m^(a-1)/a2)\Omega(m^{(\alpha -1)/\alpha^{2}}) bound on the competitive ratio of any randomized algorithm. For checkpointable processes without side effects, we give an O(log m)-competitive algorithm. Thus for processes that may have side effects or that are not checkpointable, the achievable competitive ratio grows quickly with the number of processors, but for checkpointable processes without side effects, the achievable competitive ratio grows slowly with the number of processors. We then show a lower bound of Ω(log ^1/α m) on the competitive ratio of any randomized algorithm for checkpointable processes without side effects.     

New Linear-Time Algorithms for Edge-Coloring Planar Graphs

We show efficient algorithms for edge-coloring planar graphs. Our main result is a linear-time algorithm for coloring planar graphs with maximum degree Δ with max {Δ,9} colors. Thus the coloring is optimal for graphs with maximum degree Δ≥9. Moreover for Δ=4,5,6 we give linear-time algorithms that use Δ+2 colors. These results improve over the algorithms of Chrobak and Yung (J. Algorithms 10:35–51, 1989) and of Chrobak and Nishizeki (J. Algorithms 11:102–116, 1990) which color planar graphs using max {Δ,19} colors in linear time or using max {Δ,9} colors in time. R. Cole supported in part by NSF grants CCR0105678 and CCF0515127 and IDM0414763. Ł. Kowalik supported in part by KBN grant 4T11C04425. Part of this work was done while Ł. Kowalik was staying at the Max Planck Institute in Saarbruecken, Germany.     

<Emphasis Type="Italic">f</Emphasis>-Sensitivity Distance Oracles and Routing Schemes

An f-sensitivity distance oracle for a weighted undirected graph G(V,E) is a data structure capable of answering restricted distance queries between vertex pairs, i.e., calculating distances on a subgraph avoiding some forbidden edges. This paper presents an efficiently constructible f-sensitivity distance oracle that given a triplet (s,t,F), where s and t are vertices and F is a set of forbidden edges such that |F|≤f, returns an estimate of the distance between s and t in G(V,E∖F). For an integer parameter k≥1, the size of the data structure is O(fkn ^1+1/k log (nW)), where W is the heaviest edge in G, the stretch (approximation ratio) of the returned distance is (8k−2)(f+1), and the query time is O(|F|⋅log ² n⋅log log n⋅log log d), where d is the distance between s and t in G(V,E∖F).     

Exact and Approximate Truthful Mechanisms for the Shortest Paths Tree Problem

Let a communication network be modeled by an undirected graph G=(V,E) of n nodes and m edges, and assume that edges are controlled by selfish agents. In this paper we analyze the problem of designing a truthful mechanism for computing one of the most popular structures in communication networks, i.e., the single-source shortest paths tree. More precisely, we will study several realistic scenarios, in which each agent can own either a single or multiple edges of G. In particular, for the single-edge case, we will show that: (i) in the classic utilitarian case, the problem can be solved efficiently in O(mnlog α(m,n)) time, where α(m,n) is the inverse of the Ackermann’s function; (ii) in a meaningful non-utilitarian case, namely that in which agents’ valuation functions only depend on the edge lengths, the problem can be solved in O(m+nlog n) time. Conversely, for the multiple-edges case, we will show in the utilitarian case an O(mP+nPlog n) time truthful mechanism, where P=O(n) denotes the number of agents participating in the solution, while in the same non-utilitarian case we will prove a general lower bound to the approximation ratio that can be achieved by any truthful mechanism, by showing that no c-approximate mechanism can exist, for any fixed . Work partially supported by the Research Project GRID.IT, funded by the Italian Ministry of Education, University and Research. Part of the results herein contained was presented at the 11th International Euro-Par Conference (Euro-Par’05), Lisbon, Portugal, 2005.     

Dynamic vs. Oblivious Routing in Network Design

Consider the robust network design problem of finding a minimum cost network with enough capacity to route all traffic demand matrices in a given polytope. We investigate the impact of different routing models in this robust setting: in particular, we compare oblivious routing, where the routing between each terminal pair must be fixed in advance, to dynamic routing, where routings may depend arbitrarily on the current demand. Our main result is a construction that shows that the optimal cost of such a network based on oblivious routing (fractional or integral) may be a factor of Ω(log n) more than the cost required when using dynamic routing. This is true even in the important special case of the asymmetric hose model. This answers a question in (Chekuri, SIGACT News 38(3):106–128, 2007), and is tight up to constant factors. Our proof technique builds on a connection between expander graphs and robust design for single-sink traffic patterns (Chekuri et al., Networks 50(1):50–54, 2007).