The translocation operation is one of the popular operations for genome rearrangement. In this paper, we present a algorithm for computing unsigned translocation distance which improves upon the best known 2-approxima...
详细信息
The translocation operation is one of the popular operations for genome rearrangement. In this paper, we present a algorithm for computing unsigned translocation distance which improves upon the best known 2-approximation algorithm [J. Kececioglu, R. Ravi, Of mice and men: algorithms for evolutionary distances between genomes with translocation, in: 6th ACM-SIAM Symposium on Discrete algorithms, 1995, pp. 604-6131. (c) 2007 Elsevier Inc. All rights reserved.
We consider the facility location problem with submodular penalties (FLPSP), introduced by Hayrapetyan et al. (Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete algorithms (SODA), pp. 933-942, 2005), ...
详细信息
We consider the facility location problem with submodular penalties (FLPSP), introduced by Hayrapetyan et al. (Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete algorithms (SODA), pp. 933-942, 2005), who presented a 2.50-approximation algorithm that is non-combinatorial because this algorithm has to solve the LP-relaxation of an integer program with exponential number of variables. The only known polynomial algorithm for this exponential LP is via the ellipsoid algorithm as the corresponding separation problem for its dual program can be solved in polynomial time. By exploring the properties of the submodular function, we offer a primal-dual 3-approximation combinatorial algorithm for this problem.
An l-pseudoforest is a graph each of whose connected components is at most I edges removal being a tree. The l-Pseudoforest Deletion problem is to delete a vertex set P of minimum weight from a given vertex-weighted g...
详细信息
An l-pseudoforest is a graph each of whose connected components is at most I edges removal being a tree. The l-Pseudoforest Deletion problem is to delete a vertex set P of minimum weight from a given vertex-weighted graph G = (V, E) such that the remaining graph G[V \ P] is an l-pseudoforest The Feedback Vertex Set problem is a special case of the l-Pseudoforest Deletion problem with l = 0. In this paper, we present a polynomial time 41-approximation algorithm for the l-Pseudoforest Deletion problem with l >= 1 by using the local ratio technique. When l=1, we get a better approximation ratio 2 for the problem by further analyzing the local ratio, which matches the current best constant approximation factor for the Feedback Vertex Set problem. (C) 2019 Elsevier B.V. All rights reserved.
We consider the following planar maximum weight triangulation (MAT) problem: given a set of n points in the plane, find a triangulation such that the total length of edges in triangulation is maximized. We prove an Om...
详细信息
We consider the following planar maximum weight triangulation (MAT) problem: given a set of n points in the plane, find a triangulation such that the total length of edges in triangulation is maximized. We prove an Omega(root n) lower bound on the approximation factor for several heuristics: maximum greedy triangulation, maximum greedy spanning tree triangulation and maximum spanning tree triangulation. We then propose the Spoke Triangulation algorithm, which approximates the maximum weight triangulation for points in general position within a factor of almost four in O(n log n) time. The proof is simpler than the previous work. We also prove that Spoke Triangulation approximates the maximum weight triangulation of a convex polygon within a factor of two.
The maximum duo-preservation string mapping (MAX-DUO) problem is the complement of the well studied minimum common string partition problem, both of which have applications in many fields including text compression an...
详细信息
The maximum duo-preservation string mapping (MAX-DUO) problem is the complement of the well studied minimum common string partition problem, both of which have applications in many fields including text compression and bioinformatics. k-MAX-DUO is the restricted version of MAX-DUO, where every letter of the alphabet occurs at most k times in each of the strings, which is readily reduced into the well known maximum independent set (MIS) problem on a graph of maximum degree Delta <= 6(k - 1). In particular, 2-MAX-DUO can then be approximated arbitrarily close to 1.8 using the state-of-the-art approximation algorithm for the MIS problem on bounded-degree graphs. 2-MAX-DUO was proved APX-hard and very recently a (1.6 + C)-approximation algorithm was claimed, for any C > 0. In this paper, we present a vertex-degree reduction technique, based on which, we show that 2-MAX-DUO can be approximated arbitrarily close to 1.4.
Given a set ofn points on the plane, the rectilinearm-center problem is to findn rectilinear squares covering all thesen points such that the maximum side length of these squares is minimized. In this paper we prove t...
详细信息
Given a set ofn points on the plane, the rectilinearm-center problem is to findn rectilinear squares covering all thesen points such that the maximum side length of these squares is minimized. In this paper we prove that there is no polynomial-time algorithm with an error ratio ? < 2 for the rectilinearm-center problem unless NP = P. A polynomial-time approximation algorithm with an error ratio of 2 is also proposed.
In this paper, we study two variants of the classical facility location problem, namely, the facility location problem with linear penalties (FLPLP) and the facility location problem with submodular penalties (FLPSP),...
详细信息
In this paper, we study two variants of the classical facility location problem, namely, the facility location problem with linear penalties (FLPLP) and the facility location problem with submodular penalties (FLPSP), respectively. We give a unified dual-fitting based approximation algorithm for these two problems, yielding approximation ratios 2 and 3 respectively.
Given a graph G=(V,E), we seek for a collection of vertex disjoint paths each of order at most 3 that together cover all the vertices of V. The problem is called 3-path partition, and it has close relationships to the...
详细信息
Given a graph G=(V,E), we seek for a collection of vertex disjoint paths each of order at most 3 that together cover all the vertices of V. The problem is called 3-path partition, and it has close relationships to the well-known path cover problem and the set cover problem. The general k-path partition problem for a constant k3 is NP-hard, and it admits a trivial k-approximation. When k=3, the previous best approximation ratio is 1.5 due to Monnot and Toulouse (Oper Res Lett 35:677-684, 2007), based on two maximum matchings. In this paper we first show how to compute in polynomial time a 3-path partition with the least 1-paths, and then apply a greedy approach to merge three 2-paths into two 3-paths whenever possible. Through an amortized analysis, we prove that the proposed algorithm is a 13/9-approximation. We also show that the performance ratio 13/9 is tight for our algorithm.
We provide the first nontrivial approximation algorithm for MAXIMUM WEIGHT PLANAR SUBGRAPH, the NP-hard problem of finding a heaviest planar subgraph in an edge-weighted graph G. This problem has applications in circu...
详细信息
We provide the first nontrivial approximation algorithm for MAXIMUM WEIGHT PLANAR SUBGRAPH, the NP-hard problem of finding a heaviest planar subgraph in an edge-weighted graph G. This problem has applications in circuit layout, facility layout, and graph drawing. No previous algorithm for MAXIMUM WEIGHT PLANAR SUBGRAPH had a performance ratio exceeding 1/3, which is obtained by any algorithm that produces a maximum weight spanning tree in G. Based on the Berman-Ramaiyer Steiner tree algorithm, the new algorithm has performance ratio at least 1/3 + 1/72 and at most 5/12. We also show that if G is complete and its edge weights satisfy the triangle inequality, then the performance ratio is at least 3/8. Furthermore, we derive the first nontrivial performance ratio (7/12 instead of 1/2) for the NP-hard MAXIMUM WEIGHT OUTERPLANAR SUBGRAPH problem.
In this paper,we consider the parallel-machine customer order scheduling with delivery time and submodular rejection *** this problem,we are given m dedicated machines in parallel and n customer *** order has a delive...
详细信息
In this paper,we consider the parallel-machine customer order scheduling with delivery time and submodular rejection *** this problem,we are given m dedicated machines in parallel and n customer *** order has a delivery time and consists of m product types and each product type should be manufactured on a dedicated *** order is either rejected,in which case a rejection penalty has to be paid,or accepted and manufactured on the m dedicated *** objective is to find a solution to minimize the sum of the maximum delivery completion time of the accepted orders and the penalty of the rejected orders which is determined by a submodular *** design an LP rounding algorithm with approximation ratio of n+1 for this problem.
暂无评论