演讲人：林国辉教授
时间地点：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.
演讲人简历：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.
最新动态