共查询到20条相似文献,搜索用时 31 毫秒
1.
Cees Duin 《Algorithmica》2005,41(2):131-145
We formulate and study an algorithm for all-pairs
shortest paths in a network with $n $ nodes and $m $ arcs of
positive length. Using the dynamic programming principle of optimality of
subpaths the algorithm avoids redundant updates of distance labels. A shortest $v$--$w$ path, say $\langle v,
r_{1} , r_{2} , \ldots ,
r_{k } = w \rangle$ with $k $ arcs
($k \geq 1$), is only then combined with an arc
$(w,t) \in A$ to update the distance label of pair
$v$--$t$, if $(w,t) $ is present on the shortest
$r_{\ell } $--$ t$ path for each node
$r_{\ell}$ $(\ell=k- 1 , k- 2,
\ldots, 1) $.
The algorithm extracts shortest paths in order of length from a data structure
and builds two shortest path trees per node, an extra effort of
$O(n^{2})$. This way it can execute efficiently only the
aforementioned distance updates, by picking the arcs $(w,t)$ out of
these trees. The time complexity order per distance update and path extraction
is similar as in other algorithms. An implementation with a data structure of
heaps is possible, but a bucket-type data structure may be more appropriate.
The implied number of distance updates does not exceed
$nm_{0}$ ($m_{0}$ being the total number of
shortest path arcs), but is frequently much lower. In extreme cases the new
algorithm applies $O(n^{2})$ distance updates, whereas known
algorithms require $\Omega( n ^{3})$ updates.
The algorithm is especially suited for undirected graphs; here the construction
of one tree per node is sufficient and the computation times halve. 相似文献
2.
Cees Duin 《Algorithmica》2004,41(2):131-145
We formulate and study an algorithm for all-pairs
shortest paths in a network with $n $ nodes and $m $ arcs of
positive length. Using the dynamic programming principle of optimality of
subpaths the algorithm avoids redundant updates of distance labels. A shortest $v$--$w$ path, say $\langle v,
r_{1} , r_{2} , \ldots ,
r_{k } = w \rangle$ with $k $ arcs
($k \geq 1$), is only then combined with an arc
$(w,t) \in A$ to update the distance label of pair
$v$--$t$, if $(w,t) $ is present on the shortest
$r_{\ell } $--$ t$ path for each node
$r_{\ell}$ $(\ell=k- 1 , k- 2,
\ldots, 1) $.
The algorithm extracts shortest paths in order of length from a data structure
and builds two shortest path trees per node, an extra effort of
$O(n^{2})$. This way it can execute efficiently only the
aforementioned distance updates, by picking the arcs $(w,t)$ out of
these trees. The time complexity order per distance update and path extraction
is similar as in other algorithms. An implementation with a data structure of
heaps is possible, but a bucket-type data structure may be more appropriate.
The implied number of distance updates does not exceed
$nm_{0}$ ($m_{0}$ being the total number of
shortest path arcs), but is frequently much lower. In extreme cases the new
algorithm applies $O(n^{2})$ distance updates, whereas known
algorithms require $\Omega( n ^{3})$ updates.
The algorithm is especially suited for undirected graphs; here the construction
of one tree per node is sufficient and the computation times halve. 相似文献
3.
We investigate the diameter
problem in the streaming and sliding-window
models. We show that, for
a stream of $n$ points or a sliding window of size $n$, any exact
algorithm for diameter requires $\Omega(n)$ bits of
space. We present a simple $\epsilon$-approximation algorithm
for computing the diameter in the streaming model. Our main result
is an $\epsilon$-approximation algorithm
that maintains the diameter in two dimensions in the sliding-window
model using $O(({1}/{\epsilon^{3/2}}) \log^{3}n(\log R+\log\log n +
\log ({1}/{\epsilon})))$ bits of space, where $R$ 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. 相似文献
4.
For hyper-rectangles in $\mathbb{R}^{d}$ Auer (1997) proved a PAC bound of $O(\frac{1}{\varepsilon}(d+\log \frac{1}{\delta}))$ , where $\varepsilon$ and $\delta$ are the accuracy and confidence parameters. It is still an open question whether one can obtain the same bound for intersection-closed concept classes of VC-dimension $d$ in general. We present a step towards a solution of this problem showing on one hand a new PAC bound of $O(\frac{1}{\varepsilon}(d\log d + \log \frac{1}{\delta}))$ for arbitrary intersection-closed concept classes, complementing the well-known bounds $O(\frac{1}{\varepsilon}(\log \frac{1}{\delta}+d\log \frac{1}{\varepsilon}))$ and $O(\frac{d}{\varepsilon}\log \frac{1}{\delta})$ of Blumer et al. and (1989) and Haussler, Littlestone and Warmuth (1994). Our bound is established using the closure algorithm, that generates as its hypothesis the intersection of all concepts that are consistent with the positive training examples. On the other hand, we show that many intersection-closed concept classes including e.g. maximum intersection-closed classes satisfy an additional combinatorial property that allows a proof of the optimal bound of $O(\frac{1}{\varepsilon}(d+\log \frac{1}{\delta}))$ . For such improved bounds the choice of the learning algorithm is crucial, as there are consistent learning algorithms that need $\Omega(\frac{1}{\varepsilon}(d\log\frac{1}{\varepsilon} +\log\frac{1}{\delta}))$ examples to learn some particular maximum intersection-closed concept classes. 相似文献
5.
Thomas Watson 《Computational Complexity》2013,22(4):727-769
We define a combinatorial checkerboard to be a function f : {1, . . . , m} d → {1,?1} of the form ${f(u_1,\ldots,u_d)=\prod_{i=1}^df_i(u_i)}$ for some functions f i : {1, . . . , m} → {1,?1}. This is a variant of combinatorial rectangles, which can be defined in the same way but using {0, 1} instead of {1,?1}. We consider the problem of constructing explicit pseudorandom generators for combinatorial checkerboards. This is a generalization of small-bias generators, which correspond to the case m = 2. We construct a pseudorandom generator that ${\epsilon}$ -fools all combinatorial checkerboards with seed length ${O\bigl(\log m+\log d\cdot\log\log d+\log^{3/2} \frac{1}{\epsilon}\bigr)}$ . Previous work by Impagliazzo, Nisan, and Wigderson implies a pseudorandom generator with seed length ${O\bigl(\log m+\log^2d+\log d\cdot\log\frac{1}{\epsilon}\bigr)}$ . Our seed length is better except when ${\frac{1}{\epsilon}\geq d^{\omega(\log d)}}$ . 相似文献
6.
Non-Clairvoyant Scheduling for Minimizing Mean Slowdown 总被引:1,自引:0,他引:1
We consider the problem of scheduling dynamically arriving jobs in a non-clairvoyant setting, that is, when the size of a job in remains unknown until the job finishes execution. Our focus is on minimizing the mean slowdown, where the slowdown (also known as stretch) of a job is defined as the ratio of the flow time to the size of the job. We use resource augmentation in terms of allowing a faster processor to the online algorithm to make up for its lack of knowledge of job sizes. Our main result is that the Shortest Elapsed Time First (SETF) algorithm, a close variant of which is used in the Windows NT and Unix operating system scheduling policies, is a $(1+\epsilon)$-speed, $O((1/\epsilon)^5 \log^2 B)$-competitive algorithm for minimizing mean slowdown non-clairvoyantly, when $B$ is the ratio between the largest and smallest job sizes. In a sense, this provides a theoretical justification of the effectiveness of an algorithm widely used in practice. On the other hand, we also show that any $O(1)$-speed algorithm, deterministic or randomized, is $\Omega(\min(n,\log B))$-competitive. The motivation for resource augmentation is supported by an $\Omega(\min(n,B))$ lower bound on the competitive ratio without any speedup. For the static case, i.e., when all jobs arrive at time 0, we show that SETF is $O(\log{B})$ competitive without any resource augmentation and also give a matching $\Omega(\log{B})$ lower bound on the competitiveness. 相似文献
7.
Given a set $\T$ of rooted, unordered trees,
where each $T_i \in \T$ is distinctly leaf-labeled by a set $\Lambda(T_i)$
and where the sets $\Lambda(T_i)$ may overlap,
the maximum agreement supertree problem~(MASP) is to construct a distinctly
leaf-labeled tree $Q$
with leaf set $\Lambda(Q) \subseteq $\cup$_{T_i \in \T} \Lambda(T_i)$
such that $|\Lambda(Q)|$ is maximized and for each $T_i \in \T$,
the topological restriction of $T_i$ to $\Lambda(Q)$ is isomorphic to
the topological restriction of $Q$ to $\Lambda(T_i)$.
Let $n = \left| $\cup$_{T_i \in \T} \Lambda(T_i)\right|$,
$k = |\T|$, and $D = \max_{T_i \in \T}\{\deg(T_i)\}$.
We first show that MASP with $k = 2$ can be solved
in $O(\sqrt{D} n \log (2n/D))$ time, which is $O(n \log n)$ when
$D = O(1)$ and $O(n^{1.5})$ when $D$ is unrestricted.
We then present an algorithm for MASP with $D = 2$ whose running time is polynomial if $k = O(1)$.
On the other hand, we prove that MASP is NP-hard for any fixed
$k \geq 3$ when $D$ is unrestricted,
and also NP-hard for any fixed $D \geq 2$ when $k$ is unrestricted even if
each input tree is required to contain at most three leaves.
Finally, we describe a polynomial-time $(n/\!\log n)$-approximation algorithm
for MASP. 相似文献
8.
We present a technique for analyzing the number of cache misses incurred by multithreaded cache oblivious algorithms on an
idealized parallel machine in which each processor has a private cache. We specialize this technique to computations executed
by the Cilk work-stealing scheduler on a machine with dag-consistent shared memory. We show that a multithreaded cache oblivious
matrix multiplication incurs
cache misses when executed by the Cilk scheduler on a machine with P processors, each with a cache of size Z, with high probability. This bound is tighter than previously published bounds. We also present a new multithreaded cache
oblivious algorithm for 1D stencil computations incurring
cache misses with high probability, one for Gaussian elimination and back substitution, and one for the length computation
part of the longest common subsequence problem incurring
cache misses with high probability.
This work was supported in part by the Defense Advanced Research Projects Agency (DARPA) under contract No. NBCH30390004. 相似文献
9.
We obtain subquadratic algorithms for 3SUM on integers and rationals in several models. On a standard word RAM with w-bit words, we obtain a running time of
. In the circuit RAM with one nonstandard AC
0 operation, we obtain
. In external memory, we achieve O(n
2/(MB)), even under the standard assumption of data indivisibility. Cache-obliviously, we obtain a running time of
. In all cases, our speedup is almost quadratic in the “parallelism” the model can afford, which may be the best possible.
Our algorithms are Las Vegas randomized; time bounds hold in expectation, and in most cases, with high probability. 相似文献
10.
For a set of rooted, unordered, distinctly leaf-labeled trees, the NP-hard maximum agreement subtree problem (MAST) asks for
a tree contained (up to isomorphism or homeomorphism) in all of the input trees with as many labeled leaves as possible. We
study the ordered variants of MAST where the trees are uniformly or non-uniformly ordered. We provide the first known polynomial-time
algorithms for the uniformly and non-uniformly ordered homeomorphic variants as well as the uniformly and non-uniformly ordered
isomorphic variants of MAST.
Our algorithms run in time
,
,
, and
, respectively, where n is the number of leaf labels and k is
the number of input trees. 相似文献
11.
The increased availability of data describing biological interactions provides important clues on how complex chains of genes
and proteins interact with each other. Most previous approaches either restrict their attention to analyzing simple substructures
such as paths or trees in these graphs, or use heuristics that do not provide performance guarantees when general substructures
are analyzed. We investigate a formulation to model pathway structures directly and give a probabilistic algorithm to find
an optimal path structure in
time and
space, where n and m are respectively the number of vertices and the number of edges in the given network, k is the number
of vertices in the path structure, and t is the maximum number of vertices (i.e., "width") at each level of the structure.
Even for the case t = 1 which corresponds to finding simple paths of length k, our time complexity
is a significant improvement over previous probabilistic approaches. To allow for the analysis of multiple pathway structures,
we further consider a variant of the algorithm that provides probabilistic guarantees for the top suboptimal path structures
with a slight increase in time and space. We show that our algorithm can identify pathway structures with high sensitivity
by applying it to protein interaction networks in the DIP database. 相似文献
12.
For a set $P$ of $n$ points in the plane and an integer $k \leq
n$, consider the problem of finding the smallest circle enclosing
at least $k$ points of $P$. We present a randomized algorithm
that computes in $O( n k )$ expected time such a circle, improving
over previously known algorithms. Further, we present a linear
time $\delta$-approximation algorithm that outputs a circle that
contains at least $k$ points of $P$ and has radius less than
$(1+\delta)r_{opt}(P,k)$, where $r_{opt}(P,k)$ is the radius of the
minimum circle containing at least $k$ points of $P$. The expected
running time of this approximation algorithm is $O(n + n
\cdot\min((1/k\delta^3) \log^2 (1/\delta),
k))$. 相似文献
13.
Zeev Nutov 《Algorithmica》2006,44(3):213-231
A graph is called {\em $\el$-connected from $U$ to $r$} if there are $\el$
internally disjoint paths from every node $u \in U$ to $r$.
The {\em Rooted Subset Connectivity Augmentation Problem} ({\em RSCAP}) is as
follows: given a graph $G=(V+r,E)$, a node subset $U \subseteq V$, and an
integer $k$, find a smallest set $F$ of new edges such that $G+F$ is
$k$-connected from $U$ to $r$.
In this paper we consider mainly a restricted version of RSCAP in which the
input graph $G$ is already $(k-1)$-connected from $U$ to $r$.
For this version we give an $O(\ln\! |U|)$-approximation algorithm, and
show that the problem cannot achieve a better approximation guarantee than
the Set Cover Problem (SCP) on $|U|$ elements and with $|V|-|U|$ sets.
For the general version of RSCAP we give an
$O(\ln k \ln\!|U|)$-approximation algorithm.
For $U=V$ we get the {\em Rooted Connectivity Augmentation Problem}
({\em RCAP}).
For directed graphs RCAP is polynomially solvable,
but for undirected graphs its complexity status is not known:
no polynomial algorithm is known, and it is also not known to be NP-hard.
For undirected graphs with the input graph $G$ being
$(k-1)$-connected from $V$ to $r$, we give an algorithm
that computes a solution of size at most ${\it opt}+\min\{opt,k\}/2$, where
{\it opt} denotes the optimal solution size. 相似文献
14.
Gábor Wiener 《Algorithmica》2013,67(3):315-323
A set system $\mathcal{H} \subseteq2^{[m]}$ is said to be separating if for every pair of distinct elements x,y∈[m] there exists a set $H\in\mathcal{H}$ such that H contains exactly one of them. The search complexity of a separating system $\mathcal{H} \subseteq 2^{[m]}$ is the minimum number of questions of type “x∈H?” (where $H \in\mathcal{H}$ ) needed in the worst case to determine a hidden element x∈[m]. If we receive the answer before asking a new question then we speak of the adaptive complexity, denoted by $\mathrm{c} (\mathcal{H})$ ; if the questions are all fixed beforehand then we speak of the non-adaptive complexity, denoted by $\mathrm{c}_{na} (\mathcal{H})$ . If we are allowed to ask the questions in at most k rounds then we speak of the k-round complexity of $\mathcal{H}$ , denoted by $\mathrm{c}_{k} (\mathcal{H})$ . It is clear that $|\mathcal{H}| \geq\mathrm{c}_{na} (\mathcal{H}) = \mathrm{c}_{1} (\mathcal{H}) \geq\mathrm{c}_{2} (\mathcal{H}) \geq\cdots\geq\mathrm{c}_{m} (\mathcal{H}) = \mathrm{c} (\mathcal{H})$ . A group of problems raised by G.O.H. Katona is to characterize those separating systems for which some of these inequalities are tight. In this paper we are discussing set systems $\mathcal{H}$ with the property $|\mathcal{H}| = \mathrm{c}_{k} (\mathcal{H}) $ for any k≥3. We give a necessary condition for this property by proving a theorem about traces of hypergraphs which also has its own interest. 相似文献
15.
The resource discovery problem was introduced by Harchol-Balter,
Leighton, and Lewin. They developed a number of algorithms
for the problem in the weakly connected directed graph model. This model is a
directed logical graph that represents the vertices’ knowledge about the topology
of the underlying communication network.
The current paper proposes a deterministic algorithm for the
problem in the same model,
with improved time, message, and communication complexities.
Each previous algorithm had a complexity that was higher at least in one of the
measures. Specifically, previous deterministic solutions required either time linear
in the diameter of the initial network, or communication complexity $O(n^3)$ (with
message complexity $O(n^2)$), or message complexity $O(|E_0| \log n)$ (where $E_0$
is the arc set of the initial graph $G_0$). Compared with the main randomized
algorithm of Harchol-Balter, Leighton, and Lewin, the time complexity is reduced
from $O(\log^2n)$ to\pagebreak[4] $O(\log n )$, the message complexity from $O(n \log^2 n)$ to
$O(n \log n )$, and the communication complexity from $O(n^2 \log^3 n)$ to
$O(|E_0|\log ^2 n )$.
\par
Our work significantly extends the connectivity algorithm of Shiloach
and Vishkin which was originally given for a parallel model of computation.
Our result also confirms a conjecture of Harchol-Balter, Leighton, and
Lewin, and addresses an open question due to Lipton. 相似文献
16.
In this paper, we consider the $(\in_{\gamma},\in_{\gamma} \vee \; \hbox{q}_{\delta})$ -fuzzy and $(\overline{\in}_{\gamma},\overline{\in}_{\gamma} \vee \; \overline{\hbox{q}}_{\delta})$ -fuzzy subnear-rings (ideals) of a near-ring. Some new characterizations are also given. In particular, we introduce the concepts of (strong) prime $(\in_{\gamma},\in_{\gamma} \vee \; \hbox{q}_{\delta})$ -fuzzy ideals of near-rings and discuss the relationship between strong prime $(\in_{\gamma},\in_{\gamma} \vee \; \hbox{q}_{\delta})$ -fuzzy ideals and prime $(\in_{\gamma},\in_{\gamma} \vee \; \hbox{q}_{\delta})$ -fuzzy ideals of near-rings. 相似文献
17.
The poor scalability of existing superscalar processors has been of great concern to the computer engineering community.
In particular, the critical-path lengths of many components in existing implementations grow as Θ(n
2
) where n is the fetch width, the issue width, or the window size. This paper describes two scalable processor architectures, Ultrascalar
I and Ultrascalar II, and compares their VLSI complexities (gate delays, wire-length delays, and area.) Both processors are
implemented by a large collection of ALUs with controllers (together called execution stations ) connected together by a network of parallel-prefix tree circuits. A fat-tree network connects an interleaved cache to the
execution stations. These networks provide the full functionality of superscalar processors including renaming, out-of-order
execution, and speculative execution.
The difference between the processors is in the mechanism used to transmit register values from one execution station to
another. Both architectures use a parallel-prefix tree to communicate the register values between the execution stations.
Ultrascalar I transmits an entire copy of the register file to each station, and the station chooses which register values
it needs based on the instruction. Ultrascalar I uses an H-tree layout. Ultrascalar II uses a mesh-of-trees and carefully
sends only the register values that will actually be needed by each subtree to reduce the number of wires required on the
chip.
The complexity results are as follows: The complexity is described for a processor which has an instruction-set architecture
containing L logical registers and can execute n instructions in parallel. The chip provides enough memory bandwidth to execute up to M(n) memory operations per cycle. (M is assumed to have a certain regularity property.) In all the processors, the VLSI area is the square of the wire delay.
Ultrascalar I has gate delay O(log n) and wire delay
\tauwires = \Theta(\sqrt{n}L) if $M(n)$ is $O(n^{1/2-\varepsilon})$,
\tauwires = \Theta(\sqrt{n}(L+\log n)) if $M(n)$ is $\Theta(n^{1/2})$,
\tauwires = \Theta(\sqrt{n}L+M(n)) if $M(n)$ is $\Omega(n^{1/2+\varepsilon})$
for ɛ>0 . Ultrascalar II has gate delay Θ(log L+log n) . The wire delay is Θ(n) , which is optimal for n=O(L) . Thus, Ultrascalar II dominates Ultrascalar I for n=O(L
2
) , otherwise Ultrascalar I dominates Ultrascalar II.
We introduce a hybrid ultrascalar that uses a two-level layout scheme: Clusters of execution stations are layed out using
the Ultrascalar II mesh-of-trees layout, and then the clusters are connected together using the H-tree layout of Ultrascalar
I. For the hybrid (in which n≥ L ), the wire delay is Θ(\sqrt nL+M(n)) , which is optimal. For n≥ L , the hybrid dominates both Ultrascalar I and Ultrascalar II.
We also present an empirical comparison of Ultrascalar I and the hybrid, both layed out using the Magic VLSI editor. For
a processor that has 32 32-bit registers and a simple integer ALU, the hybrid requires about 11 times less area.
Received June 11, 2000, and in revised form March 20, 2001, and in final form August 19, 2001. Online publication April 5,
2002. 相似文献
18.
We consider the problem of approximately integrating a Lipschitz function f (with a known Lipschitz constant) over an interval. The goal is to achieve an additive error of at most ε using as few samples of f as possible. We use the adaptive framework: on all problem instances an adaptive algorithm should perform almost as well
as the best possible algorithm tuned for the particular problem instance. We distinguish between
and
, the performances of the best possible deterministic and randomized algorithms, respectively. We give a deterministic algorithm
that uses
samples and show that an asymptotically better algorithm is impossible. However, any deterministic algorithm requires
samples on some problem instance. By combining a deterministic adaptive algorithm and Monte Carlo sampling with variance reduction,
we give an algorithm that uses at most
samples. We also show that any algorithm requires
samples in expectation on some problem instance (f,ε), which proves that our algorithm is optimal. 相似文献
19.
《国际计算机数学杂志》2012,89(5):665-670
This work is concerned with computing the solution of the following inverse problem: Finding u and 𝜌on D such that: $$\nabla \cdot (\rho \nabla u) = 0,\quad \hbox{on}\ D;$$ $$u = g,\quad \hbox{on}\ \partial D;\qquad \rho u_n = f,\quad \hbox{on}\ \partial D;$$ $$\rho (x_0, y_0) = \rho_0,\quad \hbox{for a given point}\ (x_0, y_0) \in D$$ where f and g are two given continuous functions defined on the boundary of D , and D is a given bounded region of R 2 . The solution is found using a development of the direct variational method. The two unknown functions are represented by linear combinations of certain classes of functions and using multiobjective optimization to minimize the two objective functionals F and H , where $$F = \vint \vint_D \rho (x,y) \nabla u\cdot \nabla u\,\hbox{d}x\,\hbox{d}y\quad \hbox{and}\quad H = \vint_{\partial D} (\rho u_n - f)^2 \hbox{d}s$$ A computer program is written and implemented and tested for data formed by numerical simulation. 相似文献
20.
In 1999 Nakano, Olariu, and Schwing in [20], they showed that the permutation routing of n items pretitled on a mobile ad hoc network (MANET for short) of p stations (p known) and k channels (MANET{(n, p, k)) with k < p, can be carried out in
broadcast rounds if k p and if each station has a
-memory locations. And if k
and if each station has a
-memory locations, the permutations of these n pretitled items can be done also in
broadcast rounds. They used two assumptions: first they suppose that each station of the mobile ad hoc network has an identifier beforehand. Secondly, the stations are partitioned into k groups such that each group has
stations, but it was not shown how this partition can be obtained. In this paper, the stations have not identifiers beforehand and p is unknown. We develop a protocol which first names the stations, secondly gives the value of p, and partitions stations in groups of
stations. Finally we show that the permutation routing problem can be solved on it in
broadcast rounds in the worst case. It can be solved in
broadcast rounds in the better case. Note that our approach does not impose any restriction on k. 相似文献