共查询到20条相似文献,搜索用时 15 毫秒
1.
We consider a model of game-theoretic network design initially studied by Anshelevich et al. (Proceedings of the 45th Annual
Symposium on Foundations of Computer Science (FOCS), pp. 295–304, 2004), where selfish players select paths in a network to minimize their cost, which is prescribed by Shapley cost shares. If
all players are identical, the cost share incurred by a player for an edge in its path is the fixed cost of the edge divided
by the number of players using it. In this special case, Anshelevich et al. (Proceedings of the 45th Annual Symposium on Foundations
of Computer Science (FOCS), pp. 295–304, 2004) proved that pure-strategy Nash equilibria always exist and that the price of stability—the ratio between the cost of the
best Nash equilibrium and that of an optimal solution—is Θ(log k), where k is the number of players. Little was known about the existence of equilibria or the price of stability in the general weighted version of the game. Here, each player i has a weight w
i
≥1, and its cost share of an edge in its path equals w
i
times the edge cost, divided by the total weight of the players using the edge.
This paper presents the first general results on weighted Shapley network design games. First, we give a simple example with
no pure-strategy Nash equilibrium. This motivates considering the price of stability with respect to α-approximate Nash equilibria—outcomes from which no player can decrease its cost by more than an α multiplicative factor. Our first positive result is that O(log w
max )-approximate Nash equilibria exist in all weighted Shapley network design games, where w
max is the maximum player weight. More generally, we establish the following trade-off between the two objectives of good stability
and low cost: for every α=Ω(log w
max ), the price of stability with respect to O(α)-approximate Nash equilibria is O((log W)/α), where W is the sum of the players’ weights. In particular, there is always an O(log W)-approximate Nash equilibrium with cost within a constant factor of optimal.
Finally, we show that this trade-off curve is nearly optimal: we construct a family of networks without o(log w
max / log log w
max )-approximate Nash equilibria, and show that for all α=Ω(log w
max /log log w
max ), achieving a price of stability of O(log W/α) requires relaxing equilibrium constraints by an Ω(α) factor.
Research of H.-L. Chen supported in part by NSF Award 0323766.
Research of T. Roughgarden supported in part by ONR grant N00014-04-1-0725, DARPA grant W911NF-04-9-0001, and an NSF CAREER
Award. 相似文献
2.
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. 相似文献
3.
Y. Nekrich 《Algorithmica》2007,49(2):94-108
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 2
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). 相似文献
4.
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 n 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
n
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?idim=\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
2
d
max 2). 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. 相似文献
5.
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 4
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 3
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 2
n),O(log 4
n))-approximation algorithm for the shallow-light k-Steiner tree and an O(log 4
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. 相似文献
6.
Approximate string matching is about finding a given string pattern in a text by allowing some degree of errors. In this paper
we present a space efficient data structure to solve the 1-mismatch and 1-difference problems. Given a text T of length n over an alphabet A, we can preprocess T and give an
-bit space data structure so that, for any query pattern P of length m, we can find all 1-mismatch (or 1-difference) occurrences of P in O(|A|mlog log n+occ) time, where occ is the number of occurrences. This is the fastest known query time given that the space of the data structure is o(nlog 2
n) bits.
The space of our data structure can be further reduced to O(nlog |A|) with the query time increasing by a factor of log
ε
n, for 0<ε≤1. Furthermore, our solution can be generalized to solve the k-mismatch (and the k-difference) problem in O(|A|
k
m
k
(k+log log n)+occ) and O(log
ε
n(|A|
k
m
k
(k+log log n)+occ)) time using an
-bit and an O(nlog |A|)-bit indexing data structures, respectively. We assume that the alphabet size |A| is bounded by
for the
-bit space data structure. 相似文献
7.
Degree-Optimal Routing for P2P Systems 总被引:1,自引:0,他引:1
Giovanni Chiola Gennaro Cordasco Luisa Gargano Mikael Hammar Alberto Negro Vittorio Scarano 《Theory of Computing Systems》2009,45(1):43-63
We define a family of Distributed Hash Table systems whose aim is to combine the routing efficiency of randomized networks—e.g.
optimal average path length O(log 2
n/δlog δ) with δ degree—with the programmability and startup efficiency of a uniform overlay—that is, a deterministic system in which the overlay network is transitive and greedy routing is optimal. It is known that Ω(log n) is a lower bound on the average path length for uniform overlays with O(log n) degree (Xu et al., IEEE J. Sel. Areas Commun. 22(1), 151–163, 2004).
Our work is inspired by neighbor-of-neighbor (NoN) routing, a recently introduced variation of greedy routing that allows us to achieve optimal average path length in randomized networks. The advantage of our proposal is that of allowing
the NoN technique to be implemented without adding any overhead to the corresponding deterministic network.
We propose a family of networks parameterized with a positive integer c which measures the amount of randomness that is used. By varying the value c, the system goes from the deterministic case (c=1) to an “almost uniform” system. Increasing c to relatively low values allows for routing with asymptotically optimal average path length while retaining most of the advantages
of a uniform system, such as easy programmability and quick bootstrap of the nodes entering the system.
We also provide a matching lower bound for the average path length of the routing schemes for any c.
This work was partially supported by the Italian FIRB project “WEB-MINDS” (Wide-scalE, Broadband MIddleware for Network Distributed
Services), . 相似文献
8.
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
1,…,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. 相似文献
9.
Ho-Leung Chan Tak-Wah Lam Wing-Kin Sung Siu-Lung Tam Swee-Seong Wong 《Algorithmica》2010,58(2):263-281
We revisit the problem of indexing a string S[1..n] to support finding all substrings in S that match a given pattern P[1..m] with at most k errors. Previous solutions either require an index of size exponential in k or need Ω(m
k
) time for searching. Motivated by the indexing of DNA, we investigate space efficient indexes that occupy only O(n) space. For k=1, we give an index to support matching in O(m+occ+log nlog log n) time. The previously best solution achieving this time complexity requires an index of O(nlog n) space. This new index can also be used to improve existing indexes for k≥2 errors. Among others, it can support 2-error matching in O(mlog nlog log n+occ) time, and k-error matching, for any k>2, in O(m
k−1log nlog log n+occ) time. 相似文献
10.
Mesh of trees (MOT) is well known for its small diameter, high bisection width, simple decomposability and area universality.
On the other hand, OTIS (Optical Transpose Interconnection System) provides an efficient optoelectronic model for massively
parallel processing system. In this paper, we present OTIS-MOT as a competent candidate for a two-tier architecture that can
take the advantages of both the OTIS and the MOT. We show that an n4-n^{4}_{-} processor OTIS-MOT has diameter 8log n
∗+1 (The base of the logarithm is assumed to be 2 throughout this paper.) and fault diameter 8log n+2 under single node failure. We establish other topological properties such as bisection width, multiple paths and the modularity.
We show that many communication as well as application algorithms can run on this network in comparable time or even faster
than other similar tree-based two-tier architectures. The communication algorithms including row/column-group broadcast and
one-to-all broadcast are shown to require O(log n) time, multicast in O(n
2log n) time and the bit-reverse permutation in O(n) time. Many parallel algorithms for various problems such as finding polynomial zeros, sales forecasting, matrix-vector multiplication
and the DFT computation are proposed to map in O(log n) time. Sorting and prefix computation are also shown to run in O(log n) time. 相似文献
11.
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 4
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 2
k)=O(log 2
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. 相似文献
12.
We present new efficient deterministic and randomized distributed algorithms for decomposing a graph with n nodes into a disjoint set of connected clusters with radius at most k−1 and having O(n
1+1/k
) intercluster edges. We show how to implement our algorithms in the distributed
CONGEST\mathcal{CONGEST}
model of computation, i.e., limited message size, which improves the time complexity of previous algorithms (Moran and Snir
in Theor. Comput. Sci. 243(1–2):217–241, 2000; Awerbuch in J. ACM 32:804–823, 1985; Peleg in Distributed Computing: A Locality-Sensitive Approach, 2000) from O(n) to O(n
1−1/k
). We apply our algorithms for constructing low stretch graph spanners and network synchronizers in sublinear deterministic
time in the
CONGEST\mathcal{CONGEST}
model. 相似文献
13.
Hans L. Bodlaender Michael R. Fellows Michael A. Langston Mark A. Ragan Frances A. Rosamond Mark Weyer 《Algorithmica》2011,61(2):362-388
The Convex Recoloring (CR) problem measures how far a tree of characters differs from exhibiting a so-called “perfect phylogeny”. For an input
consisting of a vertex-colored tree T, the problem is to determine whether recoloring at most k vertices can achieve a convex coloring, meaning by this a coloring where each color class induces a subtree. The problem
was introduced by Moran and Snir (J. Comput. Syst. Sci. 73:1078–1089, 2007; J. Comput. Syst. Sci. 74:850–869, 2008) who showed that CR is NP-hard, and described a search-tree based FPT algorithm with a running time of O(k(k/log k)
k
n
4). The Moran and Snir result did not provide any nontrivial kernelization. In this paper, we show that CR has a kernel of
size O(k
2). 相似文献
14.
We study the communication primitives of broadcasting (one-to-all communication) and gossiping (all-to-all communication)
in known topology radio networks, i.e., where for each primitive the schedule of transmissions is precomputed based on full
knowledge about the size and the topology of the network. We show that gossiping can be completed in
time units in any radio network of size n, diameter D, and maximum degree Δ=Ω(log n). This is an almost optimal schedule in the sense that there exists a radio network topology, specifically a Δ-regular tree, in which the radio gossiping cannot be completed in less than
units of time. Moreover, we show a
schedule for the broadcast task. Both our transmission schemes significantly improve upon the currently best known schedules
by Gąsieniec, Peleg, and Xin (Proceedings of the 24th Annual ACM SIGACT-SIGOPS PODC, pp. 129–137, 2005), i.e., a O(D+Δlog n) time schedule for gossiping and a D+O(log 3
n) time schedule for broadcast. Our broadcasting schedule also improves, for large D, a very recent O(D+log 2
n) time broadcasting schedule by Kowalski and Pelc.
A preliminary version of this paper appeared in the proceedings of ISAAC’06.
F. Cicalese supported by the Sofja Kovalevskaja Award 2004 of the Alexander von Humboldt Stiftung. F. Manne and Q. Xin supported
by the Research Council of Norway through the SPECTRUM project. 相似文献
15.
This paper studies vehicle routing problems on asymmetric metrics. Our starting point is the directed
k-TSP problem: given an asymmetric metric (V,d), a root r∈V and a target k≤|V|, compute the minimum length tour that contains r and at least k other vertices. We present a polynomial time
O(\fraclog2 nloglogn·logk)O(\frac{\log^{2} n}{\log\log n}\cdot\log k)-approximation algorithm for this problem. We use this algorithm for directed k-TSP to obtain an
O(\fraclog2 nloglogn)O(\frac{\log^{2} n}{\log\log n})-approximation algorithm for the directed orienteering problem. This answers positively, the question of poly-logarithmic approximability of directed orienteering, an open problem
from Blum et al. (SIAM J. Comput. 37(2):653–670, 2007). The previously best known results were quasi-polynomial time algorithms with approximation guarantees of O(log 2
k) for directed k-TSP, and O(log n) for directed orienteering (Chekuri and Pal in IEEE Symposium on Foundations in Computer Science, pp. 245–253, 2005). Using the algorithm for directed orienteering within the framework of Blum et al. (SIAM J. Comput. 37(2):653–670, 2007) and Bansal et al. (ACM Symposium on Theory of Computing, pp. 166–174, 2004), we also obtain poly-logarithmic approximation algorithms for the directed versions of discounted-reward TSP and vehicle
routing problem with time-windows. 相似文献
16.
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
2). 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. 相似文献
17.
We present an algorithm that finds out-trees and out-branchings with at least k leaves in directed graphs. These problems are known as Directed Maximum Leaf Out-Tree and Directed Maximum Leaf Out-Branching, respectively, and—in the case of undirected graphs—as Maximum Leaf Spanning Tree. The run time of our algorithm is O(4
k
nm) on directed graphs and O(poly(n)+4
k
k
2) on undirected graphs. This improves over the previously fastest algorithms for these problems with run times of 2
O(klog k)
poly(n) and O(poly(n)+6.75
k
poly(k)) respectively. 相似文献
18.
Consider a rooted tree T of arbitrary maximum degree d representing a collection of n web pages connected via a set of links, all reachable from a source home page represented by the root of T. Each web page i carries a probability p
i
representative of the frequency with which it is visited. By adding hotlinks—shortcuts from a node to one of its descendents—we
wish to minimize the expected number of steps l needed to visit pages from the home page, expressed as a function of the entropy H(p) of the access probabilities p. This paper introduces several new strategies for effectively assigning hotlinks in a tree. For assigning exactly one hotlink
per node, our method guarantees an upper bound on l of 1.141H(p)+1 if d>2 and 1.08H(p)+2/3 if d=2. We also present the first efficient general methods for assigning at most k hotlinks per node in trees of arbitrary maximum degree, achieving bounds on l of at most
\frac2H(p)log(k+1)+1\frac{2H(p)}{\log(k+1)}+1
and
\fracH(p)log(k+d)-logd+1\frac{H(p)}{\log(k+d)-\log d}+1
, respectively. All our methods are strong, i.e., they provide the same guarantees on all subtrees after the assignment. We also present an algorithm implementing these
methods in O(nlog n) time, an improvement over the previous O(n
2) time algorithms. Finally we prove a Ω(nlog n) lower bound on the running time of any strong method that guarantee an average access time strictly better than 2H(p). 相似文献
19.
In this paper, we consider source location problems and their generalizations with three connectivity requirements (arc-connectivity
requirements λ and two kinds of vertex-connectivity requirements κ and
), where the source location problems are to find a minimum-cost set S⊆V in a given graph G=(V,A) with a capacity function u:A→ℝ+ such that for each vertex v∈V, the connectivity from S to v (resp., from v to S) is at least a given demand d
−(v) (resp., d
+(v)). We show that the source location problem with edge-connectivity requirements in undirected networks is strongly NP-hard,
which solves an open problem posed by Arata et al. (J. Algorithms 42: 54–68, 2002). Moreover, we show that the source location problems with three connectivity requirements are inapproximable within a ratio
of cln D for some constant c, unless every problem in NP has an O(N
log log N
)-time deterministic algorithm. Here D denotes the sum of given demands. We also devise (1+ln D)-approximation algorithms for all the extended source location problems if we have the integral capacity and demand functions.
By the inapproximable results above, this implies that all the source location problems are Θ(ln ∑
v∈V
(d
+(v)+d
−(v)))-approximable.
An extended abstract of this paper appeared in Sakashita et al. (Proceedings of LATIN 2006, Chile, LNCS, vol. 3887, pp. 769–780, March 2006). 相似文献
20.
Parallel integer sorting and simulation amongst CRCW models 总被引:1,自引:0,他引:1
Sanjeev Saxena 《Acta Informatica》1996,33(7):607-619
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)2). Algorithm for COMMON uses n processors.
Received August 13, 1992/June 30, 1995 相似文献