Polynomial time approximation algorithms are proposed with constant approximation factors for a problem of computing the smallest cardinality set of identical disks whose union intersects each segment from a given set...
详细信息
ISBN:
(纸本)9783030226299;9783030226282
Polynomial time approximation algorithms are proposed with constant approximation factors for a problem of computing the smallest cardinality set of identical disks whose union intersects each segment from a given set E of n straight line segments on the plane. This problem has important applications in operations research, namely in wireless and road network analysis. It is equivalent to finding the least cardinality piercing (or hitting) set for the corresponding family of n Euclidean r-neighborhoods of straight line segments of E on the plane, which are called r-hippodromes in the literature. When the number of distinct orientations is upper bounded by k of segments from E, a simple O(n log n)-time 4k-approximate algorithm is known for this problem. Besides, when E contains arbitrary straight line segments, overlapping at most at their endpoints, O(n(4) log n)-time 100-approximate algorithm is given recently. In the present paper, simple approximation algorithms are proposed with small approximation factors for E, being edge set of some special plane graphs of interest in road network applications;here the number of distinct orientations of straight line segments from E can be arbitrarily large. More precisely, O(n(2))-time approximation algorithms are constructed for edge sets of either Gabriel or relative neighborhood graphs or of Euclidean minimum spanning trees with factors of 14, 12 and 10 respectively. These algorithms are much faster, more accurate and conceptually much simpler than the aforementioned 100-approximate algorithm for the general case of the problem on edge sets of arbitrary plane graphs.
In this paper we describe together with an overview about other results the main ideas of our polynomial time approximation schemes for the maximum weight independent set problem (selecting a set of disjoint disks in ...
详细信息
ISBN:
(纸本)9783540748380
In this paper we describe together with an overview about other results the main ideas of our polynomial time approximation schemes for the maximum weight independent set problem (selecting a set of disjoint disks in the plane of maximum total weight) in disk graphs and for the maximum bisection problem (finding a partition of the vertex set into twosubsets of equal cardinality with maximum number of edges between the subsets) in unit-disk graphs.
In this paper we study variants of the non-preemptive parallel job scheduling problem where the number of machines is polynomially bounded in the number of jobs. For this problem we show that a schedule With length at...
详细信息
ISBN:
(纸本)9783540705741
In this paper we study variants of the non-preemptive parallel job scheduling problem where the number of machines is polynomially bounded in the number of jobs. For this problem we show that a schedule With length at most (1 + epsilon) OPT can be calculated in polynomial time. which is the best possible result (in the sense of approximation ratio);since the problem is strongly NP-hard. For the case when all jobs must be allotted to a, subset of machines with consecutive indices a schedule with length at most (1.5 + epsilon) OPT can be calculated in polynomial time. The previously best known results are algorithms with absolute approximation ratio 2.
We consider the Capacitated Damnation problem, which models a service-requirement assignment scenario and is a generalization to the well-known Dominating Set problem. In this problem, given a graph with three paramet...
详细信息
ISBN:
(纸本)9783642145520
We consider the Capacitated Damnation problem, which models a service-requirement assignment scenario and is a generalization to the well-known Dominating Set problem. In this problem, given a graph with three parameters defined on each vertex, namely cost, capacity, and demand, we want to find an assignment of demands to vertices of least cost such that the demand of each vertex is satisfied subject to the capacity constraint of each vertex providing the service. In terms of polynomial time approximations, we present logarithmic approximation algorithms with respect to different demand assignment models on general graphs. On the other hand, from the perspective of parameterization, we prove that this problem is W[1]-hard when parameterized by a structure of the graph called treewidth. Based on this hardness result, we present exact fixed-parameter tractable algorithms with respect to treewidth and maximum capacity of the vertices. This algorithm is further extended to obtain pseudo-polynomial time approximation schemes for planar graphs.
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...
详细信息
ISBN:
(纸本)9783642036842
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. We design in 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 ail tipper 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.
In the Steiner Tree Augmentation Problem (STAP), we are given a graph G = (V, E), a set of terminals R subset of V, and a Steiner tree T spanning R. The edges L := E \ E(T) are called links and have non-negative costs...
详细信息
ISBN:
(纸本)9781611977554
In the Steiner Tree Augmentation Problem (STAP), we are given a graph G = (V, E), a set of terminals R subset of V, and a Steiner tree T spanning R. The edges L := E \ E(T) are called links and have non-negative costs. The goal is to augment T by adding a minimum cost set of links, so that there are 2 edge-disjoint paths between each pair of vertices in R. This problem is a special case of the Survivable Network Design Problem, which can be approximated to within a factor of 2 using iterative rounding [13]. We give the first polynomial time algorithm for STAP with approximation ratio better than 2. In particular, we achieve an approximation ratio of (1.5 + epsilon). To do this, we employ the Local Search approach of [24] for the Tree Augmentation Problem and generalize their main decomposition theorem from links (of size two) to hyper-links. We also consider the Node-Weighted Steiner Tree Augmentation Problem (NW-STAP) in which the nonterminal nodes have non-negative costs. We seek a cheapest subset S subset of V \ R so that G[R boolean OR S] is 2-dge-connected. Using a result of Nutov [18], there exists an O(log vertical bar R vertical bar)-approximation for this problem. We provide an O(log(2)(vertical bar R vertical bar))-approximation algorithm for NW-STAP using a greedy algorithm leveraging the spider decomposition of optimal solutions.
The stable marriage problem is a classical matching problem introduced by Gale and Shapley. It is known that for any instance, there exists a solution, and there is a polynomial time algorithm to find one. However, th...
详细信息
ISBN:
(纸本)9783540739487
The stable marriage problem is a classical matching problem introduced by Gale and Shapley. It is known that for any instance, there exists a solution, and there is a polynomial time algorithm to find one. However, the matching obtained by this algorithm is man-optimal, that is, the matching is preferable for men but unpreferable for women, (or, if we exchange the role of men and women, the resulting matching is woman-optimal). The sex-equal stable marriage problem posed by Gus-field and Irving asks to find a stable matching "fair" for both genders, namely it asks to find a stable matching with the property that the sum of the men's score is as close as possible to that of the women's. This problem is known to be strongly NP-hard. In this paper, we give a polynomial time algorithm for finding a near optimal solution in the sex-equal stable marriage problem. Furthermore, we consider the problem of optimizing additional criterion: among stable matchings that are near optimal in terms of the sex-equality, find a minimum egalitarian stable matching. We show that this problem is NP-hard, and give a polynomial time algorithm whose approximation ratio is less than two.
We give first constant-factor approximations for various cases of the coupled-task single machine and two-machine flow shop scheduling problems with exact delays and makespan as the objective function. In particular, ...
详细信息
ISBN:
(纸本)9783540695134
We give first constant-factor approximations for various cases of the coupled-task single machine and two-machine flow shop scheduling problems with exact delays and makespan as the objective function. In particular, we design 3.5- and 3-approximation algorithms for the general cases of the single-machine and the two-machine problems, respectively. We also prove that the existence of a (2 - epsilon)-approximation algorithm for the single-machine problem as well as the existence of a (1.5 - epsilon)-approximation algorithm for the two-machine problem implies P = NP. The inapproximability results are valid for the cases when the operations of each job have equal processing times and for these cases the approximation ratios achieved by. our algorithms are very close to best possible: we prove that the single machine problem is approximable within a factor of 2.5 and the two-machine problem is approximable within a factor of 2.
Motivated by the need for, and growing interest in, modeling uncertainty in data, we introduce and study stochastic minimum-norm optimization. We have an underlying combinatorial optimization problem where the costs i...
详细信息
ISBN:
(纸本)9781728196213
Motivated by the need for, and growing interest in, modeling uncertainty in data, we introduce and study stochastic minimum-norm optimization. We have an underlying combinatorial optimization problem where the costs involved are random variables with given distributions;each feasible solution induces a random multidimensional cost vector, and given a certain objective function, the goal is to find a solution (that does not depend on the realizations of the costs) that minimizes the expected objective value. For instance, in stochastic load balancing, jobs with random processing times need to be assigned to machines, and the induced cost vector is the machine- load vector. The choice of objective is typically the maximum- or sum-of the entries of the cost vector, or in some cases some other pound.p norm of the cost vector. Recently, in the deterministic setting, Chakrabarty and Swamy [7] considered a much broader suite of objectives, wherein we seek to minimize the f- norm of the cost vector under a given arbitrary monotone, symmetric norm f. In stochastic minimum- norm optimization, we work with this broad class of objectives, and seek a solution that minimizes the expected f-norm of the induced cost vector. The class of monotone, symmetric norms is versatile and includes pound.p-norms, and TOPe-norms (sum of *** coordinates in absolute value), and enjoys various closure properties;in particular, it can be used to incorporate multiple norm budget constraints, f (x) pound <= Be, pound. = 1,..., k. We give a general framework for devising algorithms for stochastic minimum- norm combinatorial optimization, using which we obtain approximation algorithms for the stochastic minimum- norm versions of the load balancing and spanning tree problems. We obtain the following concrete results. An O(1)-approximation for stochastic minimum-norm load balancing on unrelated machines with: (i) arbitrary monotone symmetric norms and job sizes that are Bernoulli random variab
In this paper, we investigate the problem of scheduling weighted jobs on a single machine with a maintenance whose starting time is prior to a given deadline and whose duration is a nondecreasing function of the start...
详细信息
ISBN:
(纸本)9783642143540
In this paper, we investigate the problem of scheduling weighted jobs on a single machine with a maintenance whose starting time is prior to a given deadline and whose duration is a nondecreasing function of the starting time. We are asked not only to schedule the jobs but also the maintenance such that the total weighted job completion time is minimum. The problem is shown to be weakly NP-hard. In the case that the duration of the maintenance is a concave (and nondecreasing) function of its starting time, we provide two approximation algorithms with approximation ratio of 2 and at most 1 + root 2/2 + epsilon, respectively.
暂无评论