当前位置:首页 |  学术沙龙

加拿大阿尔伯特大学林国辉教授学术报告

加拿大阿尔伯特大学林国辉教授学术报告

信息来源: 福州大学物理与信息工程学院 发布日期: 2017-03-29

演讲人:林国辉教授

时间地点: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.