演讲人：林国辉教授
时间地点：4月1(周六)下午2：30，物理与信息工程学院309房间
讲座内容：A local search 2.917-approximation algorithm for duo-preservation string mapping problem
摘要：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.
学术沙龙