共查询到20条相似文献，搜索用时 31 毫秒
1.
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. 相似文献
2.
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. 相似文献
3.
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 log N ) 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. 相似文献
4.
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 . 相似文献
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/3 N . 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.
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 . 相似文献
8.
The computational complexity of counting the number of matchings of size k in a given triple set has been open. It is conjectured that the problem is not fixed parameter tractable. In this paper,
we present a fixed parameter tractable randomized approximation scheme (FPTRAS) for the problem. More precisely, we develop
a randomized algorithm that, on given positive real numbers ε and δ, and a given set S of n triples and an integer k, produces a number h in time O(5.48 3k
n
2ln (2/ δ)/ ε
2) such that where h
0 is the total number of matchings of size k in the triple set S. Our algorithm is based on the recent improved color-coding techniques and the Monte-Carlo self-adjusting coverage algorithm
developed by Karp, Luby and Madras.
A preliminary version of this paper was presented at The 13th Annual International Computing and Combinatorics Conference (COCOON 2007), July 16–19, 2007, Banff, Alberta, Canada. This work is supported by the National Natural Science Foundation
of China (No. 60433020 and No. 60773111), by the National Basic Research 973 Program of China (No. 2008CB317107), and by the
China Program for New Century Excellent Talents in University (NCET-05-0683). 相似文献
9.
There are only a few ethical regulations that deal explicitly with robots, in contrast to a vast number of regulations, which
may be applied. We will focus on ethical issues with regard to “responsibility and autonomous robots”, “machines as a replacement
for humans”, and “tele-presence”. Furthermore we will examine examples from special fields of application (medicine and healthcare,
armed forces, and entertainment). We do not claim to present a complete list of ethical issue nor of regulations in the field
of robotics, but we will demonstrate that there are legal challenges with regard to these issues.
相似文献
10.
In this paper, we consider the numerical solution of Fredholm integral equations of the second kind: Discretizing the integral equation by a certain quadrature rule, we get the linear system where I is the identity matrix, A is the discretization matrix corresponding to the kernel function a( x, t), and W is a diagonal matrix which depends on the quadrature rule. We propose an approximation scheme based on the polynomial interpolation technique and use the scheme to compute approximation matrices Aa of A and matrices Ba such that ( I+ BaW)( I- AaW) I for sufficiently large N, where N is the number of quadrature points used in the discretization. The approximations Aa and Ba, and the matrix-vector multiplications and , are obtained in O( N) operations by using the approximation scheme. Hence preconditioned iterative methods such as the preconditioned conjugate gradient method and the residual correction scheme are well suited for the solution of the preconditioned system 相似文献
11.
We present a study of using camera-phones and visual-tags to access mobile services. Firstly, a user-experience study is described in which participants were both observed learning to interact with a prototype mobile service and interviewed
about their experiences. Secondly, a pointing-device task is presented in which quantitative data was gathered regarding the speed and accuracy with which participants aimed and clicked
on visual-tags using camera-phones. We found that participants’ attitudes to visual-tag-based applications were broadly positive,
although they had several important reservations about camera-phone technology more generally. Data from our pointing-device
task demonstrated that novice users were able to aim and click on visual-tags quickly (well under 3 s per pointing-device
trial on average) and accurately (almost all meeting our defined speed/accuracy tradeoff of 6% error-rate). Based on our findings,
design lessons for camera-phone and visual-tag applications are presented.
相似文献
12.
We consider Discrete Event Systems that can dynamically allocate resources in order to process tasks with real-time constraints.
In the case of “weakly hard” constraints, a fraction of tasks is allowed to violate them, as long as m out of any k consecutive tasks meet their respective constraints. This is a generalization of a system with purely hard real-time constraints
where m = k = 1. For non-preemptive and aperiodic tasks, we formulate an optimization problem where task processing times are controlled
so as to minimize a cost function while guaranteeing that a “weakly hard” criterion is satisfied. We establish a number of
structural properties of the solution to this problem which lead to an efficient algorithm that does not require any explicit
nonlinear programming problem solver. The low complexity of this algorithm makes it suitable for on-line applications. Simulation
examples illustrate the performance improvements in such optimally controlled systems compared to ad hoc schemes.
相似文献
13.
Ohne Zusammenfassung
相似文献
14.
We provide the complete record of methodology that let us evolve BrilliAnt, the winner of the Ant Wars contest. Ant Wars contestants are virtual ants collecting food on a grid board in the presence
of a competing ant. BrilliAnt has been evolved through a competitive one-population coevolution using genetic programming
and fitnessless selection. In this paper, we detail the evolutionary setup that lead to BrilliAnt’s emergence, assess its
direct and indirect human-competitiveness, and describe the behavioral patterns observed in its strategy.
相似文献
15.
Documents and authors can be clustered into “knowledge communities” based on the overlap in the papers they cite. We introduce
a new clustering algorithm, Streemer, which finds cohesive foreground clusters embedded in a diffuse background, and use it
to identify knowledge communities as foreground clusters of papers which share common citations. To analyze the evolution
of these communities over time, we build predictive models with features based on the citation structure, the vocabulary of
the papers, and the affiliations and prestige of the authors. Findings include that scientific knowledge communities tend
to grow more rapidly if their publications build on diverse information and if they use a narrow vocabulary.
相似文献
16.
A number of mobile applications have emerged that allow users to locate one another. However, people have expressed concerns
about the privacy implications associated with this class of software, suggesting that broad adoption may only happen to the
extent that these concerns are adequately addressed. In this article, we report on our work on P eopleF inder, an application that enables cell phone and laptop users to selectively share their locations with others (e.g. friends,
family, and colleagues). The objective of our work has been to better understand people’s attitudes and behaviors towards
privacy as they interact with such an application, and to explore technologies that empower users to more effectively and
efficiently specify their privacy preferences (or “policies”). These technologies include user interfaces for specifying rules
and auditing disclosures, as well as machine learning techniques to refine user policies based on their feedback. We present
evaluations of these technologies in the context of one laboratory study and three field studies.
相似文献
17.
This paper introduces the problem of discovering maximum-length repeating patterns in music objects. A novel algorithm is
presented for the extraction of this kind of patterns from a melody music object. The proposed algorithm discovers all maximum-length
repeating patterns using an “aggressive” accession during searching, by avoiding costly repetition frequency calculation and
by examining as few as possible repeating patterns in order to reach the maximum-length repeating pattern(s). Detailed experimental
results illustrate the significant performance gains due to the proposed algorithm, compared to an existing baseline algorithm.
相似文献
18.
A polynomial-time algorithm is presented for partitioning a collection of sporadic tasks among the processors of an identical
multiprocessor platform. Since the partitioning problem is NP-hard in the strong sense, this algorithm is unlikely to be optimal.
A quantitative characterization of its worst-case performance is provided in terms of resource augmentation.
相似文献
19.
This viewpoint argues that the introduction of most computer-based system to an organization transforms the organization and
changes the work patterns of the system’s users in the organization. These changes interact with the users’ values and beliefs
and trigger emotional responses which are sometimes directed against the software system and its proponents. A requirements
engineer must be aware of these emotions.
相似文献
20.
This paper describes the simulated car racing competition that was arranged as part of the 2007 IEEE Congress on Evolutionary
Computation. Both the game that was used as the domain for the competition, the controllers submitted as entries to the competition
and its results are presented. With this paper, we hope to provide some insight into the efficacy of various computational
intelligence methods on a well-defined game task, as well as an example of one way of running a competition. In the process,
we provide a set of reference results for those who wish to use the simplerace game to benchmark their own algorithms. The paper is co-authored by the organizers and participants of the competition.
相似文献
|
