加拿大阿尔贝塔大学林国辉教授学术报告-中南大学信息科学与工程学院门户网站

首页
学院新闻
学院公告
学术信息
就业信息

加拿大阿尔贝塔大学林国辉教授学术报告

来源: 点击: 时间: 2018年06月27日 10:05

报告题目:Approximation algorithms for two-machine flow-shop scheduling with a conflict graph

报告时间:2018年6月29日上午10:00

报告地点:校本部升华后楼215

报告简介:

Path cover is a well-known intractable problem that finds a minimum number of vertex disjoint paths in a given graph to cover all the vertices. We show that a variant, where the objective function is not the number of paths but the number of length-0 paths (that is, isolated vertices), turns out to be polynomial-time solvable. We further show that another variant, where the objective function is the total number of length-0 and length-1 paths, is also polynomial-time solvable. Both variants find applications in approximating the two-machine flow-shop scheduling problem in which job processing has constraints that are formulated as a conflict graph. For the unit jobs, we present a 4/3-approximation algorithm for the scheduling problem with an arbitrary conflict graph, based on the exact algorithm for the variants of the path cover problem.

报告人简介:

林国辉,阿尔贝塔大学计算机科学系终身教授。1993年浙江大学应用数学系本科,1997年中国科学院博士(导师:堵丁柱教授)。长期从事组合优化、近似算法设计与分析,生物信息学等研究工作,发表论文200余篇,其中在国际顶尖和知名期刊发表并被SCI(SSCI)收录140余篇。主持加拿大自然科学与工程基金委项目4项,共同主持加拿大基因组研究大项目1项、加拿大脑科学研究大项目1项以及其它国家级和省级研究基金项目10余项。研究成果获1997年“中国科学院院长创新基金奖”和2003年“加拿大创新机会基金奖”。2008年至今,任国际期刊《Journal of Combinatorial Optimization》副主编。


返回首页

上一条:新加坡工程院院士,南洋理工大学Alex Chichung KOT教授学术报告

下一条:挪威奥斯陆大学张彦教授学术报告