发表日期:2017年3月29日    阅读:524 




讲座内容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.

演讲人简历:Dr. Guohui Lin is currently a Professor of Computing Science at the University of Alberta, with tenure. He was an Assistant and then an Associate Professor at the same university since 2001. He obtained his PhD degree in Computer Science, specialized in Combinatorial Optimization, in 1998 from the Chinese Academy of Sciences (Thesis Supervisor Dr. Ding-Zhu Du); and he obtained Master of Science and Bachelor of Science in Applied Mathematics in 1995 and 1993, respectively, from the Zhejiang University. 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.

上一篇:IEEE Fellow徐敬文教授莅临我院交流访问
下一篇:IEEE Fellow林楠教师科研团队系列讲座

Copyright 2010