共查询到20条相似文献,搜索用时 0 毫秒
1.
Zeev Nutov 《Algorithmica》2006,44(3):213-231
A graph is called {\em $\el$-connected from $U$ to $r$} if there are $\el$
internally disjoint paths from every node $u \in U$ to $r$.
The {\em Rooted Subset Connectivity Augmentation Problem} ({\em RSCAP}) is as
follows: given a graph $G=(V+r,E)$, a node subset $U \subseteq V$, and an
integer $k$, find a smallest set $F$ of new edges such that $G+F$ is
$k$-connected from $U$ to $r$.
In this paper we consider mainly a restricted version of RSCAP in which the
input graph $G$ is already $(k-1)$-connected from $U$ to $r$.
For this version we give an $O(\ln\! |U|)$-approximation algorithm, and
show that the problem cannot achieve a better approximation guarantee than
the Set Cover Problem (SCP) on $|U|$ elements and with $|V|-|U|$ sets.
For the general version of RSCAP we give an
$O(\ln k \ln\!|U|)$-approximation algorithm.
For $U=V$ we get the {\em Rooted Connectivity Augmentation Problem}
({\em RCAP}).
For directed graphs RCAP is polynomially solvable,
but for undirected graphs its complexity status is not known:
no polynomial algorithm is known, and it is also not known to be NP-hard.
For undirected graphs with the input graph $G$ being
$(k-1)$-connected from $V$ to $r$, we give an algorithm
that computes a solution of size at most ${\it opt}+\min\{opt,k\}/2$, where
{\it opt} denotes the optimal solution size. 相似文献
2.
Fernando C. Gomes Cludio N. Meneses Panos M. Pardalos Gerardo Valdisio R. Viana 《Computers & Operations Research》2006,33(12):3520
Several approximation algorithms with proven performance guarantees have been proposed to find approximate solutions to classical combinatorial optimization problems. However, theoretical results may not reflect the experimental performance of the proposed algorithms. As a consequence, a question arises: how “far” from the theoretically proved performance are the experimental results? We conduct a controlled empirical study of approximation algorithms for the Vertex Cover and the Set Covering Problems. Many authors have proposed approximation algorithms for those problems. Our main goal is to better understand their strengths, weaknesses, and operation. Although we implement more than one algorithm to find feasible solutions to either problems, this work does not emphasize competition between them. The quality of the solutions related to the theoretical performance guarantees are analyzed instead. The computational experiments showed that the proven performance guarantees of all tested algorithms did not forecast well the empirical performance. 相似文献
3.
L. Trevisan 《Algorithmica》2000,28(1):145-172
We study the approximability of the Maximum Satisfiability Problem (MAX SAT) and of the boolean k -ary Constraint Satisfaction Problem (MAX k CSP) restricted to satisfiable instances. For both problems we improve on the performance ratios of known algorithms for
the unrestricted case.
Our approximation for satisfiable MAX 3CSP instances is better than any possible approximation for the unrestricted version
of the problem (unless P=NP). This result implies that the requirement of perfect completeness weakens the acceptance power
of non-adaptive PCP verifiers that read 3 bits.
We also present the first non-trivial results about PCP classes defined in terms of free bits that collapse to P.
Received August 1997; revised February 1999. 相似文献
4.
A bipartite graph G=(U,V,E) is a chain graph [M. Yannakakis, Computing the minimum fill-in is NP-complete, SIAM J. Algebraic Discrete Methods 2 (1) (1981) 77–79] if there is a bijection such that Γ(π(1))Γ(π(2))Γ(π(|U|)), where Γ is a function that maps a node to its neighbors.We give approximation algorithms for two variants of the Minimum Chain Completion problem, where we are given a bipartite graph G(U,V,E), and the goal is find the minimum set of edges F that need to be added to G such that the bipartite graph G′=(U,V,E′) (E′=EF) is a chain graph. 相似文献
5.
We consider the problem of finding a minimum diameter spanning tree
with maximum node degree $B$ in a complete undirected edge-weighted
graph. We provide an $O(\sqrt{\log_Bn})$-approximation algorithm for the
problem. Our algorithm is purely combinatorial, and relies on a
combination of filtering and divide and conquer. 相似文献
6.
We consider the problem of finding a minimum diameter spanning tree
with maximum node degree $B$ in a complete undirected edge-weighted
graph. We provide an $O(\sqrt{\log_Bn})$-approximation algorithm for the
problem. Our algorithm is purely combinatorial, and relies on a
combination of filtering and divide and conquer. 相似文献
7.
8.
A cycle cover of a graph is a spanning subgraph, each node of which is part of exactly one simple cycle. A k-cycle cover is a cycle cover where each cycle has length at least k. Given a complete directed graph with edge weights zero and one, Max-k-DDC(0,1) is the problem of finding a k-cycle cover with maximum weight. We present a 2/3 approximation algorithm for Max-k-DDC(0,1) with running time O(n 5/2). This algorithm yields a 4/3 approximation algorithm for Max-k-DDC(1,2) as well. Instances of the latter problem are complete directed graphs with edge weights one and two. The goal is to find a k-cycle cover with minimum weight. We particularly obtain a 2/3 approximation algorithm for the asymmetric maximum traveling salesman problem with distances zero and one and a 4/3 approximation algorithm for the asymmetric minimum traveling salesman problem with distances one and two. As a lower bound, we prove that Max-k-DDC(0,1) for k 3 and Max-k-UCC(0,1) (finding maximum weight cycle covers
in undirected graphs) for k 7 are \APX-complete. 相似文献
9.
Let G be a graph which is k -outconnected from a specified root node r , that is, G has k openly disjoint paths between r and v for every node v . We give necessary and sufficient conditions for the existence of a pair rv,rw of edges for which replacing these edges by a new edge vw gives a graph that is k -outconnected from r . This generalizes a theorem of Bienstock et al. on splitting off edges while preserving k -node-connectivity.
We also prove that if C is a cycle in G such that each edge in C is critical with respect to k -outconnectivity from r , then C has a node v , distinct from r , which has degree k . This result is the rooted counterpart of a theorem due to Mader.
We apply the above results to design approximation algorithms for the following problem: given a graph with nonnegative edge
weights and node requirements c
u
for each node u , find a minimum-weight subgraph that contains max {c
u
,c
v
} openly disjoint paths between every pair of nodes u,v . For metric weights, our approximation guarantee is 3 . For uniform weights, our approximation guarantee is \min{ 2, (k+2q-1)/k} . Here k is the maximum node requirement, and q is the number of positive node requirements.
Received September 15, 1998; revised March 10, 2000, and April 17, 2000. 相似文献
10.
A tree (tour) cover of an edge-weighted graph is a set of edges
which forms a tree (closed walk) and covers every other edge in the graph.
Arkin et al. give approximation
algorithms with ratios 3.55 (tree cover) and 5.5 (tour cover).
We present algorithms with a worst-case ratio of 3 for both problems. 相似文献
11.
A tree (tour) cover of an edge-weighted graph is a set of edges
which forms a tree (closed walk) and covers every other edge in the graph.
Arkin et al. give approximation
algorithms with ratios 3.55 (tree cover) and 5.5 (tour cover).
We present algorithms with a worst-case ratio of 3 for both problems. 相似文献
12.
We study minimisation of integer linear programs with positive right-hand sides. We show that such programs can be approximated within the maximum absolute row sum of the constraint matrix A whenever the variables are allowed to take values in N. This result is optimal under the unique games conjecture. When the variables are restricted to bounded domains, we show that finding a feasible solution is NP-hard in almost all cases. 相似文献
13.
We present an NC approximation algorithm for the weighted matching problem in graphs with an approximation ratio of (1−ε). This improves the previously best approximation ratio of of an NC algorithm for this problem. 相似文献
14.
Julián Mestre 《Algorithmica》2009,55(1):227-239
We study the partial vertex cover problem. Given a graph G=(V,E), a weight function w:V→R
+, and an integer s, our goal is to cover all but s edges, by picking a set of vertices with minimum weight. The problem is clearly NP-hard as it generalizes the well-known
vertex cover problem. We provide a primal-dual 2-approximation algorithm which runs in O(nlog n+m) time. This represents an improvement in running time from the previously known fastest algorithm.
Our technique can also be used to get a 2-approximation for a more general version of the problem. In the partial capacitated vertex cover problem each vertex u comes with a capacity k
u
. A solution consists of a function x:V→ℕ0 and an orientation of all but s edges, such that the number of edges oriented toward vertex u is at most x
u
k
u
. Our objective is to find a cover that minimizes ∑
v∈V
x
v
w
v
. This is the first 2-approximation for the problem and also runs in O(nlog n+m) time.
Research supported by NSF Awards CCR 0113192 and CCF 0430650, and the University of Maryland Dean’s Dissertation Fellowship. 相似文献
15.
16.
Approximating minimum cocolorings 总被引:1,自引:0,他引:1
A cocoloring of a graph G is a partition of the vertex set of G such that each set of the partition is either a clique or an independent set in G. Some special cases of the minimum cocoloring problem are of particular interest.We provide polynomial-time algorithms to approximate a minimum cocoloring on graphs, partially ordered sets and sequences. In particular, we obtain an efficient algorithm to approximate within a factor of 1.71 a minimum partition of a partially ordered set into chains and antichains, and a minimum partition of a sequence into increasing and decreasing subsequences. 相似文献
17.
Let $G=(V,E)$ be an undirected multigraph with a special vertex
${\it root} \in V$, and where each edge $e \in E$ is endowed with a
length $l(e) \geq 0$ and a capacity $c(e) > 0$. For a path $P$
that connects $u$ and $v$, the {\it transmission time} of $P$ is
defined as $t(P)=\mbox{\large$\Sigma$}_{e \in P} l(e) + \max_{e \in P}\!{(1 /
c(e))}$. For a spanning tree $T$, let $P_{u,v}^T$ be the unique $u$--$v$
path in $T$. The {\sc quickest radius spanning tree problem} is to find
a spanning tree $T$ of $G$ such that $\max _{v \in V} t(P^T_{root,v})$ is
minimized. In this paper we present a 2-approximation algorithm for
this problem, and show that unless $P =NP$, there is no approximation
algorithm with a performance guarantee of $2 - \epsilon$ for any
$\epsilon >0$. The {\sc quickest diameter spanning tree problem} is
to find a spanning tree $T$ of $G$ such that $\max_{u,v \in V}
t(P^T_{u,v})$ is minimized. We present a ${3 \over 2}$-approximation
to this problem, and prove that unless $P=NP$
there is no approximation algorithm with a performance guarantee of
${3 \over 2}-\epsilon$ for any $\epsilon >0$. 相似文献
18.
Let $G=(V,E)$ be an undirected multigraph with a special vertex
${\it root} \in V$, and where each edge $e \in E$ is endowed with a
length $l(e) \geq 0$ and a capacity $c(e) > 0$. For a path $P$
that connects $u$ and $v$, the {\it transmission time} of $P$ is
defined as $t(P)=\mbox{\large$\Sigma$}_{e \in P} l(e) + \max_{e \in P}\!{(1 /
c(e))}$. For a spanning tree $T$, let $P_{u,v}^T$ be the unique $u$--$v$
path in $T$. The {\sc quickest radius spanning tree problem} is to find
a spanning tree $T$ of $G$ such that $\max _{v \in V} t(P^T_{root,v})$ is
minimized. In this paper we present a 2-approximation algorithm for
this problem, and show that unless $P =NP$, there is no approximation
algorithm with a performance guarantee of $2 - \epsilon$ for any
$\epsilon >0$. The {\sc quickest diameter spanning tree problem} is
to find a spanning tree $T$ of $G$ such that $\max_{u,v \in V}
t(P^T_{u,v})$ is minimized. We present a ${3 \over 2}$-approximation
to this problem, and prove that unless $P=NP$
there is no approximation algorithm with a performance guarantee of
${3 \over 2}-\epsilon$ for any $\epsilon >0$. 相似文献
19.
Frédéric Chataigner 《Information Processing Letters》2005,93(5):239-244
The Maximum Agreement Forest problem (MAF) asks for the largest common subforest of a set of binary trees. This problem is known to be MAXSNP-complete for instances consisting of 2 trees. We show that it remains MAXSNP-complete for k?2 trees. 相似文献
20.
The Dense k -Subgraph Problem 总被引:1,自引:0,他引:1
This paper considers the problem of computing the dense k -vertex subgraph of a given graph, namely, the subgraph with the most edges. An approximation algorithm is developed for
the problem, with approximation ratio O(n
δ
) , for some δ < 1/3 .
Received April 29, 1997; revised June 26, 1998, and April 13, 1999. 相似文献