现在位置:首页 > 学术报告
 

 

Academy of Mathematics and Systems Science, CAS
Colloquia & Seminars

Speaker:

Dr.Guohui Lin,University of Alberta

Inviter: 闫桂英 研究员
Title:
A local search 4/3-approximation algorithm for the minimum 3-path partition problem
Time & Venue:
2019.6.21 10:30 N602
Abstract:
Given a graph G = (V, E), the 3-path partition problem is to find a minimum collection of vertex-disjoint paths each of order at most 3 to cover all the vertices of V. It is different from but closely related to the well-known 3-set cover problem. The best known approximation algorithm for the 3-path partition problem was proposed recently and has a ratio 13/9. Here we present a local search algorithm and show, by an amortized analysis, that it is a 4/3-approximation.This ratio matches up to the best approximation ratio for the 3-set cover problem.
 

 

附件下载:
 
 
【打印本页】【关闭本页】
电子政务平台   |   科技网邮箱   |   ARP系统   |   会议服务平台   |   联系我们   |   友情链接