报告题目：

A local search 2.917-approximation algorithm for duo-preservation string mapping problem

时间：2017年4月11日（星期二）下午15:30

地点：理学院会议室18-918

报告人：加拿大阿尔伯塔大学， 林国辉 教授

研究领域：

Dr. Lin has two lines of research interests, one is Combinatorial Optimization, mostly on approximability and inapproximability, and the other is Bioinformatics, especially on cattle genomics and human proteomics, metabolomics, and lipidomics.

报告摘要：

Problems of string comparison have a wide range of applications in the fields such as text compression and bioinformatics. One of the most common measurements is to compute the edit distance between two strings, which is the minimum number of operations (including insertion, deletion, and/or substitution operations) required to transform one string into the other. When only the "shifting" operations, also known as rearrangements, are allowed, and shifting a substring is also considered as a single operation, the problem of measuring edit distance between two strings is referred to as the minimum common string partition problem, which is known to be APX-hard. In this talk, we will discuss its complement, the maximum duo-preservation string mapping problem, and present an improved local search approximation algorithm through a complex yet interesting amortized analysis.