Approximation Algorithms for the Maximum Duo-preservation String Mapping Problem

摘要：

We introduce the maximum duo-preservation string mapping problem (MPSM), which is complementary to the minimum common string partition problem (MCSP). When each letter occurs at most times in any input string, the version of MPSM is called -MPSM. Using Linear Programming method, we propose an approximation algorithm for 2-MPSM with approximation ratio 2, an approximation algorithm for 3-MPSM with approximation ratio 9, and an approximation algorithm for 4-MPSM with approximation ratio 16. We also design a 0-1 Integer Programming formulation for MCSP to pave the way for approximation algorithms of MCSP using randomized rounding method.

关键词： Approximation Algorithm Duo-preservation string mapping Linear Programming Integer Programming Randomized Rounding

作者: Wenbin Chen Zhengzhang Chen Nagiza F. Samatova

作者单位: Department of Computer Science North Carolina State University Raleigh, U.S.A Computer Science and Mathematics Division Oak Ridge National Laboratory Oak Ridge, U.S.A

会议类型: 国际会议

会议名称: 2010 International Conference on Future Information Technology(2010年未来信息技术国际会议 ICFIT 2010)

会议地点: 长沙

会议语种:英文

页码: 190-198

在线出版日期: 2010-12-14（万方平台首次上网日期，不代表论文的发表时间）