Given a collection of phylogenetic trees with identical leaf label-set, the Maximum Agreement Forest problem (maf) asks for a largest common subforest of these input trees. The maf problem on two binary phylogenetic t...
详细信息
ISBN:
(纸本)9783319087832;9783319087825
Given a collection of phylogenetic trees with identical leaf label-set, the Maximum Agreement Forest problem (maf) asks for a largest common subforest of these input trees. The maf problem on two binary phylogenetic trees has been studied extensively in the literature. In this paper, we will be focused on the maf problem on multiple (i.e., two or more) binary phylogenetic trees and present two polynomial-time approximation algorithms, one for the maf problem on multiple rooted trees, and the other for the maf problem on multiple unrooted trees. The ratio of our algorithm for the maf problem on multiple rooted trees is 3, which is an improvement over the previously best ratio 8 for the problem. Our 4-approximation algorithm for the maf problem on multiple unrooted trees is the first approximation algorithm for the problem.
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 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.
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.
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.
暂无评论