排序方式: 共有15条查询结果,搜索用时 15 毫秒
1.
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$. 相似文献
2.
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$. 相似文献
3.
We study bottleneck labeled optimization problems arising in the context of graph theory. This long-established model partitions
the set of edges into classes, each of which is identified by a unique color. The generic objective is to construct a subgraph
of prescribed structure (such as an s-t path, a spanning tree, or a perfect matching) while trying to minimize the maximum (or, alternatively, maximize the minimum)
number of edges picked from any given color. 相似文献
4.
We consider two allocation problems in this paper, namely, allocation of bandwidth and storage. In these problems, we face a number of independent requests, respectively, for reservation of bandwidth of a communication channel of fixed capacity and for storage of items into a space of fixed size. In both problems, a request is characterized by: (i) its required period of allocation; (ii) its required bandwidth (item width, respectively)and (iii)the profit of accepting the request. The problem is to decide which requests to accept so as to maximize the total profit. These problems in general are NP-hard. In this paper we provide polynomial-time algorithms for solving various special cases, and develop polynomial-time approximation algorithms for very general NP-hard cases with good performance guarantees. 相似文献
5.
Let G be an undirected 2-edge connected graph with nonnegative edge weights and a distinguished vertex z. For every node consider the shortest cycle containing this node and z in G. The cycle-radius of G is the maximum length of a cycle in this set. Let H be a directed graph obtained by directing the edges of G. The cycle-radius of H is similarly defined except that cycles are replaced by directed closed walks. We prove that there exists for every nonnegative edge weight function an orientation H of G whose cycle-radius equals that of G if and only if G is series-parallel. 相似文献
6.
The input to the metric maximum clustering problem with given cluster sizes consists of a complete graph G=(V,E) with edge weights satisfying the triangle inequality, and integers c1,…,cp. The goal is to find a partition of V into disjoint clusters of sizes c1,…,cp, maximizing the sum of weights of edges whose two ends belong to the same cluster. We describe an approximation algorithms for this problem with performance guarantee that approaches 0.5 when the cluster sizes are large. 相似文献
7.
Simcha Finkelman Shlomo Navarro Miriam Rindner Refael Dias Avi Azrieli 《Journal of Stored Products Research》2004,40(5):499-506
This study forms part of an effort to eliminate the need for methyl bromide fumigation to control insects in stored commodities, through development of a novel “vacuum-hermetic” technology. The effects of low pressures and exposure times on the mortality of insects in stored cocoa beans were studied at a temperature of 30°C in order to simulate cocoa bean storage conditions in tropical climates. Insects were exposed within test chambers containing the cocoa beans at a moisture content in equilibrium with 55% r.h. and at a constant temperature of 30°C. Three species of insects were used, all being major pests of cocoa beans in producer countries: Ephestia cautella (Walker), Plodia interpunctella (Hübner) and Tribolium castaneum (Herbst). At 50±5 mmHg, the egg stage was the most resistant in all three species, times needed to obtain 99% mortality being 45, 49 and 22 h, respectively. Results show that low-pressure treatment can provide an additional and more effective option to the 5 days fumigation with phosphine used today in the replacement of methyl bromide. The use of low pressures allows the control of insect pests at shorter exposure times without the need for toxic chemicals with their environmental impact. 相似文献
8.
We study a capacitated network design problem with applications in
local access network design. Given a network, the problem is to route
flow from several sources to a sink and to install
capacity on the edges to support the flow at minimum cost.
Capacity can be purchased only in multiples of a fixed quantity.
All the flow from a source must be routed
in a single path to the sink. This NP-hard problem generalizes the
Steiner tree problem and also more effectively models the applications
traditionally formulated as capacitated tree problems. We present
an approximation algorithm with performance ratio
(ST + 2) where ST is the performance ratio of
any approximation algorithm for the minimum Steiner tree problem.
When all sources have unit demand, the ratio
improves to ST + 1) and, in particular, to 2 when all nodes
in the graph are sources. 相似文献
9.
We consider a graph with n vertices, and p<n pebbles of m colors. A pebble move consists of transferring a pebble from its current host vertex to an adjacent unoccupied vertex. The
problem is to move the pebbles to a given new color arrangement. 相似文献
10.
We study a capacitated network design problem with applications in
local access network design. Given a network, the problem is to route
flow from several sources to a sink and to install
capacity on the edges to support the flow at minimum cost.
Capacity can be purchased only in multiples of a fixed quantity.
All the flow from a source must be routed
in a single path to the sink. This NP-hard problem generalizes the
Steiner tree problem and also more effectively models the applications
traditionally formulated as capacitated tree problems. We present
an approximation algorithm with performance ratio
(ρST + 2) where ρST is the performance ratio of
any approximation algorithm for the minimum Steiner tree problem.
When all sources have unit demand, the ratio
improves to ρST + 1) and, in particular, to 2 when all nodes
in the graph are sources. 相似文献