共查询到20条相似文献,搜索用时 0 毫秒
1.
Katalin Friedl Gábor Ivanyos Miklos Santha Yves F. Verhoeven 《Theory of Computing Systems》2009,45(3):629-646
We present several results on the complexity of various forms of Sperner’s Lemma in the black-box model of computing. We give
a deterministic algorithm for Sperner problems over pseudo-manifolds of arbitrary dimension. The query complexity of our algorithm
is linear in the separation number of the skeleton graph of the manifold and the size of its boundary. As a corollary we get
an
deterministic query algorithm for the black-box version of the problem 2D-SPERNER, a well studied member of Papadimitriou’s complexity class PPAD. This upper bound matches the
deterministic lower bound of Crescenzi and Silvestri. The tightness of this bound was not known before. In another result
we prove for the same problem an
lower bound for its probabilistic, and an
lower bound for its quantum query complexity, showing that all these measures are polynomially related.
Research supported by the European Commission IST Integrated Project Qubit Application (QAP) 015848, the OTKA grants T42559
and T46234, and by the ANR Blanc AlgoQP grant of the French Research Ministry. 相似文献
2.
The quantum query complexity of searching for local optima has been a subject of much interest in the recent literature. For the d-dimensional grid graphs, the complexity has been determined asymptotically for all fixed d≥5, but the lower dimensional cases present special difficulties, and considerable gaps exist in our knowledge. In the present paper we present near-optimal lower bounds, showing that the quantum query complexity for the 2-dimensional grid [n]2 is Ω(n 1/2?δ ), and that for the 3-dimensional grid [n]3 is Ω(n 1?δ ), for any fixed δ>0.A general lower bound approach for this problem, initiated by Aaronson (based on Ambainis’ adversary method for quantum lower bounds), uses random walks with low collision probabilities. This approach encounters obstacles in deriving tight lower bounds in low dimensions due to the lack of degrees of freedom in such spaces. We solve this problem by the novel construction and analysis of random walks with non-uniform step lengths. The proof employs in a nontrivial way sophisticated results of Sárközy and Szemerédi, Bose and Chowla, and Halász from combinatorial number theory, as well as less familiar probability tools like Esseen’s Inequality. 相似文献
3.
We consider the following network design problem; Given a vertex set V with a metric cost c on V, an integer k≥1, and a degree specification b, find a minimum cost k-edge-connected multigraph on V under the constraint that the degree of each vertex v∈V is equal to b(v). This problem generalizes metric TSP. In this paper, we show that the problem admits a ρ-approximation algorithm if b(v)≥2, v∈V, where ρ=2.5 if k is even, and ρ=2.5+1.5/k if k is odd. We also prove that the digraph version of this problem admits a 2.5-approximation algorithm and discuss some generalization
of metric TSP. 相似文献
4.
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. 相似文献
5.
A graph is König-Egerváry if the size of a minimum vertex cover equals that of a maximum matching in the graph. These graphs have been studied extensively from a graph-theoretic point of view. In this paper, we introduce and study the algorithmic complexity of finding König-Egerváry subgraphs of a given graph. In particular, given a graph G and a nonnegative integer k, we are interested in the following questions: We show that these problems are NP-complete and study their complexity from the points of view of approximation and parameterized complexity. Towards this end, we first study the algorithmic complexity of Above Guarantee Vertex Cover, where one is interested in minimizing the additional number of vertices needed beyond the maximum matching size for the vertex cover. Further, while studying the parameterized complexity of the problem of deleting k vertices to obtain a König-Egerváry graph, we show a number of interesting structural results on matchings and vertex covers which could be useful in other contexts.
相似文献
- 1.does there exist a set of k vertices (edges) whose deletion makes the graph König-Egerváry?
- 2.does there exist a set of k vertices (edges) that induce a König-Egerváry subgraph?
6.
Emilio Di Giacomo Walter Didimo Giuseppe Liotta Henk Meijer 《Theory of Computing Systems》2011,49(3):565-575
In this paper we study non-planar drawings of graphs, and study trade-offs between the crossing resolution (i.e., the minimum
angle formed by two crossing segments), the curve complexity (i.e., maximum number of bends per edge), the total number of
bends, and the area. 相似文献
7.
8.
We study the approximation of the smallest eigenvalue of a Sturm–Liouville problem in the classical and quantum settings. We consider a univariate Sturm–Liouville eigenvalue problem with a nonnegative function q from the class C2 ([0,1]) and study the minimal number n() of function evaluations or queries that are necessary to compute an -approximation of the smallest eigenvalue. We prove that n()=(–1/2) in the (deterministic) worst case setting, and n()=(–2/5) in the randomized setting. The quantum setting offers a polynomial speedup with bit queries and an exponential speedup with power queries. Bit queries are similar to the oracle calls used in Grovers algorithm appropriately extended to real valued functions. Power queries are used for a number of problems including phase estimation. They are obtained by considering the propagator of the discretized system at a number of different time moments. They allow us to use powers of the unitary matrix exp((1/2) iM), where M is an n× n matrix obtained from the standard discretization of the Sturm–Liouville differential operator. The quantum implementation of power queries by a number of elementary quantum gates that is polylog in n is an open issue. In particular, we show how to compute an -approximation with probability (3/4) using n()=(–1/3) bit queries. For power queries, we use the phase estimation algorithm as a basic tool and present the algorithm that solves the problem using n()=(log –1) power queries, log 2–1 quantum operations, and (3/2) log –1 quantum bits. We also prove that the minimal number of qubits needed for this problem (regardless of the kind of queries used) is at least roughly (1/2) log –1. The lower bound on the number of quantum queries is proven in Bessen (in preparation). We derive a formula that relates the Sturm–Liouville eigenvalue problem to a weighted integration problem. Many computational problems may be recast as this weighted integration problem, which allows us to solve them with a polylog number of power queries. Examples include Grovers search, the approximation of the Boolean mean, NP-complete problems, and many multivariate integration problems. In this paper we only provide the relationship formula. The implications are covered in a forthcoming paper (in preparation).PACS: 03.67.Lx, 02.60.-x. 相似文献
9.
We study the complexity of equivalence and isomorphism on primitive positive formulas with respect to a given structure. We
study these problems for various fixed structures; we present generic hardness and complexity class containment results, and
give classification theorems for the case of two-element (boolean) structures. 相似文献
10.
We study the problem of querying data sources that accept only a limited set of queries, such as sources accessible by Web
services which can implement very large (potentially infinite) families of queries. We revisit a classical setting in which
the application queries are conjunctive queries and the source accepts families of conjunctive queries specified as the expansions
of a (potentially recursive) Datalog program with parameters. 相似文献
11.
The Determining Method about the Conflict between the Null Constraints and the Set of Functional Dependencies
下载免费PDF全文
![点击此处可从《计算机科学技术学报》网站下载免费的PDF全文](/ch/ext_images/free.gif)
刘惟一 《计算机科学技术学报》1989,4(2):116-125
In this paper the conflict between the null constraints and the set of functional dependencies is defined.Some rules for determining the conflicts and a method for processing the conflicts are obtained. 相似文献
12.
We present a lattice algorithm specifically designed for some classical applications of lattice reduction. The applications
are for lattice bases with a generalized knapsack-type structure, where the target vectors have bounded depth. For such applications,
the complexity of the algorithm improves traditional lattice reduction by replacing some dependence on the bit-length of the
input vectors by some dependence on the bound for the output vectors. If the bit-length of the target vectors is unrelated
to the bit-length of the input, then our algorithm is only linear in the bit-length of the input entries, which is an improvement
over the quadratic complexity floating-point LLL algorithms. To illustrate the usefulness of this algorithm we show that a
direct application to factoring univariate polynomials over the integers leads to the first complexity bound improvement since
1984. A second application is algebraic number reconstruction, where a new complexity bound is obtained as well. 相似文献
13.
LIUChun-tao LINZhi-hang ZHOUChunojing 《计算机辅助绘图.设计与制造(英文版)》2005,15(1):64-71
The problem of robust design is treated as a multi-objective optimization issue in which the performance mean and variation are optimized and minimized respectively, while maintaining the feasibility of design constraints under uncertainty. To effectively address this issue in robust design, this paper presents a novel robust optimization approach which integrates multi-objective optimization concepts with Taguchi’s crossed arrays techniques. In this approach, Pareto-optimal robust design solution sets are obtained with the aid of design of experiment set-ups, which utilize the results of Analysis of Variance to quantify relative dominance and significance of design variables. A beam design problem is used to illustrate the effectiveness of the proposed approach. 相似文献
14.
Giovanni Bellettini Valentina Beorchia Maurizio Paolini 《Journal of Mathematical Imaging and Vision》2008,32(3):265-291
We introduce and study a two-dimensional variational model for the reconstruction of a smooth generic solid shape E, which may handle the self-occlusions and that can be considered as an improvement of the 2.1D sketch of Nitzberg and Mumford
(Proceedings of the Third International Conference on Computer Vision, Osaka, 1990). We characterize from the topological viewpoint the apparent contour of E, namely, we characterize those planar graphs that are apparent contours of some shape E. This is the classical problem of recovering a three-dimensional layered shape from its apparent contour, which is of interest
in theoretical computer vision. We make use of the so-called Huffman labeling (Machine Intelligence, vol. 6, Am. Elsevier,
New York, 1971), see also the papers of Williams (Ph.D. Dissertation, 1994 and Int. J. Comput. Vis. 23:93–108, 1997) and the paper of Karpenko and Hughes (Preprint, 2006) for related results. Moreover, we show that if E and F are two shapes having the same apparent contour, then E and F differ by a global homeomorphism which is strictly increasing on each fiber along the direction of the eye of the observer.
These two topological theorems allow to find the domain of the functional ℱ describing the model. Compactness, semicontinuity
and relaxation properties of ℱ are then studied, as well as connections of our model with the problem of completion of hidden
contours.
相似文献
Maurizio PaoliniEmail: |
15.
Peder Lindberg James Leingang Daniel Lysaker Samee Ullah Khan Juan Li 《The Journal of supercomputing》2012,59(1):323-360
In this paper, we study the problem of scheduling tasks on a distributed system, with the aim to simultaneously minimize energy
consumption and makespan subject to the deadline constraints and the tasks’ memory requirements. A total of eight heuristics
are introduced to solve the task scheduling problem. The set of heuristics include six greedy algorithms and two naturally
inspired genetic algorithms. The heuristics are extensively simulated and compared using an simulation test-bed that utilizes
a wide range of task heterogeneity and a variety of problem sizes. When evaluating the heuristics, we analyze the energy consumption,
makespan, and execution time of each heuristic. The main benefit of this study is to allow readers to select an appropriate
heuristic for a given scenario. 相似文献
16.
Given a data set in a metric space, we study the problem of hierarchical clustering to minimize the maximum cluster diameter,
and the hierarchical k-supplier problem with customers arriving online.
We prove that two previously known algorithms for hierarchical clustering, one (offline) due to Dasgupta and Long and the
other (online) due to Charikar, Chekuri, Feder and Motwani, output essentially the same result when points are considered
in the same order. We show that the analyses of both algorithms are tight and exhibit a new lower bound for hierarchical clustering.
Finally we present the first constant factor approximation algorithm for the online hierarchical k-supplier problem. 相似文献
17.
In this paper, a new lattice Boltzmann model based on the rebuilding-divergency method for the Poisson equation is proposed.
In order to translate the Poisson equation into a conservation law equation, the source term and diffusion term are changed
into divergence forms. By using the Chapman-Enskog expansion and the multi-scale time expansion, a series of partial differential
equations in different time scales and several higher-order moments of equilibrium distribution functions are obtained. Thus,
by rebuilding the divergence of the source and diffusion terms, the Laplace equation and the Poisson equation with the second
accuracy of the truncation errors are recovered. In the numerical examples, we compare the numerical results of this scheme
with those obtained by other classical method for the Green-Taylor vortex flow, numerical results agree well with the classical
ones. 相似文献
18.
The motion behaviors of vertebrates require the correct coordination of the muscles and of the body limbs even for the most
stereotyped ones like the rhythmical patterns. It means that the neural circuits have to share some part of the control with
the material properties and the body morphology in order to rise any of these motor synergies. To this respect, the chemical
downward neuromodulators that supervise the pattern generators in the spinal cord create the conditions to merge (or to disrupt)
them by matching the phase of the neural controllers to the body dynamics. In this paper, we replicate this control based
on phase synchronization to implement neuromodulators and investigate the interplay between control, morphology and material.
We employ this mechanism to control three robotic setups of gradual complexity and actuated by McKibben type air muscles:
a single air muscle, an elbow-like system and a leg-like articulation. We show that for specific values, the control parameters
modulate the internal dynamics to match those of the body and of the material physics to either the rhythmical and non-rhythmical
gait patterns. 相似文献
19.
Peter Hachenberger 《Algorithmica》2009,55(2):329-345
We present the first exact and robust implementation of the 3D Minkowski sum of two non-convex polyhedra. Our implementation
decomposes the two polyhedra into convex pieces, performs pairwise Minkowski sums on the convex pieces, and constructs their
union. We achieve exactness and the handling of all degeneracies by building upon 3D Nef polyhedra as provided by Cgal. The implementation also supports open and closed polyhedra. This allows the handling of degenerate scenarios like the tight
passage problem in robot motion planning.
The bottleneck of our approach is the union step. We address efficiency by optimizing this step by two means: we implement
an efficient decomposition that yields a small number of convex pieces, and develop, test and optimize multiple strategies
for uniting the partial sums by consecutive binary union operations.
The decomposition that we implemented as part of the Minkowski sum is interesting in its own right. It is the first robust
implementation of a decomposition of polyhedra into convex pieces that yields at most O(r
2) pieces, where r is the number of edges whose adjacent facets comprise an angle of more than 180 degrees with respect to the interior of the
polyhedron.
This work was partially supported by the Netherlands’ Organisation for Scientific Research (NWO) under project no. 639.023.301. 相似文献
20.
In this paper we solve a conjecture on the zeros of R-Bonacci polynomials in the case when r=3 (Tribonacci polynomials) and determine the zero attractor of the Tribonacci polynomials. Universality of the zero attractor
is also established.
相似文献