共查询到20条相似文献,搜索用时 15 毫秒
1.
Prosenjit Bose Paz Carmi Mohammad Farshi Anil Maheshwari Michiel Smid 《Algorithmica》2010,58(3):711-729
The greedy algorithm produces high-quality spanners and, therefore, is used in several applications. However, even for points
in d-dimensional Euclidean space, the greedy algorithm has near-cubic running time. In this paper, we present an algorithm that
computes the greedy spanner for a set of n points in a metric space with bounded doubling dimension in
O(n2logn)\ensuremath {\mathcal {O}}(n^{2}\log n)
time. Since computing the greedy spanner has an Ω(n
2) lower bound, the time complexity of our algorithm is optimal within a logarithmic factor. 相似文献
2.
Given an undirected graph and 0 £ e £ 1{0\le\epsilon\le1}, a set of nodes is called an e{\epsilon}-near clique if all but an e{\epsilon} fraction of the pairs of nodes in the set have a link between them. In this paper we present a fast synchronous network algorithm
that uses small messages and finds a near-clique. Specifically, we present a constant-time algorithm that finds, with constant
probability of success, a linear size e{\epsilon}-near clique if there exists an e3{\epsilon^3}-near clique of linear size in the graph. The algorithm uses messages of O(log n) bits. The failure probability can be reduced to n
−Ω(1) by increasing the time complexity by a logarithmic factor, and the algorithm also works if the graph contains a clique of
size Ω(n/(log log n)
α
) for some a ? (0,1){\alpha \in (0,1)}. Our approach is based on a new idea of adapting property testing algorithms to the distributed setting. 相似文献
3.
We show a construction of a PCP with both sub-constant error and almost-linear size. Specifically, for some constant 0 < α < 1, we construct a PCP verifier for checking satisfiability of Boolean formulas that on input of size n uses log n+O((log n)1-a)\log\, n+O((\log\, n)^{1-\alpha}) random bits to make 7 queries to a proof of size n·2O((log n)1-a)n·2^{O((\log\, n)^{1-\alpha})}, where each query is answered by O((log n)1-a)O((\log\, n)^{1-\alpha}) bit long string, and the verifier has perfect completeness and error 2-W((log n)a)2^{-\Omega((\log\, n)^{\alpha})}. 相似文献
4.
We investigate the arithmetic formula complexity of the elementary symmetric polynomials Skn{S^k_n} . We show that every multilinear homogeneous formula computing Skn{S^k_n} has size at least kW(logk)n{k^{\Omega(\log k)}n} , and that product-depth d multilinear homogeneous formulas for Skn{S^k_n} have size at least 2W(k1/d)n{2^{\Omega(k^{1/d})}n} . Since Sn2n{S^{n}_{2n}} has a multilinear formula of size O(n
2), we obtain a superpolynomial separation between multilinear and multilinear homogeneous formulas. We also show that Skn{S^k_n} can be computed by homogeneous formulas of size kO(logk)n{k^{O(\log k)}n} , answering a question of Nisan and Wigderson. Finally, we present a superpolynomial separation between monotone and non-monotone
formulas in the noncommutative setting, answering a question of Nisan. 相似文献
5.
We investigate the diameter
problem in the streaming and sliding-window
models. We show that, for
a stream of nn points or a sliding window of size nn, any exact
algorithm for diameter requires W(n)\Omega(n) bits of
space. We present a simple e\epsilon-approximation algorithm
for computing the diameter in the streaming model. Our main result
is an e\epsilon-approximation algorithm
that maintains the diameter in two dimensions in the sliding-window
model using O((1/e3/2) log3n(logR+loglogn + log(1/e)))O(({1}/{\epsilon^{3/2}}) \log^{3}n(\log R+\log\log n +
\log ({1}/{\epsilon}))) bits of space, where RR is the maximum, over all
windows, of the ratio of the diameter to the minimum non-zero distance
between any two points in the window. 相似文献
6.
We prove that the concept class of disjunctions cannot be pointwise approximated by linear combinations of any small set of
arbitrary real-valued functions. That is, suppose that there exist functions f1, ?, fr\phi_{1}, \ldots , \phi_{r} : {− 1, 1}n →
\mathbbR{\mathbb{R}} with the property that every disjunction f on n variables has $\|f - \sum\nolimits_{i=1}^{r} \alpha_{i}\phi
_{i}\|_{\infty}\leq 1/3$\|f - \sum\nolimits_{i=1}^{r} \alpha_{i}\phi
_{i}\|_{\infty}\leq 1/3 for some reals a1, ?, ar\alpha_{1}, \ldots , \alpha_{r}. We prove that then $r \geq
exp \{\Omega(\sqrt{n})\}$r \geq
exp \{\Omega(\sqrt{n})\}, which is tight. We prove an incomparable lower bound for the concept class of decision lists. For the concept class of majority
functions, we obtain a lower bound of W(2n/n)\Omega(2^{n}/n) , which almost meets the trivial upper bound of 2n for any concept class. These lower bounds substantially strengthen and generalize the polynomial approximation lower bounds of Paturi
(1992) and show that the regression-based agnostic learning algorithm of Kalai et al. (2005) is optimal. 相似文献
7.
We consider the distributed complexity of the stable matching problem (a.k.a. “stable marriage”). In this problem, the communication graph is undirected and bipartite, and each node ranks its neighbors. Given a matching of the nodes, a pair of unmatched nodes is called blocking if they prefer each other to their assigned match. A matching is called stable if it does not induce any blocking pair. In the distributed model, nodes exchange messages in each round over the communication links, until they find a stable matching. We show that if messages may contain at most B bits each, then any distributed algorithm that solves the stable matching problem requires ${\Omega(\sqrt{n/B\log n})}We consider the distributed complexity of the stable matching problem (a.k.a. “stable marriage”). In this problem, the communication
graph is undirected and bipartite, and each node ranks its neighbors. Given a matching of the nodes, a pair of unmatched nodes
is called blocking if they prefer each other to their assigned match. A matching is called stable if it does not induce any
blocking pair. In the distributed model, nodes exchange messages in each round over the communication links, until they find
a stable matching. We show that if messages may contain at most B bits each, then any distributed algorithm that solves the stable matching problem requires W(?{n/Blogn}){\Omega(\sqrt{n/B\log n})} communication rounds in the worst case, even for graphs of diameter O(log n), where n is the number of nodes in the graph. Furthermore, the lower bound holds even if we allow the output to contain O(?n){O(\sqrt n)} blocking pairs, and if a pair is considered blocking only if they like each other much more then their assigned match. 相似文献
8.
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. 相似文献
9.
Coalition formation for task allocation: theory and algorithms 总被引:1,自引:0,他引:1
This paper focuses on coalition formation for task allocation in both multi-agent and multi-robot domains. Two different problem
formalizations are considered, one for multi-agent domains where agent resources are transferable and one for multi-robot
domains. We demonstrate complexity theoretic differences between both models and show that, under both, the coalition formation
problem, with m tasks, is NP-hard to both solve exactly and to approximate within a factor of O(m1-e){O(m^{1-\epsilon})} for all ${\epsilon > 0}${\epsilon > 0}. Two natural restrictions of the coalition formation problem are considered. In the first situation agents are drawn from
a set of j types. Agents of each type are indistinguishable from one another. For this situation a dynamic programming based approach
is presented, which, for fixed j finds the optimal coalition structure in polynomial time and is applicable in both multi-agent and multi-robot domains. We
then consider situations where coalitions are restricted to k or fewer agents. We present two different algorithms. Each guarantees the generated solution to be within a constant factor,
for fixed k, of the optimal in terms of utility. Our algorithms complement Shehory and Kraus’ algorithm (Artif Intell 101(1–2):165–200,
1998), which provides guarantee’s on solution cost, as ours provides guarantees on utility. Our algorithm for general multi-agent
domains is a modification of and has the same running time as Shehory and Kraus’ algorithm, while our approach for multi-robot
domains runs in time
O(n\frac32m){O(n^{\frac{3}{2}}m)}, much faster than Vig and Adams (J Intell Robot Syst 50(1):85–118, 2007) modifications to Shehory and Kraus’ algorithm for
multi-robot domains, which ran in time O(n
k
m), for n agents and m tasks. 相似文献
10.
We show that every languageL in the class ACC can be recognized by depth-two deterministic circuits with a symmetric-function gate at the root and
AND gates of fan-in log
O(1)
n at the leaves, or equivalently, there exist polynomialsp
n
(x
1
,..., x
n
) overZ of degree log
O(1)
n and with coefficients of magnitude
and functionsh
n
:Z{0,1} such that for eachn and eachx{0,1}
n
,XL
(x)
=h
n
(p
n
(x
1
,...,x
n
)). This improves an earlier result of Yao (1985). We also analyze and improve modulus-amplifying polynomials constructed by Toda (1991) and Yao (1985). 相似文献
11.
We present a general framework for designing fast subexponential exact and parameterized algorithms on planar graphs. Our approach is based on geometric properties of planar branch decompositions obtained by Seymour and Thomas, combined with refined techniques of dynamic programming on planar graphs based on properties of non-crossing partitions. To exemplify our approach we show how to obtain an $O(2^{6.903\sqrt{n}})We present a general framework for designing fast subexponential exact and parameterized algorithms on planar graphs. Our
approach is based on geometric properties of planar branch decompositions obtained by Seymour and Thomas, combined with refined
techniques of dynamic programming on planar graphs based on properties of non-crossing partitions. To exemplify our approach
we show how to obtain an
O(26.903?n)O(2^{6.903\sqrt{n}})
time algorithm solving weighted Hamiltonian Cycle on an n-vertex planar graph. Similar technique solves Planar Graph Travelling Salesman Problem with n cities in time
O(29.8594?n)O(2^{9.8594\sqrt{n}})
. Our approach can be used to design parameterized algorithms as well. For example, we give an algorithm that for a given
k decides if a planar graph on n vertices has a cycle of length at least k in time
O(213.6?kn+n3)O(2^{13.6\sqrt{k}}n+n^{3})
. 相似文献
12.
Davod Khojasteh Salkuyeh 《Soft Computing - A Fusion of Foundations, Methodologies and Applications》2011,15(5):953-961
In this paper, we consider the fuzzy Sylvester matrix equation AX+XB=C,AX+XB=C, where
A ? \mathbbRn ×nA\in {\mathbb{R}}^{n \times n} and
B ? \mathbbRm ×mB\in {\mathbb{R}}^{m \times m} are crisp M-matrices, C is an n×mn\times m fuzzy matrix and X is unknown. We first transform this system to an (mn)×(mn)(mn)\times (mn) fuzzy system of linear equations. Then, we investigate the existence and uniqueness of a fuzzy solution to this system. We
use the accelerated over-relaxation method to compute an approximate solution to this system. Some numerical experiments are
given to illustrate the theoretical results. 相似文献
13.
We study some problems solvable in deterministic polynomial time given oracle access to the (promise version of) Arthur–Merlin
class. Our main results are the following:
° BPPNP|| í PprAM||.\circ\quad{\rm BPP}^{{\rm NP}}_{||} \subseteq {{\rm P}^{{{\rm pr}{\rm AM}}}_{||}}. 相似文献
14.
Hongzhong Wu 《Acta Informatica》1994,31(3):285-299
This paper presents a new approach to construct a smalln-column 0, 1-matrix for two given integersn andk(k
15.
Abstract. Let S be a set of n points in a metric space, and let k be a positive integer. Algorithms are given that construct k -fault-tolerant spanners for S . If in such a spanner at most k vertices and/ or edges are removed, then each pair of points in the remaining graph is still connected by a ``short' path. First, an algorithm
is given that transforms an arbitrary spanner into a k -fault-tolerant spanner. For the Euclidean metric in R
d
, this leads to an O(n log n + c
k
n) -time algorithm that constructs a k -fault-tolerant spanner of degree O(c
k
) , whose total edge length is O(c
k
) times the weight of a minimum spanning tree of S , for some constant c . For constant values of k , this result is optimal. In the second part of the paper, algorithms are presented for the Euclidean metric in R
d
. These algorithms construct (i) in O(n log n + k
2
n) time, a k -fault-tolerant spanner with O(k
2
n) edges, and (ii) in O(k n log n) time, such a spanner with O(k n log n) edges. 相似文献
16.
Given a “black box” function to evaluate an unknown rational polynomial
f ? \mathbbQ[x]f \in {\mathbb{Q}}[x] at points modulo a prime p, we exhibit algorithms to compute the representation of the polynomial in the sparsest shifted power basis. That is, we determine
the sparsity $t \in {\mathbb{Z}}_{>0}$t \in {\mathbb{Z}}_{>0}, the shift
a ? \mathbbQ\alpha \in {\mathbb{Q}}, the exponents 0 £ e1 < e2 < ? < et{0 \leq e_{1} < e_{2} < \cdots < e_{t}}, and the coefficients
c1, ?, ct ? \mathbbQ \{0}c_{1}, \ldots , c_{t} \in {\mathbb{Q}} \setminus \{0\} such that
|
设为首页 | 免责声明 | 关于勤云 | 加入收藏 |
Copyright©北京勤云科技发展有限公司 京ICP备09084417号 |