【理学院】An Improved Approximation Algorithm for the Minimum Common Integer Partition Problem

报告题目：An Improved Approximation Algorithm for the Minimum Common Integer Partition Problem

报告摘要：Given a collection of multisets {X_1, X_2, ..., X_k} (k >= 2) of positive integers, a multiset S is a common integer partition for them if S is an integer partition of every multiset X_i. The minimum common integer partition (k-MCIP) problem is defined as to find a CIP for {X_1, X_2, ..., X_k} with the minimum cardinality. We present a 6/5-approximation algorithm for the 2-MCIP problem, improving the previous best algorithm of ratio 5/4 designed in 2006. We then extend it to obtain a direct (not de-randomized) 3k/5-approximation algorithm for k-MCIP.

报告人：Guohui Lin，Professor（University of Alberta, Canada）

时 间：6月10日（本周二）下午 15：20—16：20

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

人物名片1：

Guohui Lin is a full professor of computing science at the University of Alberta, Canada. He received his BSc in applied mathematics from ZhejiangUniversity and PhD in theoretical computer science from Chinese Academic Sciences. He did the postdoc research at University of Vermont, McMasterUniversity and University of Waterloo. He joined the University of Alberta in 2001. His major research areas are algorithm design and analysis and omics. He has published more than 140 peer reviewed papers, served as associate editors for four international journals, and been (co-)principle investigators for six multi-million-dollar projects in the past five years.