共查询到20条相似文献,搜索用时 31 毫秒
1.
The Orbit problem is defined as follows: Given a matrix A∈ℚ
n×n
and vectors x,y∈ℚ
n
, does there exist a non-negative integer i such that A
i
x=y. This problem was shown to be in deterministic polynomial time by Kannan and Lipton (J. ACM 33(4):808–821, 1986). In this paper we place the problem in the logspace counting hierarchy GapLH. We also show that the problem is hard for
C=L with respect to logspace many-one reductions. 相似文献
2.
Ashkan Aazami 《Journal of Combinatorial Optimization》2010,19(4):429-456
We introduce a hierarchy of problems between the Dominating Set problem and the Power Dominating Set (PDS) problem called the ℓ-round power dominating set (ℓ-round PDS, for short) problem. For ℓ=1, this is the Dominating Set problem, and for ℓ≥n−1, this is the PDS problem; here n denotes the number of nodes in the input graph. In PDS the goal is to find a minimum size set of nodes S that power dominates all the nodes, where a node v is power dominated if (1) v is in S or it has a neighbor in S, or (2) v has a neighbor u such that u and all of its neighbors except v are power dominated. Note that rule (1) is the same as for the Dominating Set problem, and that rule (2) is a type of propagation rule that applies iteratively. The ℓ-round PDS problem has the same set of rules as PDS, except we apply rule (2) in “parallel” in at most ℓ−1 rounds. We prove that ℓ-round PDS cannot be approximated better than
2log1-en2^{\log^{1-\epsilon}{n}}
even for ℓ=4 in general graphs. We provide a dynamic programming algorithm to solve ℓ-round PDS optimally in polynomial time on graphs of bounded tree-width. We present a PTAS (polynomial time approximation
scheme) for ℓ-round PDS on planar graphs for
l = O(\fraclognloglogn)\ell=O(\frac{\log{n}}{\log{\log{n}}})
. Finally, we give integer programming formulations for ℓ-round PDS. 相似文献
3.
Given a graph G=(V,E) with node weight w:V→R
+ and a subset S⊆V, find a minimum total weight tree interconnecting all nodes in S. This is the node-weighted Steiner tree problem which will be studied in this paper. In general, this problem is NP-hard
and cannot be approximated by a polynomial time algorithm with performance ratio aln n for any 0<a<1 unless NP⊆DTIME(n
O(log n)), where n is the number of nodes in s. In this paper, we are the first to show that even though for unit disk graphs, the problem is still NP-hard and it has a
polynomial time constant approximation. We present a 2.5ρ-approximation where ρ is the best known performance ratio for polynomial time approximation of classical Steiner minimum tree problem in graphs.
As a corollary, we obtain that there is a polynomial time (9.875+ε)-approximation algorithm for minimum weight connected dominating set in unit disk graphs, and also there is a polynomial
time (4.875+ε)-approximation algorithm for minimum weight connected vertex cover in unit disk graphs. 相似文献
4.
In this paper, we study the parameterized complexity of Dominating Set problem in chordal graphs and near chordal graphs. We show the problem is W[2]-hard and cannot be solved in time n
o(k) in chordal and s-chordal (s>3) graphs unless W[1]=FPT. In addition, we obtain inapproximability results for computing a minimum dominating set in chordal
and near chordal graphs. Our results prove that unless NP=P, the minimum dominating set in a chordal or s-chordal (s>3) graph cannot be approximated within a ratio of
\fracc3lnn\frac{c}{3}\ln{n} in polynomial time, where n is the number of vertices in the graph and 0<c<1 is the constant from the inapproximability of the minimum dominating set in general graphs. In other words, our results
suggest that restricting to chordal or s-chordal graphs can improve the approximation ratio by no more than a factor of 3. We then extend our techniques to find similar
results for the Independent Dominating Set problem and the Connected Dominating Set problem in chordal or near chordal graphs. 相似文献
5.
A linear extension problem is defined as follows: Given a poset P=(E,≤), we want to find a linear order L such that x≤y in L whenever x≤yin P. In this paper, we assign each pair of elements x,y∈E with a cost, and to find a linear extension of P with the minimum sum cost. For the general case, it is NP-complete and we present a greedy approximation algorithm which
can be finished in polynomial time. Also we consider a special case which can be solved in polynomial time. 相似文献
6.
We study the problem of separating sublinear time computations via approximating the diameter for a sequence S=p
1
p
2
⋅⋅⋅
p
n
of points in a metric space, in which any two consecutive points have the same distance. The computation is considered respectively
under deterministic, zero error randomized, and bounded error randomized models. We obtain a class of separations using various
versions of the approximate diameter problem based on restrictions on input data. We derive tight sublinear time separations
for each of the three computation models via proving that computation with O(n
r
) time is strictly more powerful than that with O(n
r−ε
) time, where r and ε are arbitrary parameters in (0,1) and (0,r) respectively. We show that, for any parameter r∈(0,1), the bounded error randomized sublinear time computation in time O(n
r
) cannot be simulated by any zero error randomized sublinear time algorithm in o(n) time or queries; and the same is true for zero error randomized computation versus deterministic computation. 相似文献
7.
Let G=(V,E) be an undirected graph in which every vertex v∈V is assigned a nonnegative integer w(v). A w-packing is a collection of cycles (repetition allowed) in G such that every v∈V is contained at most w(v) times by the members of . Let 〈w〉=2|V|+∑
v∈V
⌈log (w(v)+1)⌉ denote the binary encoding length (input size) of the vector (w(v): v∈V)
T
. We present an efficient algorithm which finds in O(|V|8〈w〉2+|V|14) time a w-packing of maximum cardinality in G provided packing and covering cycles in G satisfy the ℤ+-max-flow min-cut property. 相似文献
8.
String barcoding is a method that can identify microorganisms by analyzing their genome sequences. In this paper, we study
the polylogarithmic string barcoding problem, where the lengths of the substrings in the testing set are polylogarithmically
bounded. In particular, we show that the polylogarithmic string barcoding problem remains NP-hard and moreover, for a problem
instance with n sequences, it is NP-hard to achieve an approximate ratio within dln n in polynomial time, where d is some constant. We then consider the parameterized polylogarithmic string barcoding problem, where the number of substrings
in the test set is considered to be a fixed parameter k. We show that, unless W[2]=FPT, there does not exist a 2
O(k)
n
c
algorithm that can decide whether a test set of size k exists or not, where c is a constant independent of n and k. 相似文献
9.
Mohamed Saad Tamás Terlaky Anthony Vannelli Hu Zhang 《Journal of Combinatorial Optimization》2008,16(4):402-423
Given an undirected edge-capacitated graph and given (possibly) different subsets of vertices, we consider the problem of
selecting a maximum (weighted) set of Steiner trees, each tree spanning a subset of vertices, without violating the capacity
constraints. This problem is motivated by applications in multicast communication networks. We give an integer linear programming
(ILP) formulation for the problem, and observe that its linear programming (LP) relaxation is a fractional packing problem
with exponentially many variables and a block (sub-)problem that cannot be solved in polynomial time. To this end, we take
an r-approximate block solver (a weak block solver) to develop a (1−ε)/r-approximation algorithm for the LP relaxation. The algorithm has a polynomial coordination complexity for any ε∈(0,1). To the best of our knowledge, this is the first approximation result for fractional packing problems with only weak
block solvers (with arbitrarily large approximation ratio) and a coordination complexity that is polynomial in the input size.
This leads also to an approximation algorithm for the underlying tree packing problem. Finally, we extend our results to an
important multicast routing and wavelength assignment problem in optical networks, where each Steiner tree is to be assigned
one of a limited set of given wavelengths, so that trees crossing the same fiber are assigned different wavelengths.
A preliminary version of this paper appeared in the Proceedings of the 1st Workshop on Internet and Network Economics (WINE
2005), LNCS, vol. 3828, pp. 688–697. Research supported by a MITACS grant for all the authors, an NSERC post doctoral fellowship
for the first author, the NSERC Discovery Grant #5-48923 for the second and fourth author, NSERC Discovery Grant #15296 for
the third author, the Canada Research Chair Program for the second author, and an NSERC industrial and development fellowship
for the fourth author. 相似文献
10.
Haoli Wang Xirong Xu Yuansheng Yang Kai Lü 《Journal of Combinatorial Optimization》2011,21(4):481-496
Let G=(V,E) be a graph without an isolated vertex. A set D⊆V(G) is a k
-distance paired dominating set of G if D is a k-distance dominating set of G and the induced subgraph 〈D〉 has a perfect matching. The minimum cardinality of a k-distance paired dominating set for graph G is the k
-distance paired domination number, denoted by γ
p
k
(G). In this paper, we determine the exact k-distance paired domination number of generalized Petersen graphs P(n,1) and P(n,2) for all k≥1. 相似文献
11.
Rocchio’s similarity-based relevance feedback algorithm, one of the most important query reformation methods in information
retrieval, is essentially an adaptive supervised learning algorithm from examples. In practice, Rocchio’s algorithm often
uses a fixed query updating factor. When this is the case, we strengthen the linear Ω(n) lower bound obtained by Chen and Zhu (Inf. Retr. 5:61–86, 2002) and prove that Rocchio’s algorithm makes Ω(k(n−k)) mistakes in searching for a collection of documents represented by a monotone disjunction of k relevant features over the n-dimensional binary vector space {0,1}
n
, when the inner product similarity measure is used. A quadratic lower bound is obtained when k is linearly proportional to n. We also prove an O(k(n−k)3) upper bound for Rocchio’s algorithm with the inner product similarity measure in searching for such a collection of documents
with a constant query updating factor and a zero classification threshold. 相似文献
12.
The following planar minimum disk cover problem is considered in this paper: given a set
D\mathcal{D}
of n disks and a set ℘ of m points in the Euclidean plane, where each disk covers a subset of points in ℘, to compute a subset of disks with minimum
cardinality covering ℘. This problem is known to be NP-hard and an algorithm which approximates the optimal disk cover within
a factor of (1+ε) in
O(mnO(\frac1e2log2\frac1e))\mathcal{O}(mn^{\mathcal{O}(\frac{1}{\epsilon^{2}}\log^{2}\frac{1}{\epsilon})})
time is proposed in this paper. This work presents the first polynomial time approximation scheme for the minimum disk cover
problem where the best known algorithm can approximate the optimal solution with a large constant factor. Further, several
variants of the minimum disk cover problem such as the incongruent disk cover problem and the weighted disk cover problem
are considered and approximation schemes are designed. 相似文献
13.
We show several hardness results for the Minimum Hacking problem, which roughly can be described as the problem of finding the best way to compromise a target node given a few initial compromised nodes in a network. We give several reductions to show that Minimum Hacking is not approximable to within
where δ = 1−
c n, for any c < 1/2. We also analyze some heuristics on this problem. 相似文献
14.
The problems dealt with in this paper are generalizations of the set cover problem, min{cx | Ax b, x {0,1}n}, where c Q+n, A {0,1}m × n, b 1. The covering 0-1 integer program is the one, in this formulation, with arbitrary nonnegative entries of A and b, while the partial set cover problem requires only m–K constrains (or more) in Ax b to be satisfied when integer K is additionall specified. While many approximation algorithms have been recently developed for these problems and their special cases, using computationally rather expensive (albeit polynomial) LP-rounding (or SDP-rounding), we present a more efficient purely combinatorial algorithm and investigate its approximation capability for them. It will be shown that, when compared with the best performance known today and obtained by rounding methods, although its performance comes short in some special cases, it is at least equally good in general, extends for partial vertex cover, and improves for weighted multicover, partial set cover, and further generalizations. 相似文献
15.
The problem of optimal surface flattening in 3-D finds many applications in engineering and manufacturing. However, previous
algorithms for this problem are all heuristics without any quality guarantee and the computational complexity of the problem
was not well understood. In this paper, we prove that the optimal surface flattening problem is NP-hard. Further, we show
that the problem of flattening a topologically spherical surface admits a PTAS and can be solved by a (1+ε)-approximation algorithm in O(nlog n) time for any constant ε>0, where n is the input size of the problem. 相似文献
16.
In this paper, we consider the problem of enumerating all maximal motifs in an input string for the class of repeated motifs
with wild cards. A maximal motif is such a representative motif that is not properly contained in any larger motifs with the
same location lists. Although the enumeration problem for maximal motifs with wild cards has been studied in Parida et al.
(2001), Pisanti et al. (2003) and Pelfrêne et al. (2003), its output-polynomial time computability has been still open. The
main result of this paper is a polynomial space polynomial delay algorithm for the maximal motif enumeration problem for the
repeated motifs with wild cards. This algorithm enumerates all maximal motifs in an input string of length n in O(n
3) time per motif with O(n) space, in particular O(n
3) delay. The key of the algorithm is depth-first search on a tree-shaped search route over all maximal motifs based on a technique
called prefix-preserving closure extension. We also show an exponential lower bound and a succinctness result on the number
of maximal motifs, which indicate the limit of a straightforward approach. The results of the computational experiments show
that our algorithm can be applicable to huge string data such as genome data in practice, and does not take large additional
computational cost compared to usual frequent motif mining algorithms.
This work is done during the Hiroki Arimura’s visit in LIRIS, University Claude-Bernard Lyon 1, France. 相似文献
17.
Hanno Lefmann 《Journal of Combinatorial Optimization》2008,16(2):182-195
In this paper generalizations of Heilbronn’s triangle problem to convex hulls of j points in the unit square [0,1]2 are considered. By using results on the independence number of linear hypergraphs, for fixed integers k≥3 and any integers n≥k a deterministic o(n
6k−4) time algorithm is given, which finds distributions of n points in [0,1]2 such that, simultaneously for j=3,…,k, the areas of the convex hulls determined by any j of these n points are Ω((log n)1/(j−2)/n
(j−1)/(j−2)). 相似文献
18.
The objective of the Interconnecting Highways problem is to construct roads of minimum total length to interconnect n given highways under the constraint that the roads can intersect each highway only at one point in a designated interval which is a line segment. We present a polynomial time approximation scheme for this problem by applying Arora's framework (Arora, 1998; also available from http:www.cs.princeton.edu/~arora). For every fixed c > 1 and given any n line segments in the plane, a randomized version of the scheme finds a
-approximation to the optimal cost in O(n
O(c)log(n) time. 相似文献
19.
N. Bourgeois A. Giannakos G. Lucarelli I. Milis V. T. Paschos O. Pottié 《Journal of Combinatorial Optimization》2012,23(1):94-117
In this paper, we deal with the problem of finding quasi-independent sets in graphs. This problem is formally defined in three
versions, which are shown to be polynomially equivalent. The one that looks most general, namely, f-max quasi-independent set, consists of, given a graph and a non-decreasing function f, finding a maximum size subset Q of the vertices of the graph, such that the number of edges in the induced subgraph is less than or equal to f(|Q|). For this problem, we show an exact solution method that runs within time
O*(2\fracd-27/23d+1n)O^{*}(2^{\frac{d-27/23}{d+1}n}) on graphs of average degree bounded by d. For the most specifically defined γ-max quasi-independent set and k-max quasi-independent set problems, several results on complexity and approximation are shown, and greedy algorithms are proposed, analyzed and tested. 相似文献
20.
In this paper, we study the circular packing problem. Its objective is to pack a set of n circular pieces into a rectangular plate R of fixed dimensions L×W. Each piece’s type i, i=1,…,m, is characterized by its radius r
i
and its demand b
i
. The objective is to determine the packing pattern corresponding to the minimum unused area of R for the circular pieces placed. This problem is solved by using a hybrid algorithm that adopts beam search and a looking-ahead
strategy. A node at a level ℓ of the beam-search tree contains a partial solution corresponding to the circles already placed inside R. Each node is then evaluated using a looking-ahead strategy, based on the minimum local-distance heuristic, by computing
the corresponding complete solution. The nodes leading to the best solutions at level ℓ are then chosen for branching. A multi-start strategy is also considered in order to diversify the search space. The computational
results show, on a set of benchmark instances, the effectiveness of the proposed algorithm. 相似文献