共查询到20条相似文献,搜索用时 218 毫秒
1.
Given a closed, convex set X\subseteq \bbR
n
, containing the origin, we consider the problem (P) : max {c^\T x\colon x ∈ X} . We show that, for a fixed dimension, n , and fixed \eps , 0 <\eps<1 , the existence of a combinatorial, strongly polynomial \eps -approximation separation algorithm for the set X is equivalent to the existence of a combinatorial, strongly polynomial \eps -approximation optimization algorithm for the problem (P) .
Received June 5, 1996; revised September 25, 1997. 相似文献
2.
Given a Laman graph G, i.e. a minimally rigid graph in R
2, we provide a Θ(n
2) algorithm to augment G to a redundantly rigid graph, by adding a minimum number of edges. Moreover, we prove that this problem of augmenting is
NP-hard for an arbitrary rigid graph G in R
2. 相似文献
3.
We study local, distributed algorithms for the capacitated minimum dominating set (CapMDS) problem, which arises in various
distributed network applications. Given a network graph G=(V,E), and a capacity cap(v)∈ℕ for each node v∈V, the CapMDS problem asks for a subset S⊆V of minimal cardinality, such that every network node not in S is covered by at least one neighbor in S, and every node v∈S covers at most cap(v) of its neighbors. We prove that in general graphs and even with uniform capacities, the problem is inherently non-local, i.e., every distributed algorithm achieving a non-trivial approximation ratio must have a time complexity that essentially
grows linearly with the network diameter. On the other hand, if for some parameter ε>0, capacities can be violated by a factor of 1+ε, CapMDS becomes much more local. Particularly, based on a novel distributed randomized rounding technique, we present a distributed
bi-criteria algorithm that achieves an O(log Δ)-approximation in time O(log 3
n+log (n)/ε), where n and Δ denote the number of nodes and the maximal degree in G, respectively. Finally, we prove that in geometric network graphs typically arising in wireless settings, the uniform problem
can be approximated within a constant factor in logarithmic time, whereas the non-uniform problem remains entirely non-local. 相似文献
4.
Approximation Algorithms for Connected Dominating Sets 总被引:38,自引:0,他引:38
The dominating set problem in graphs asks for a minimum size subset of vertices with the following property: each vertex
is required to be either in the dominating set, or adjacent to some vertex in the dominating set. We focus on the related
question of finding a connected dominating set of minimum size, where the graph induced by vertices in the dominating set is required to be connected as well. This problem arises in network testing, as well as in wireless communication.
Two polynomial time algorithms that achieve approximation factors of 2H(Δ)+2 and H(Δ)+2 are presented, where Δ is the maximum degree and H is the harmonic function. This question also arises in relation to the traveling tourist problem, where one is looking for
the shortest tour such that each vertex is either visited or has at least one of its neighbors visited. We also consider a
generalization of the problem to the weighted case, and give an algorithm with an approximation factor of (c
n
+1) \ln n where c
n
ln k is the approximation factor for the node weighted Steiner tree problem (currently c
n
= 1.6103 ). We also consider the more general problem of finding a connected dominating set of a specified subset of vertices and provide a polynomial time algorithm with a (c+1) H(Δ) +c-1 approximation factor, where c is the Steiner approximation ratio for graphs (currently c = 1.644 ).
Received June 22, 1996; revised February 28, 1997. 相似文献
5.
Consider an n-vertex planar graph G. The depth of an embedding Γ of G is the maximum distance of its internal faces from the external one. Several researchers pointed out that the quality of
a planar embedding can be measured in terms of its depth. We present an O(n
4)-time algorithm for computing an embedding of G with minimum depth. This bound improves on the best previous bound by an O(nlog n) factor. As a side effect, our algorithm improves the bounds of several algorithms that require the computation of a minimum-depth
embedding. 相似文献
6.
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.483k
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). 相似文献
7.
Frédéric Havet Martin Klazar Jan Kratochvíl Dieter Kratsch Mathieu Liedloff 《Algorithmica》2011,59(2):169-194
The notion of distance constrained graph labelings, motivated by the Frequency Assignment Problem, reads as follows: A mapping
from the vertex set of a graph G=(V,E) into an interval of integers {0,…,k} is an L(2,1)-labeling of G of span k if any two adjacent vertices are mapped onto integers that are at least 2 apart, and every two vertices with a common neighbor
are mapped onto distinct integers. It is known that for any fixed k≥4, deciding the existence of such a labeling is an NP-complete problem. We present exact exponential time algorithms that
are faster than the naive O
*((k+1)
n
) algorithm that would try all possible mappings. The improvement is best seen in the first NP-complete case of k=4, where the running time of our algorithm is O(1.3006
n
). Furthermore we show that dynamic programming can be used to establish an O(3.8730
n
) algorithm to compute an optimal L(2,1)-labeling. 相似文献
8.
We study two related network design problems with two cost functions. In the buy-at-bulk k-Steiner tree problem we are given a graph G(V,E) with a set of terminals T⊆V including a particular vertex s called the root, and an integer k≤|T|. There are two cost functions on the edges of G, a buy cost b:E→ℝ+ and a distance cost r:E→ℝ+. The goal is to find a subtree H of G rooted at s with at least k terminals so that the cost ∑
e∈H
b(e)+∑
t∈T−s
dist(t,s) is minimized, where dist(t,s) is the distance from t to s in H with respect to the r cost. We present an O(log 4
n)-approximation algorithm for the buy-at-bulk k-Steiner tree problem. The second and closely related one is bicriteria approximation algorithm for Shallow-light k-Steiner trees. In the shallow-light k-Steiner tree problem we are given a graph G with edge costs b(e) and distance costs r(e), and an integer k. Our goal is to find a minimum cost (under b-cost) k-Steiner tree such that the diameter under r-cost is at most some given bound D. We develop an (O(log n),O(log 3
n))-approximation algorithm for a relaxed version of Shallow-light k-Steiner tree where the solution has at least
terminals. Using this we obtain an (O(log 2
n),O(log 4
n))-approximation algorithm for the shallow-light k-Steiner tree and an O(log 4
n)-approximation algorithm for the buy-at-bulk k-Steiner tree problem. Our results are recently used to give the first polylogarithmic approximation algorithm for the non-uniform
multicommodity buy-at-bulk problem (Chekuri, C., et al. in Proceedings of 47th Annual IEEE Symposium on Foundations of Computer
Science (FOCS’06), pp. 677–686, 2006).
A preliminary version of this paper appeared in the Proceedings of 9th International Workshop on Approximation Algorithms
for Combinatorial Optimization Problems (APPROX) 2006, LNCS 4110, pp. 153–163, 2006.
M.T. Hajiaghayi supported in part by IPM under grant number CS1383-2-02.
M.R. Salavatipour supported by NSERC grant No. G121210990, and a faculty start-up grant from University of Alberta. 相似文献
9.
The polynomial-time solvable k-hurdle problem is a natural generalization of the classical s-t minimum cut problem where we must select a minimum-cost subset S of the edges of a graph such that |p∩S|≥k for every s-t path p. In this paper, we describe a set of approximation algorithms for “k-hurdle” variants of the NP-hard multiway cut and multicut problems. For the k-hurdle multiway cut problem with r terminals, we give two results, the first being a pseudo-approximation algorithm that outputs a (k−1)-hurdle solution whose cost is at most that of an optimal solution for k hurdles. Secondly, we provide a
2(1-\frac1r)2(1-\frac{1}{r})-approximation algorithm based on rounding the solution of a linear program, for which we give a simple randomized half-integrality
proof that works for both edge and vertex k-hurdle multiway cuts that generalizes the half-integrality results of Garg et al. for the vertex multiway cut problem. We
also describe an approximation-preserving reduction from vertex cover as evidence that it may be difficult to achieve a better
approximation ratio than
2(1-\frac1r)2(1-\frac{1}{r}). For the k-hurdle multicut problem in an n-vertex graph, we provide an algorithm that, for any constant ε>0, outputs a ⌈(1−ε)k⌉-hurdle solution of cost at most O(log n) times that of an optimal k-hurdle solution, and we obtain a 2-approximation algorithm for trees. 相似文献
10.
Stefan Porschen Bert Randerath Ewald Speckenmeyer 《Annals of Mathematics and Artificial Intelligence》2005,43(1-4):173-193
Let F=C
1C
m
be a Boolean formula in conjunctive normal form over a set V of n propositional variables, s.t. each clause C
i
contains at most three literals l over V. Solving the problem exact 3-satisfiability (X3SAT) for F means to decide whether there is a truth assignment setting exactly one literal in each clause of F to true (1). As is well known X3SAT is NP-complete [6]. By exploiting a perfect matching reduction we prove that X3SAT is deterministically decidable in time O(20.18674n
). Thereby we improve a result in [2,3] stating X3SATO(20.2072n
) and a bound of O(20.200002n
) for the corresponding enumeration problem #X3SAT stated in a preprint [1]. After that by a more involved deterministic case analysis we are able to show that X3SATO(20.16254n
). 相似文献
11.
The minimum k-terminal cut problem is of considerable theoretical interest and arises in several
applied areas such as parallel and distributed computing, VLSI circuit design, and networking. In this paper
we present two new approximation and exact algorithms for this problem on an n-vertex undirected weighted
planar graph G. For the case when the k terminals are covered by the boundaries of m > 1 faces of G, we
give a min{O(n
2 log n logm), O(m
2
n
1.5 log2
n + k
n)} time algorithm with a (2–2/k)-approximation ratio
(clearly, m \le k). For the case when all k terminals are covered by the boundary of one face of G, we give an
O(n
k3 + (n log n)k
2) time exact algorithm, or a linear time exact algorithm if k = 3, for computing an optimal
k-terminal cut. Our algorithms are based on interesting observations and improve the previous algorithms when
they are applied to planar graphs. To our best knowledge, no previous approximation algorithms specifically
for solving the k-terminal cut problem on planar graphs were known before. The (2–2/k)-approximation
algorithm of Dahlhaus et al. (for general graphs) takes O(k
n
2 log n) time when applied to planar graphs. Our
approximation algorithm for planar graphs runs faster than that of Dahlhaus et al. by at least an O(k/logm)
factor (m \le k). 相似文献
12.
Let S be a set of n taxa. Given a parameter k and a set of quartet topologies Q over S such that there is exactly one topology for every subset of four taxa, the parameterized Minimum Quartet Inconsistency (MQI)
problem is to decide whether we can find an evolutionary tree inducing a set of quartet topologies that differs from the given
set in at most k quartet topologies. The best fixed-parameter algorithm devised so far for the parameterized MQI problem runs in time O(4
k
n+n
4). In this paper, first we present an O(3.0446
k
n+n
4) fixed-parameter algorithm and an O(2.0162
k
n
3+n
5) fixed-parameter algorithm for the parameterized MQI problem. Finally, we give an O
*((1+ε)
k
) fixed-parameter algorithm, where ε>0 is an arbitrarily small constant. 相似文献
13.
Vincenzo D. Cunsolo Salvatore Distefano Antonio Puliafito Marco L. Scarpa 《Journal of Grid Computing》2010,8(3):391-418
Technological trend and the advent of worldwide networks, such as the Internet, made computing systems more and more powerful,
increasing both processing and storage capabilities. In Grid computing infrastructures, the data storage subsystem is physically
distributed among several nodes and logically shared among several users. This highlights the necessity of a) availability
for authorized users only, b) confidentiality, and c) integrity of information and data: in one term security. In this work we face the problem of data security in Grid, by proposing a lightweight cryptography algorithm combining the
strong and highly secure asymmetric cryptography technique (RSA) with the symmetric cryptography (AES). The proposed algorithm,
we named Grid secure storage system (GS3), has been implemented on top of the Grid file access library (GFAL) of the gLite middleware, in order to provide a file
system service with cryptography capability and POSIX interface. The choice of implementing GS3 as a file system, the GS3FS, allows to protect the file system structure also, and to overcome the well-known problem of
file rewriting in gLite/GFAL environments. In the specification of the GS3FS, particular care is addressed on providing a usable user interface
and on implementing a file system that has low impact on the middleware. The final result is the introduction of a new storage
Grid service into the gLite middleware, whose overall characteristics are never offered before, at the best of authors’ knowledge.
The paper describes and details both the GS3 algorithm and its implementation; the performance of such implementation are evaluated discussing the obtained results and
possible application scenarios in order to demonstrate its effectiveness and usefulness. 相似文献
14.
Frank Dehne Michael Fellows Michael Langston Frances Rosamond Kim Stevens 《Theory of Computing Systems》2007,41(3):479-492
We describe an algorithm for the Feedback Vertex Set problem on undirected graphs, parameterized
by the size k of the feedback vertex set, that runs in time O(ckn3) where c = 10.567 and n is the number of vertices in the graph. The best previous algorithms were based on the method of
bounded search trees, branching on short cycles. The best previous running time of an FPT algorithm for this problem, due
to Raman, Saurabh and Subramanian, has a parameter function of the form 2O(k log k /log log k). Whether an exponentially linear in k FPT algorithm for this problem is possible has been previously noted as a significant
challenge. Our algorithm is based on the new FPT technique of iterative compression. Our result holds for a more general form
of the problem, where a subset of the vertices may be marked as forbidden to belong to the feedback set. We also establish
"exponential optimality" for our algorithm by proving that no FPT algorithm with a parameter function of the form O(2o(k)) is possible, unless there is an unlikely collapse of parameterized complexity classes, namely FPT = M[1]. 相似文献
15.
《Computer Communications》2007,30(14-15):2880-2891
Hierarchical routing techniques have long been known to increase network scalability by constructing a virtual backbone. Even though MANETs have no physical backbone, a virtual backbone can be constructed by finding a connected dominating set (CDS) in the network graph. Many centralized as well as distributed algorithms have been designed to find a CDS in a graph (network). Theoretically, any centralized algorithm can be implemented in a distributed fashion, with the tradeoff of higher protocol overhead. Because centralized approaches do not scale well and because distributed approaches are more practical especially in MANETs, we propose a fast distributed connected dominating set (FDDS) construction in MANETs. FDDS has message and time complexity of O(n) and O(Δ2), where n is the number of nodes in the network and Δ is the maximum node degree. According to our knowledge, FDDS achieves the best message and time complexity combinations among the previously suggested approaches. Moreover, FDDS constructs a reliable virtual backbone that takes into account (1) node’s limited energy, (2) node’s mobility, and (3) node’s traffic pattern. Our simulation study shows that FDDS achieves a very low network stretch. Also, when the network size is large, FDDS constructs a backbone with size smaller than other well known schemes found in the literature. 相似文献
16.
Scheduling is one of the most successful application areas of constraint programming mainly thanks to special global constraints
designed to model resource restrictions. Among these global constraints, edge-finding and not-first/not-last are the most
popular filtering algorithms for unary resources. In this paper we introduce new O(n log n) versions of these two filtering algorithms and one more O(n log n) filtering algorithm called detectable precedences. These algorithms use a special data structures Θ-tree and Θ-Λ-tree. These
data structures are especially designed for “what-if” reasoning about a set of activities so we also propose to use them for
handling so called optional activities, i.e. activities which may or may not appear on the resource. In particular, we propose
new O(n log n) variants of filtering algorithms which are able to handle optional activities: overload checking, detectable precedences
and not-first/not-last. 相似文献
17.
提出了一种基于多生成树和子网-节点度联合权重的静态无线网络极小连通支配集MCDS构造算法SWNMCDS。算法首先设定一个概率p,每个节点随机生成一个概率并与p对比后决定是否成为候选根节点。两跳范围内的候选根节点相互交换信息,确定最终的根节点。每个根节点基于节点权重的连通树生成算法生成多棵连通树。最后基于子网-节点度联合权重选择连通节点,将多棵连通树连成极小连通支配集。经分析,SWNMCDS算法近似比上限为2β(2+H(Δ)),时间复杂度为O(Δ2),消息复杂度为O(Δ2)(Δ为最大一跳邻居节点集合的大小,β为生成树数目)。仿真实验表明,与经典MCDS算法比较,SWNMCDS所构造的连通支配集具有较小的规模。 相似文献
18.
《Information Processing Letters》1986,23(3):131-134
A total dominating set of a graph G is a subset S of nodes such that each node of G is adjacent to some node of S. We present an O(n2) time algorithm for finding a minimum cardinality total dominating set in an interval graph (one which represents intersecting intervals on the line) by reducing it to a shortest path problem on an appropriate acyclic directed network. 相似文献
19.
The paper deals with a numerical analysis of the incomplete interior penalty Galerkin (IIPG) method applied to one dimensional
Poisson problem. Based on a particular choice of the interior penalty parameter σ (order of O(h
−1)), we derive the optimal error estimate in the L
2-norm for odd degrees of polynomial approximation for locally quasi-uniform meshes. Moreover, we show that only the mentioned
choice of the penalty parameter leads to optimal orders of convergence. Finally, presented numerical experiments verify the
theoretical results. 相似文献
20.
In this paper we describe, from a theoretical point of view, critical configurations for the projective reconstruction of
a set of points, for a single view, i.e. for calibration of a camera, in the case of projections from ℙk to ℙ2 for k ≥ 4. We give first a general result describing these critical loci in ℙk, which, if irreducible, are algebraic varieties of dimension k−2 and degree 3. If k=4 they can be either a smooth ruled surface or a cone and if k = 5 they can be a smooth three dimensional variety, ruled in planes, or a cone. If k≥ 6, the variety is always a cone, the
vertex of which has dimension at least k − 6. The reducible cases are studied in Appendix A.
These results are then applied to determine explicitly the critical loci for the projections from ℙk which arise from the dynamic scenes in ℙ3 considered in [13].
Marina Bertolini is currently Associate Professor of Geometry at the Department of Mathematics at the Università degli Studi di Milano, Italy.
Her main field of research is Complex Projective Algebraic Geometry, with particular interest for the classification of projective
varieties and for the geometry of Grassmann varieties. On these topics M. Bertolini has published more than twenty reviewed
papers on national and international journals. She has been for some years now interested also in applications of Algebraic
Geometry to Computer Vision problems.
Cristina Turrini is Associate Professor of Geometry at the Department of Mathematics of Università degli Studi di Milano, Italy. Her main
research interest is Complex Projective Algebraic Geometry: subvarieties of Grassmannians, special varieties, automorphisms,
classification. In the last two years she has started to work on applications of Algebraic Geometry to problems of Computer
Vision. She is author or co-author of about thirty reviewed papers. She is also involved in popularization of Mathematics,
and on this subject she is co-editor of some books. 相似文献