共查询到20条相似文献,搜索用时 609 毫秒
1.
Jie Wang 《Journal of Combinatorial Optimization》1999,3(4):453-463
We study an optimization problem of packing unequal spheres into a three-dimensional (3D) bounded region in connection with radiosurgical treatment planning. Given an input (R, V, S, L), where R is a 3D bounded region, V a positive integer, S a multiset of spheres, and L a location constraint on spheres, we want to find a packing of R using the minimum number of spheres in S such that the covered volume is at least V; the location constraint L is satisfied; and the number of points on the boundary of R that are touched by spheres is maximized. Such a packing arrangement corresponds to an optimal radiosurgical treatment planning. Finding an optimal solution to the problem, however, is computationally intractable. In particular, we show that this optimization problem and several related problems are NP-hard. Hence, some form of approximations is needed. One approach is to consider a simplified problem under the assumption that spheres of arbitrary (integral) diameters are available with unlimited supply, and there are no location constraints. This approach has met with certain success in medical applications using a dynamic programming algorithm (Bourland and Wu, 1996; Wu, 1996). We propose in this paper an improvement to the algorithm that can greatly reduce its computation cost. 相似文献
2.
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. 相似文献
3.
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. 相似文献
4.
This paper solves the problem of increasing the edge-connectivity of a bipartite digraph by adding the smallest number of new edges that preserve bipartiteness. A natural application arises when we wish to reinforce a 2-dimensional square grid framework with cables. We actually solve the more general problem of covering a crossing family of sets with the smallest number of directed edges, where each new edge must join the blocks of a given bipartition of the elements. The smallest number of new edges is given by a min-max formula that has six infinite families of exceptional cases. We discuss a problem on network flows whose solution has a similar formula with three infinite families of exceptional cases. We also discuss a problem on arborescences whose solution has five infinite families of exceptions. We give an algorithm that increases the edge-connectivity of a bipartite digraph in the same time as the best-known algorithm for the problem without the bipartite constraint: O(km log n) for unweighted digraphs and O(nm log (n
2/m)) for weighted digraphs, where n, m and k are the number of vertices and edges of the given graph and the target connectivity, respectively. 相似文献
5.
We consider some inverse min-max (or max-min) network problems. Such an inverse problem is to modify the weights with bound
constraints so that a given feasible solution becomes an optimal solution of a min-max (or max-min) network problem, and the
deviation of the weights, measured by the weighted l
1 norm or weighted l
∞ norm, is minimum. In this paper, we present strongly polynomial time algorithms to solve the inverse min-max spanning tree
problem and the inverse maximum capacity path problem. 相似文献
6.
We study a new coloring concept which generalizes the classical vertex coloring problem in a graph by extending the notion
of stable sets to split graphs. First of all, we propose the packing problem of finding the split graph of maximum size where
a split graph is a graph G = (V,E) in which the vertex set V can be partitioned into a clique K and a stable set S. No condition is imposed on the edges linking vertices in S to the vertices in K. This maximum split graph problem gives rise to an associated partitioning problem that we call the split-coloring problem.
Given a graph, the objective is to cover all his vertices by a least number of split graphs. Definitions related to this new
problem are introduced. We mention some polynomially solvable cases and describe open questions on this area.
An erratum to this article is available at . 相似文献
7.
Since the seminal work of Ford and Fulkerson in the 1950s, network flow theory is one of the most important and most active areas of research in combinatorial optimization. Coming from the classical maximum flow problem, we introduce and study an apparently basic but new flow problem that features a couple of interesting peculiarities. We derive several results on the complexity and approximability of the new problem. On the way we also discover two closely related basic covering and packing problems that are of independent interest. Starting from an LP formulation of the maximum s-t-flow problem in path variables, we introduce unit upper bounds on the amount of flow being sent along each path. The resulting (fractional) flow problem is NP-hard; its integral version is strongly NP-hard already on very simple classes of graphs. For the fractional problem we present an FPTAS that is based on solving the k shortest paths problem iteratively. We show that the integral problem is hard to approximate and give an interesting O(log?m)-approximation algorithm, where m is the number of arcs in the considered graph. For the multicommodity version of the problem there is an $O(\sqrt{m})Since the seminal work of Ford and Fulkerson in the 1950s, network flow theory is one of the most important and most active
areas of research in combinatorial optimization. Coming from the classical maximum flow problem, we introduce and study an
apparently basic but new flow problem that features a couple of interesting peculiarities. We derive several results on the
complexity and approximability of the new problem. On the way we also discover two closely related basic covering and packing
problems that are of independent interest.
Starting from an LP formulation of the maximum s-t-flow problem in path variables, we introduce unit upper bounds on the amount of flow being sent along each path. The resulting
(fractional) flow problem is NP-hard; its integral version is strongly NP-hard already on very simple classes of graphs. For
the fractional problem we present an FPTAS that is based on solving the k shortest paths problem iteratively. We show that the integral problem is hard to approximate and give an interesting O(log m)-approximation algorithm, where m is the number of arcs in the considered graph. For the multicommodity version of the problem there is an
O(?m)O(\sqrt{m})
-approximation algorithm. We argue that this performance guarantee is best possible, unless P=NP. 相似文献
8.
Let G=(V,E) be a graph without isolated vertices. A set S⊆V is a paired-dominating set if every vertex in V−S is adjacent to a vertex in S and the subgraph induced by S contains a perfect matching. The paired-domination problem is to determine the paired-domination number, which is the minimum
cardinality of a paired-dominating set. Motivated by a mistaken algorithm given by Chen, Kang and Ng (Discrete Appl. Math.
155:2077–2086, 2007), we present two linear time algorithms to find a minimum cardinality paired-dominating set in block and interval graphs.
In addition, we prove that paired-domination problem is NP-complete for bipartite graphs, chordal graphs, even for split graphs. 相似文献
9.
The Steiner tree problem asks for a minimum cost tree spanning a given set of terminals S⊂eqV in a weighted graph G = (V,E,c), c:E→ R+. In this paper we consider a generalization of the Steiner tree problem, so called Polymatroid Steiner Problem, in which a polymatroid P = P(V) is defined on V and the Steiner tree is required to span at least one base of P (in particular, there may be a single base S⊂eqV). This formulation is motivated by the following application in sensor networks – given a set of sensors S = {s1,…,sk}, each sensor si can choose to monitor only a single target from a subset of targets Xi, find minimum cost tree spanning a set of sensors capable of monitoring the set of all targets X = X1 ∪ … ∪ Xk. The Polymatroid Steiner Problem generalizes many known Steiner tree problem formulations including the group and covering Steiner tree problems. We show that this problem can be solved with the polylogarithmic approximation ratio by a generalization of the combinatorial algorithm of Chekuri et al. (2002).We also define the Polymatroid directed Steiner problem which asks for a minimum cost arborescence connecting a given root to a base of a polymatroid P defined on the terminal set S. We show that this problem can be approximately solved by algorithms generalizing methods of Chekuri et al. (2002).A preliminary version of this paper appeared in ISAAC 2004 相似文献
10.
Energy efficient multicast problem is one of important issues in ad hoc networks. In this paper, we address the energy efficient
multicast problem for discrete power levels in ad hoc wireless networks. The problem of our concern is: given n nodes deployed over 2-D plane and each node v has l(v) transmission power levels and a multicast request (s,D) (clearly, when D is V∖{s}, the multicast request is a broadcast request), how to find a multicast tree rooted at s and spanning all destinations in D such that the total energy cost of the multicast tree is minimized. We first prove that this problem is NP-hard and it is
unlikely to have an approximation algorithm with performance ratio ρlnn(ρ<1). Then, we propose a general algorithm for the multicast/broadcast tree problem. And based on the general algorithm, we
propose an approximation algorithm and a heuristics for multicast tree problem. Especially, we also propose an efficient heuristic
for broadcast tree problem. Simulations ensure our algorithms are efficient. 相似文献
11.
Given a graph G=(V,E) with node weight w:V→R
+, the minimum weighted connected vertex cover problem (MWCVC) is to seek a subset of vertices of the graph with minimum total
weight, such that for any edge of the graph, at least one endpoint of the edge is contained in the subset, and the subgraph
induced by this subset is connected. In this paper, we study the problem on unit disk graph. A polynomial-time approximation
scheme (PTAS) for MWCVC is presented under the condition that the graph is c-local. 相似文献
12.
In this paper, we consider the center location improvement problems under the sum-type and bottleneck-type Hamming distance. For the sum-type problem, we show that achieving an algorithm with a worst-case ratio of O(log |V|) is NP-hard, and for the bottleneck-type problem, we present a strongly polynomial algorithm. 相似文献
13.
The two-dimensional strip packing problem is a generalization of the classic one-dimensional bin packing problem. It has many important applications such as costume clipping, material cutting, real-world planning, packing, scheduling etc. Average-case performance analysis of approximation algorithms attracts a lot of attention because it plays a crucial role in selecting an appropriate algorithm for a given application. While approximation algorithms for two-dimensional packing are frequently presented, the results of their average-case performance analyses have seldom been reported due to intractability. In this paper, we analyze the average-case performance of Next Fit Decreasing Height (NFDH) algorithm, one of the first strip packing algorithms proposed by Coffman, Jr. in 1980. We prove that the expected height of packing with NFDH algorithm, when the heights and widths of the rectangle items are independent and both obey (0, 1] uniform distribution, is about n/3, where n is the number of rectangle items. We also validate the theoretical result with experiments.This work is supported by National 973 Fundamental Research Project of China on NP Complete Problems and High Performance Software (No. G1998030403). 相似文献
14.
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. 相似文献
15.
Order Consolidation for Batch Processing 总被引:3,自引:0,他引:3
We consider the batch processing of orders where either whole or part of a single order or a specific pair of different orders may be grouped in a batch with a fixed capacity. The problem can be modelled by a graph G = (V,E), where each node v
V corresponds to an order, its weight w(v) corresponds to the amount of ordered quantity and a pair of orders, say u and v may be grouped in a batch if there exists the edge (u,v)
E. The objective is to maximize the number of batches filled up to its capacity
. In this paper, we prove that the problem is NP-hard and, moreover, that no PTAS exists unless P = NP. Then, an optimal algorithm is developed with running time O(|V|log |V|) for the special case when G is a tree. 相似文献
16.
The problem of computing the strength and performing optimal reinforcement for an edge-weighted graph G(V, E, w) is well-studied. In this paper, we present fast (sequential linear time and parallel logarithmic time) on-line algorithms for optimally reinforcing the graph when the reinforcement material is available continuously on-line. These are the first on-line algorithms for this problem. We invest O(|V|3|E|log|V|) time (equivalent to (|V|) invocations of the fastest known algorithms for optimal reinforcement) in preprocessing the graph before the start of our algorithms. It is shown that the output of our on-line algorithms is as good as that of the off-line algorithms. Thus our algorithms are better than the fastest off-line algorithms in situations when a sequence of more than (|V|) reinforcement problems need to be solved. The key idea is to make use of ideas underlying the theory of Principal Partition of a Graph. Our ideas are easily generalized to the general setting of polymatroid functions. We also present a new efficient algorithm for computation of the Principal Sequence of a graph. 相似文献
17.
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. 相似文献
18.
Yong Zhang Francis Y. L. Chin Hing-Fung Ting Xin Han 《Journal of Combinatorial Optimization》2013,26(2):223-236
In this paper, we study 1-space bounded multi-dimensional bin packing and hypercube packing. A sequence of items arrive over time, each item is a d-dimensional hyperbox (in bin packing) or hypercube (in hypercube packing), and the length of each side is no more than 1. These items must be packed without overlapping into d-dimensional hypercubes with unit length on each side. In d-dimensional space, any two dimensions i and j define a space P ij . When an item arrives, we must pack it into an active bin immediately without any knowledge of the future items, and 90°-rotation on any plane P ij is allowed. The objective is to minimize the total number of bins used for packing all these items in the sequence. In the 1-space bounded variant, there is only one active bin for packing the current item. If the active bin does not have enough space to pack the item, it must be closed and a new active bin is opened. For d-dimensional bin packing, an online algorithm with competitive ratio 4 d is given. Moreover, we consider d-dimensional hypercube packing, and give a 2 d+1-competitive algorithm. These two results are the first study on 1-space bounded multi dimensional bin packing and hypercube packing. 相似文献
19.
Mohammad Khairul Hasan Hyunwoo Jung Kyung-Yong Chwa 《Journal of Combinatorial Optimization》2008,16(2):155-172
We study Connected Facility Location problems. We are given a connected graph G=(V,E) with nonnegative edge cost c
e
for each edge e∈E, a set of clients D⊆V such that each client j∈D has positive demand d
j
and a set of facilities F⊆V each has nonnegative opening cost f
i
and capacity to serve all client demands. The objective is to open a subset of facilities, say
, to assign each client j∈D to exactly one open facility i(j) and to connect all open facilities by a Steiner tree T such that the cost
is minimized for a given input parameter M≥1. We propose a LP-rounding based 8.29 approximation algorithm which improves the previous bound 8.55 (Swamy and Kumar in
Algorithmica, 40:245–269, 2004). We also consider the problem when opening cost of all facilities are equal. In this case we give a 7.0 approximation algorithm. 相似文献
20.
Let G be a undirected connected graph. Given g groups each being a subset of V(G) and a number of colors, we consider how to find a subgroup of subsets such that there exists a tree interconnecting all
vertices in each subset and all trees can be colored properly with given colors (no two trees sharing a common edge receive
the same color); the objective is to maximize the number of subsets in the subgroup. This problem arises from the application
of multicast communication in all optical networks. In this paper, we first obtain an explicit lower bound on the approximability
of this problem and prove Ω(g1−ε)-inapproximability even when G is a mesh. We then propose a simple greedy algorithm that achieves performance ratio O√|E(G)|, which matches the theoretical bounds.
Supported in part by the NSF of China under Grant No. 70221001 and 60373012. 相似文献