We study the problem of packing element-disjoint Steiner trees in graphs. We are given a graph and a designated subset of terminal nodes, and the goal is to find a maximum cardinality set of element-disjoint trees suc...
详细信息
We study the problem of packing element-disjoint Steiner trees in graphs. We are given a graph and a designated subset of terminal nodes, and the goal is to find a maximum cardinality set of element-disjoint trees such that each tree contains every terminal node. An element means a non-terminal node or an edge. (Thus, each non-terminal node and each edge must be in at most one of the trees.) We show that the problem is APX-hard when there are only three terminal nodes, thus answering an open question. Our main focus is on the special case when the graph is planar. We show that the problem of finding two element-disjoint Steiner trees in a planar graph is NP-hard. Similarly, the problem of finding two edge-disjoint Steiner trees in a planar graph is NP-hard. We design an algorithm for planar graphs that achieves an approximation guarantee close to 2. In fact, given a planar graph that is k element-connected on the terminals (k is an upper bound on the number of element-disjoint Steiner trees), the algorithm returns [k/2] - 1 element-disjoint Steiner trees. Using this algorithm, we get an approximation algorithm for the edge-disjoint version of the problem on planar graphs that improves on the previous approximation guarantees. We also show that the natural LP relaxation of the planar problem has an integrality ratio approaching 2.
Given a weighted graph G on n + 1 vertices, a spanning K-tree T-K of G is defined to be a spanning tree T of G together with K distinct edges of G that are not edges of T. The objective of the minimum-cost spanning K-...
详细信息
Given a weighted graph G on n + 1 vertices, a spanning K-tree T-K of G is defined to be a spanning tree T of G together with K distinct edges of G that are not edges of T. The objective of the minimum-cost spanning K-tree problem is to choose a subset of edges to form a spanning K-tree with the minimum weight. In this paper, we consider the constructing spanning K-tree problem that is a generalization of the minimum-cost spanning K-tree problem. We are required to construct a spanning K-tree T-K whose n + K edges are assembled from some stock pieces of bounded length L. Let c(0) be the sale price of each stock piece of length L and k(T-K) the number of minimum stock pieces to construct the n + K edges in T-K. For each edge e in G, let c(e) be the construction cost of that edge e. Our new objective is to minimize the total cost of constructing a spanning K-tree T-K, i.e., min(TK) {Sigma(e is an element of TK) c(e) + k(T-K) . c(0)}. The main results obtained in this paper are as follows. (1) A 2-approximation algorithm to solve the constructing spanning K-tree problem. (2) A 3/2-approximation algorithm to solve the special case for constant construction cost of edges. (3) An APTAS for this special case.
We study network-design problems with two different design objectives: the total cost of the edges and nodes in the network and the maximum degree of any node in the network. A prototypical example is the degree-const...
详细信息
We study network-design problems with two different design objectives: the total cost of the edges and nodes in the network and the maximum degree of any node in the network. A prototypical example is the degree-constrained node-weighted Steiner tree problem: We are given an undirected graph G(V, E), with a nonnegative integral function d that specifies an upper bound d(v) on the degree of each vertex v is an element of V in the Steiner tree to be constructed, nonnegative costs on the nodes, and a subset of k nodes called terminals. The goal is to construct a Steiner tree T containing all the terminals such that the degree of any node v in T is at most the specified upper bound d(v) and the total cost of the nodes in T is minimum. Our main result is a bicriteria approximation algorithm whose output is approximate in terms of both the degree and cost criteria-the degree of any node v is an element of V in the output Steiner tree is O(d(v)log k) and the cost of the tree is 0(log k) times that of a minimum-cost Steiner tree that obeys the degree bound d(v) for each node v. Our result extends to the more general problem of constructing one-connected networks such as generalized Steiner forests. We also consider the special case in which the edge costs obey the triangle inequality and present simple approximation algorithms with better performance guarantees.
We introduce the Bipartite Multicut problem. This is a generalization of the st-Mincut problem is similar to the Multicut problem and also turns out to be an immediate generalization of the Min UnCut problem. We prove...
详细信息
We introduce the Bipartite Multicut problem. This is a generalization of the st-Mincut problem is similar to the Multicut problem and also turns out to be an immediate generalization of the Min UnCut problem. We prove that this problem is NP-hard and then present an SDP based approximation algorithm. The SDP based approximation algorithm uses the structure theorem of l(2)(2) metrics along with region growing techniques. (C) 2010 Elsevier B.V. All rights reserved.
IN lhIS PAPER WE DISCUSS APPROXIM AMON ALGORI1hMS fOR ThE ELEMENT -DISJOINT STEINER TREE PACKING PrObLEM (Element-STP foR show). FOR A GRAPh G = (V, E) AND A subsEr of NODES T c V, CAVED TERMINAL NODES, A STEINER TREE...
详细信息
IN lhIS PAPER WE DISCUSS APPROXIM AMON ALGORI1hMS fOR ThE ELEMENT -DISJOINT STEINER TREE PACKING PrObLEM (Element-STP foR show). FOR A GRAPh G = (V, E) AND A subsEr of NODES T c V, CAVED TERMINAL NODES, A STEINER TREE IS A CONNECTED, ACyCLIC SUbGRAPh lhAT CONTAINS AIL1hE TERMINAL NODES IN T. ThE GOAL Of Element-STP IS 10 fiND AS MANY EIEMENT=DISJOINTSTEINERTREES AS POSSIblE. Element-STP IS KNOWN 10 bE P X-hARD EVEN foR right perpendicular vertical bar T vertical bar/2left perpendicular = 3 [I]. IT IS ALSO KNOWN ThAT Element-STP IS NP-hAPD 10 APPROXIMATE WITh vertical bar T vertical bar A fACTOR of n(log M) [3] AND lhERE IS AN O(log vertical bar V vertical bar)-APPROXIMMION ALGORI1hM foR Element-STP [2], [4]. IN lhIS PAPER WE PROVIDE right perpendicular vertical bar T vertical bar/2left perpendicular approximation ALGORI111M foR Element-STP ON GRAPhS WIlh IT I TERMINAL NODES. FURITERMORE, WE ShOW 1hAT1hE approximation RATIO of 3 foR Element-STP ON GRAPhS WI1h fiVE TERM INALNODES CAN bE IMPROVED TO 2.
This article considers the problem of finding a shortest tour to visit viewing sets of points on a plane. Each viewing set is represented as an inverted view cone with apex angle alpha and height h. The apex of each c...
详细信息
This article considers the problem of finding a shortest tour to visit viewing sets of points on a plane. Each viewing set is represented as an inverted view cone with apex angle alpha and height h. The apex of each cone is restricted to lie on the ground plane. Its orientation angle (tilt) epsilon is the angle difference between the cone bisector and the ground plane normal. This is a novel variant of the 3D Traveling Salesman Problem with Neighborhoods (TSPN) called Cone-TSPN. One application of Cone-TSPN is to compute a trajectory to observe a given set of locations with a camera: for each location, we can generate a set of cones whose apex and orientation angles alpha and epsilon correspond to the camera's field of view and tilt. The height of each cone h corresponds to the desired resolution. Recently, Plonski and Isler presented an approximation algorithm for Cone-TSPN for the case where all cones have a uniform orientation angle of epsilon=0. We study a new variant of Cone-TSPN where we relax this constraint and allow the cones to have non-uniform orientations. We call this problem Tilted Cone-TSPN and present a polynomial-time approximation algorithm with ratio O(1+tan alpha 1-tan epsilon tan alpha(1+logmax(H)min(H))), where H is the set of all cone heights. We demonstrate through simulations that our algorithm can be implemented in a practical way and that by exploiting the structure of the cones we can achieve shorter tours. Finally, we present experimental results from various agriculture applications that show the benefit of considering view angles for path planning.
Motivated by issues in allocating limited preventative resources to protect a landscape against the spread of a wildfire from a stochastic ignition point, we give approximation algorithms for a new family of stochasti...
详细信息
Motivated by issues in allocating limited preventative resources to protect a landscape against the spread of a wildfire from a stochastic ignition point, we give approximation algorithms for a new family of stochastic optimization problems. We study several models in which we are given a graph with edge costs and node values, a budget, and a probabilistic distribution over ignition nodes: the goal is to find a budget-limited set of edges whose removal protects the largest expected value from being reachable from a stochastic ignition node. In particular, 2-stage stochastic models capture the tradeoffs between preventative treatment and real-time response. The resulting stochastic cut problems are interesting in their own right, and capture a number of related interdiction problems, both in the domain of computational sustainability, and beyond. In trees, even the deterministic problem is (weakly) NP hard: we give a Polynomial-time approximation scheme for the single-stage stochastic case in trees when the number of scenarios is constant. For the 2-stage stochastic model in trees we give a -approximation in trees which violates the budget by a factor of at most 2 (delta is the tree diameter), and a 0.387-approximation that is budget-balanced. For the single-stage stochastic case in trees we can save (1- (1 - 1/delta) (delta)) OPT without violating the budget. Single-stage results extend to general graphs with an additional O(log n) loss in budget-balancedness. Multistage results have a similar extension when the number of scenarios is constant. In an extension of the single-stage model where both ignition and spread are stochastic we give a -approximation in trees. Our approximation guarantees in trees also hold for multistage and probabilistic-element-failure generalizations of the Maximum Coverage with Knapsack Constraint problem (MCKP).
In this paper, we present new approximation results for the offline problem of single machine scheduling with sequence-independent set-ups and item availability, where the jobs to be scheduled are independent (i.e., h...
详细信息
In this paper, we present new approximation results for the offline problem of single machine scheduling with sequence-independent set-ups and item availability, where the jobs to be scheduled are independent (i.e., have no precedence constraints) and have a common release time. We present polynomial-time approximation algorithms for two versions of this problem. In the first version, the input includes a weight for each job, and the goal is to minimize the total weighted completion time. On any input, our algorithm produces a schedule whose total weighted completion time is within a factor 2 of optimal for that input. In the second version, the input includes a due date for each job, and the goal is to minimize the maximum lateness of any job. On any input, our algorithm produces a schedule with the following performance guarantee: the maximum lateness of a job is at most the maximum lateness of the optimal schedule on a machine that runs at half the speed of our machine. (C) 2007 Elsevier B.V. All rights reserved.
LetR be a rectangle and letP be a set of points located insideR. Our problem consists of introducing a set of line segments of least total length to partition the interior ofR into rectangles. Each rectangle in a vali...
详细信息
LetR be a rectangle and letP be a set of points located insideR. Our problem consists of introducing a set of line segments of least total length to partition the interior ofR into rectangles. Each rectangle in a valid partition must not contain points fromP as interior points. Since this partitioning problem is computationally intractable (NP-hard), we present efficient approximation algorithms for its solution. The solutions generated by our algorithms are guaranteed to be within three times the optimal solution value. Our algorithm also generates solutions within four times the optimal solution value whenR is a rectilinear polygon. Our algorithm can be generalized to generate good approximation solutions for the case whenR is a rectilinear polygon, there are rectilinear polygonal holes, and the sum of the length of the boundaries is not more than the sum of the length of the edges in an optimal solution.
We study the distance constrained vehicle routing problem (DVRP) (Laporte et al., Networks 14 (1984), 47-61, Li et al., Oper Res 40 (1992), 790-799): given a set of vertices in a metric space, a specified depot, and a...
详细信息
We study the distance constrained vehicle routing problem (DVRP) (Laporte et al., Networks 14 (1984), 47-61, Li et al., Oper Res 40 (1992), 790-799): given a set of vertices in a metric space, a specified depot, and a distance bound D, find a minimum cardinality set of tours originating at the depot that covers all vertices, such that each tour has length at most D. This problem is NP-complete, even when the underlying metric is induced by a weighted star. Our main result is a 2-approximation algorithm for DVRP on tree metrics;we also show that no approximation factor better than 1.5 is possible unless P = NP. For the problem on general metrics, we present a (O(log 1/epsilon), 1 + epsilon)-bicriteria approximation algorithm: i.e., for any epsilon > 0, it obtains a solution violating the length bound by a 1 + epsilon factor while using at most O(log 1/epsilon) times the optimal number of vehicles. (C) 2011 Wiley Periodicals, Inc. NETWORKS, Vol. 59(2), 209-214 2012
暂无评论