共查询到20条相似文献，搜索用时 31 毫秒
1.
2.
Abstract. We show that the 2-Opt and 3-Opt heuristics for the traveling salesman problem (TSP) on the complete graph K
n
produce a solution no worse than the average cost of a tour in K
n
in a polynomial number of iterations. As a consequence, we get that the domination numbers of the 2- Opt , 3- Opt , Carlier—Villon,
Shortest Path Ejection Chain, and Lin—Kernighan heuristics are all at least (n-2)! / 2 . The domination number of the Christofides heuristic is shown to be no more than
, and for the Double Tree heuristic and a variation of the Christofides heuristic the domination numbers are shown to be
one (even if the edge costs satisfy the triangle inequality). Further, unless P = NP, no polynomial time approximation algorithm
exists for the TSP on the complete digraph
with domination number at least (n-1)!-k for any constant k or with domination number at least (n-1)! - (( k /(k+1))(n+r))!-1 for any non-negative constants r and k such that (n+r)
0 mod (k+1). The complexities of finding the median value of costs of all the tours in
and of similar problems are also studied. 相似文献
3.
Abstract. We consider a simple restriction of the PRAM model (called PPRAM), where the input is arbitrarily partitioned between a fixed
set of p processors and the shared memory is restricted to m cells. This model allows for investigation of the tradeoffs/ bottlenecks with respect to the communication bandwidth (modeled by the shared memory size m ) and the number of processors p . The model is quite simple and allows the design of optimal algorithms without losing the effect of communication bottlenecks.
We have focused on the PPRAM complexity of problems that have
(n) sequential solutions (where n is the input size), and where m ≤ p ≤ n . We show essentially tight time bounds (up to logarithmic factors) for several problems in this model such as summing, Boolean
threshold, routing, integer sorting, list reversal and k -selection. We get typically two sorts of complexity behaviors for these problems: One type is
(n/p + p/m) , which means that the time scales with the number of processors and with memory size (in appropriate ranges) but not with
both. The other is
(n/m) , which means that the running time does not scale with p and reflects a communication bottleneck (as long as m < p ). We are not aware of any problem whose complexity scales with both p and m (e.g.
). This might explain why in actual implementations one often fails to get p -scalability for p close to n . 相似文献
4.
Abstract. We present a competitive analysis of the LRFU paging algorithm, a hybrid of the LRU (Least Recently Used) and LFU (Least
Frequently Used) paging algorithms. We show that the competitive ratio of LRFU is k +
log(1-λ ) / logλ
- 1, where 1/2 < ≤
λ
≤ 1 is the decay parameter used by the LRFU algorithm, and k is the size of the cache. This supplies, in particular, the first natural paging algorithms that are competitive but are
not optimally competitive, answering a question of Borodin and El-Yaniv. Although LRFU, as it turns out, is not optimally
competitive, it is expected to behave well in practice, as it combines the benefits of both LRU and LFU. 相似文献
5.
Abstract. We describe a quantum black-box network computing the majority of N bits with zero-sided error ɛ using only
queries: the algorithm returns the correct answer with probability at least 1 - ɛ , and ``I don't know' otherwise. Our algorithm is given as a randomized ``XOR decision tree' for which the number of queries
on any input is strongly concentrated around a value of at most 2/3N . We provide a nearly matching lower bound of
on the expected number of queries on a worst-case input in the randomized XOR decision tree model with zero-sided error
o(1) . Any classical randomized decision tree computing the majority on N bits with zero-sided error 1/2 has cost N . 相似文献
6.
Iwata 《Algorithmica》2008,36(4):331-341
Abstract. This paper presents a new algorithm for computing the maximum degree δ
k
(A) of a minor of order k in a matrix pencil A(s) . The problem is of practical significance in the field of numerical analysis and systems control.
The algorithm adopts a general framework of ``combinatorial relaxation' due to Murota. It first solves the weighted bipartite
matching problem to obtain an estimate
on δ
k
(A) , and then checks if the estimate is correct, exploiting the optimal dual solution. In case of incorrectness, it modifies
the matrix pencil A(s) to improve the estimate
without changing δ
k
(A) .
The present algorithm performs this matrix modification by an equivalence transformation with constant matrices, whereas
the previous one uses biproper rational function matrices. Thus the present approach saves memory space and reduces the running
time bound by a factor of rank A . 相似文献
7.
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. 相似文献
8.
Abstract. Given a graph G=(V,E) and a set of vertices M
V , a vertex v ∈ V is said to be controlled by M if the majority of v 's neighbors (including itself) belong to M . M is called a monopoly in G if every vertex v∈ V is controlled by M . For a specified M and a given range for edge set E (E
1
E
E
2
), we try to determine an E such that M is a monopoly in G=(V,E) . We first present a polynomial algorithm for testing if such an E exists, by formulating it as a network flow problem. Assuming that a solution for E does exist, we then show that solutions with the maximum and minimum |E| , respectively, can be found in polynomial time, by solving weighted matching problems.
In case there is no solution for E , we want to maximize the number of vertices controlled by the given M . Unfortunately, this problem turns out to be NP-hard. We, therefore, design a simple approximation algorithm which guarantees
an approximation ratio of 2 . 相似文献
9.
This paper concerns 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 in advance based
on full knowledge about the size and the topology of the network. The first part of the paper examines the two communication
primitives in arbitrary graphs. In particular, for the broadcast task we deliver two new results: a deterministic efficient
algorithm for computing a radio schedule of length D + O(log3
n), and a randomized algorithm for computing a radio schedule of length D + O(log2
n). These results improve on the best currently known D + O(log4
n) time schedule due to Elkin and Kortsarz (Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms, pp. 222–231,
2005). Later we propose a new (efficiently computable) deterministic schedule that uses 2D + Δlog n + O(log3
n) time units to complete the gossiping task in any radio network with size n, diameter D and max-degree Δ. Our new schedule improves and simplifies the currently best known gossiping schedule, requiring time
, for any network with the diameter D = Ω(log
i+4
n), where i is an arbitrary integer constant i ≥ 0, see Gąsieniec et al. (Proceedings of the 11th International Colloquium on Structural Information and Communication Complexity,
vol. 3104, pp. 173–184, 2004). The second part of the paper focuses on radio communication in planar graphs, devising a new
broadcasting schedule using fewer than 3D time slots. This result improves, for small values of D, on the currently best known D + O(log3
n) time schedule proposed by Elkin and Kortsarz (Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms, pp. 222–231,
2005). Our new algorithm should be also seen as a separation result between planar and general graphs with small diameter
due to the polylogarithmic inapproximability result for general graphs by Elkin and Kortsarz (Proceedings of the 7th International
Workshop on Approximation Algorithms for Combinatorial Optimization Problems, vol. 3122, pp. 105–116, 2004; J. Algorithms
52(1), 8–25, 2004).
The second author is supported in part by a grant from the Israel Science Foundation and by the Royal Academy of Engineering.
Part of this research was performed while this author (Q. Xin) was a PhD student at The University of Liverpool. 相似文献
10.
Abstract. We consider the quantum complexities of the following three problems: searching an ordered list, sorting an un-ordered list,
and deciding whether the numbers in a list are all distinct. Letting N be the number of elements in the input list, we prove a lower bound of (1/π )(ln(N )-1) accesses to the list elements for ordered searching, a lower bound of Ω(N logN ) binary comparisons for sorting, and a lower bound of
binary comparisons for element distinctness. The previously best known lower bounds are 1/12 log
2
(N) - O (1) due to Ambainis, Ω(N) , and
, respectively. Our proofs are based on a weighted all-pairs inner product argument.
In addition to our lower bound results, we give an exact quantum algorithm for ordered searching using roughly 0.631 log
2
(N) oracle accesses. Our algorithm uses a quantum routine for traversing through a binary search tree faster than classically,
and it is of a nature very different {from} a faster exact algorithm due to Farhi, Goldstone, Gutmann, and Sipser. 相似文献
11.
We study deterministic gossiping in ad hoc radio networks with large node labels. The labels (identifiers)
of the nodes come from a domain of size N which may be much larger than the size n of the network (the number of nodes). Most
of the work on deterministic communication has been done for the model with small labels which assumes N = O(n). A notable
exception is Peleg's paper, where the problem of deterministic communication in ad hoc radio networks with large labels is
raised and a deterministic broadcasting algorithm is proposed, which runs in O(n2log n) time for N polynomially large in n. The O(nlog2n)-time deterministic broadcasting algorithm for networks with small labels given by Chrobak et al. implies deterministic
O(n log N log n)-time broadcasting and O(n2log2N log n)-time gossiping in networks with large labels. We propose two new deterministic gossiping algorithms for ad hoc radio
networks with large labels, which are the first such algorithms with subquadratic time for polynomially large N. More specifically,
we propose: a deterministic O(n3/2log2N log n)-time gossiping algorithm for directed networks; and a deterministic O(n log2N log2n)-time gossiping algorithm for undirected networks. 相似文献
12.
Abstract. In this paper we deal with two geometric problems arising from heterogeneous parallel computing: how to partition the unit
square into p rectangles of given area s
1
, s
2
, . . . ,s
p
(such that Σ
i=1
p
s
i
= 1 ), so as to minimize either (i) the sum of the p perimeters of the rectangles or (ii) the largest perimeter of the p rectangles? For both problems, we prove NP-completeness and we introduce a 7/4 -approximation algorithm for (i) and a
-approximation algorithm for (ii). 相似文献
13.
14.
Alexander D. Healy 《Computational Complexity》2008,17(1):3-37
We construct a randomness-efficient averaging sampler that is computable by uniform constant-depth circuits with parity gates (i.e., in uniform AC
0[⊕]). Our sampler matches the parameters achieved by random walks on constant-degree expander graphs, allowing us to apply
a variety expander-based techniques within NC
1. For example, we obtain the following results:
Our sampler is based on the zig-zag graph product of Reingold, Vadhan & Wigderson (Annals of Math 2002) and as part of our analysis we givean elementary proof of a generalization of Gillman’s Chernoff Bound for Expander Walks (SIAM Journal on Computing 1998).
相似文献
| • | Randomness-efficient error-reduction for uniform probabilistic NC 1, TC 0, AC 0[⊕] and AC 0: Any function computable by uniform probabilistic circuits with error 1/3 using r random bits is computable by circuits of the same type with error δ using r + O(log(1/δ)) random bits. |
| • | An optimal bitwise ϵ-biased generator in AC 0[⊕]: There exists a 1/2Ω(n)-biased generator G : {0, 1} O(n) → {0, 1}2n for which poly(n)-size uniform AC 0[⊕] circuits can compute G(s) i given (s, i) ∈ {0, 1} O(n) × {0, 1} n . This resolves question raised by Gutfreund and Viola (Random 2004). |
| • | uniform BP · AC 0 ⊆ uniform AC 0/O(n). |
15.
Aminollah Mahabadi Hamid Sarbazi-Azad Ebrahim Khodaie Keivan Navi 《The Journal of supercomputing》2008,45(1):1-14
This paper proposes an efficient parallel algorithm for computing Lagrange interpolation on k-ary n-cube networks. This is done using the fact that a k-ary n-cube can be decomposed into n link-disjoint Hamiltonian cycles. Using these n link-disjoint cycles, we interpolate Lagrange polynomial using full bandwidth of the employed network. Communication in the
main phase of the algorithm is based on an all-to-all broadcast algorithm on the n link-disjoint Hamiltonian cycles exploiting all network channels, and thus, resulting in high-efficiency in using network
resources. A performance evaluation of the proposed algorithm reveals an optimum speedup for a typical range of system parameters
used in current state-of-the-art implementations.
相似文献
| Hamid Sarbazi-AzadEmail: Email: |
16.
A formal definition of a combinatorial topology is presented in this paper for the discrete N-dimensional space defined by the An* lattice. The use of this grid instead of the classical ℤn is based on two arguments:
Their interest in image processing and in the medical imaging field is presented with some examples. 相似文献
| – | It is the optimal sampling grid in the sense of Shannon’s sampling theorem in 2 and 3 dimensions, |
| – | It induces the simplest discrete topology definition because its dual is a K-simplex. |
17.
Abstract. We show how to maintain efficiently a minimum piercing set for a set S of intervals on the line, under insertions and deletions to/from S. A linear-size dynamic data structure is presented, which enables us to compute a new minimum piercing set following an insertion
or deletion in time O(c( S) log |S|), where c (S) is the size of the new minimum piercing set. We also show how to maintain a piercing set for S of size at most (1+ɛ)c (S), for 0 < ɛ ≤ 1 , in
((log |S|)/ɛ) amortized time per update. We then apply these results to obtain efficient solutions to the following three problems: (i)
the shooter location problem, (ii) computing a minimum piercing set for arcs on a circle, and (iii) dynamically maintaining
a box cover for a d -dimensional point set. 相似文献
18.
Erik Melin 《Journal of Mathematical Imaging and Vision》2009,33(3):267-280
We consider different possibilities to define digital manifolds that are locally homeomorphic to Khalimsky n-space. We prove existence and non-existence of certain types of Khalimsky manifolds. An embedding theorem is proved.
We introduce the join operator and use it to analyze the structure of adjacency neighborhoods and of intersections of neighborhoods
in ℤ
n
.
相似文献
| Erik MelinEmail: |
19.
20.
Alexis De Vos 《Open Systems & Information Dynamics》2006,13(2):179-195
If a message can have n different values and all values are equally probable, then the entropy of the message is log(n). In the present paper, we discuss the expectation value of the entropy, for an arbitrary probability distribution. We introduce
a mixture of all possible probability distributions. We assume that the mixing function is uniform
A computation is a manipulation of an incoming message, i.e. a mapping in probability space:
During a reversible computation, no isentropic path in the probability space can be found. Therefore we have to conclude that
a computation cannot be represented by a message which merely follows a path in n-dimensional probability space. Rather, the point representing the mixing function travels along a path in an infinite-dimensional
Hilbert space.
In honour of prof. dr. Henrik Farkas (Department of Chemical Physics, Technical University of Budapest) an outstanding scientist
and most remarkable human being who unfortunately left us on 21 July 2005. 相似文献
| • | either in flat probability space, i.e. the unitary n-dimensional hypertriangle |
| • | or in Bhattacharyya’s spherical statistical space, i.e. the unitary n-dimensional hyperoctant. |
| • | either a reversible mapping, i.e. a symmetry operation (rotation or reflection) in n-dimen sional space |
| • | or an irreversible mapping, i.e. a projection operation from n-dimensional to lower-dimensional space. |