In this paper we present improved approximation results for the max duo-preservation string mapping problem (MPSM) introduced in [Chen et al., Theoretical Computer Science, 2014] that is complementary to the well-stud...
详细信息
ISBN:
(纸本)9783662447536;9783662447529
In this paper we present improved approximation results for the max duo-preservation string mapping problem (MPSM) introduced in [Chen et al., Theoretical Computer Science, 2014] that is complementary to the well-studied min common string partition problem (MCSP). When each letter occurs at most k times in each string the problem is denoted by k-MPSM. First, we prove that k-MPSM is APX-Hard even when k = 2. Then, we improve on the previous results by devising two distinct algorithms: the first ensures approximation ratio 8/5 for k = 2 and ratio 3 for k = 3, while the second guarantees approximation ratio 4 for any bigger value of k. Finally, we address the approximation of constrained maximum induced subgraph (CMIS, a generalization of MPSM, also introduced in [Chen et al., Theoretical Computer Science, 2014]), and improve the best known 9-approximation for 3-CMIS to a 6-approximation, by using a configuration LP to get a better linear relaxation. We also prove that such a linear program has an integrality gap of k, which suggests that no constant approximation (i.e. independent of k) can be achieved through rounding techniques.
We present an improved approximation for the Maximum Duo-Preservation string Mapping problem (MPSM). This problem was introduced in [7] as the complement to the well-studied minimum commonstringpartitionproblem (MC...
详细信息
ISBN:
(数字)9783319436814
ISBN:
(纸本)9783319436814;9783319436807
We present an improved approximation for the Maximum Duo-Preservation string Mapping problem (MPSM). This problem was introduced in [7] as the complement to the well-studied minimum commonstringpartitionproblem (MCSP). Prior work also considers the k-MPSM and k-MCSP variants in which each letter occurs at most k times. The authors of [7] showed a k(2)-appoximation for k >= 3 and 2-approximation for k = 2. A 4-approximation independent of k was shown in [4]. In [4], they also showed that k-MPSM is APX-Hard and achieved approximation ratios of 8/5 for k = 2 and 3 for k = 3. In this paper, we show an algorithm which achieves a 13/4-approximation for the general MPSM problem using a new combinatorial triplet matching approach. During publication of this paper, [3] presented a local search algorithm yielding 7/2, which falls in between the previous best and this paper. The remainder of the paper has not been altered to reflect this.
暂无评论