宁波大学

学术活动

甬江数学讲坛127讲(2020年第54讲)

发布日期:2020-11-11 作者:数学与统计澳门葡京 文章来源:未知  责任编辑:

报告题目:Approximation Algorithms for Some Multi-Vehicle Stacker Crane Problems

人:余炜(华东理工大学 副教授)

报告时间:20201119  上午9:00开始

报告地点:腾讯会议ID4829624974密码:485075

报告摘要:We study a variety of extensions of the Stacker Crane Problem to a situation with k1 vehicles. The input consists of a mixed graph G=(V,E,A) with vertex set V, edge set E, arc set A and a nonnegative integer cost function c on EA. We consider three types of problems. (1) k-depot SCP (k-DSCP). There is a depot set D?V containing k distinct depots and one vehicle is located at a distinct depot initially. The goal is to determine a collection of k closed walks including all the arcs of A such that the total cost of the closed walks is minimized, where each closed walk corresponds to the route of one vehicle and has to start from a distinct depot and return to it. (2) k-SCP. There are no given depots and each vehicle may start from any vertex and then go back to it. The goal is to find a collection of k closed walks including all the arcs of A such that the total cost of the closed walks is minimized. (3) k-depot Stacker Crane Path Problem (k-DSCPP). There is a depot set D?V containing k distinct depots. The aim is to find k (open) walks including all the arcs of A such that the total cost of the walks is minimized, where each (open) walk has to start from a distinct depot but may end at any vertex. We present the first constant-factor approximation algorithms for all the above three problems. To be specific, we give 3-approximation algorithms for the k-DSCP, the k-SCP and the k-DSCPP. If the costs of the arcs are symmetric, i.e. for every arc there is a parallel edge of no greater cost, we develop better algorithms with approximation ratios max{9/5,2-1/(2k+1)}, 2, 2, respectively. All the proposed algorithms have a time complexity of O(|V|3) except that the two 2-approximation algorithms run in O(|V|2log|V|) time.

报告人简介:余炜,华东理工大学理澳门葡京副教授,研究方向为组合优化、排序与路线问题、图覆盖问题、旅行商选址问题、算法博弈论等。2010年博士毕业于华东理工大学数学专业,随后进入浙江大学计算机澳门葡京进行为期两年的博士后研究,期间曾访问香港科技大学。20161-20171月在多伦大学访问。已在运筹学主流刊物《European Journal of Operational Research》、《Naval Research Logistics》、《Operations Research Letters》、《Networks》、《Annals of Operations Research》、《Journal of Combinatorial Optimization》、《Theoretical Computer Science》发表论文10余篇。

上一条:物理讲坛(2020年第23讲) 下一条:甬江数学讲坛126讲(2020年第53讲)

关闭