首页 > 正文

【11月10日】陈永教授学术报告

发布时间:2022-11-08文章来源:002cc白菜资讯苗翠霞 浏览次数:

报告题目 Improved approximation algorithms for the unit stop number problem

报告人:陈永 教授

报告时间:2022年11月12 19:30-20:30

报告地点:腾讯会议平台967-349-268

报告简介: The Unit Stop Number Problem (USNP) is described as follows. In a modern transport system, we are given a fixed transport circuit with predefined n stations, p identical capacitated electrical vehicles (each of them has the same capacity C, where C ≥ 1 is an integer) and m unit-load transport demands (defined by an origin station and a different destination station). The fleet of these identical capacitated electrical vehicles travels around the circuit (always in the same direction) to serve these demands and stops at a station upon request. The Unit Stop Number Problem consists of assigning each demand to a vehicle such that no vehicle gets overloaded, and the total number of vehicles’ stops is minimized. Recently, this problem has been proved to be NP-hard even when C = 2 and the authors proposed a simple C-approximation algorithm. Moreover, the authors also proved the Intersection USNP (a variant where there exists some special station that is crossed by all demands) is NP-hard even when C = 3. In this paper, we first design a Multi-Merge approximation algorithm and then prove its worst-case ratio is  for the general USNP,  for the Intersection USNP. Furthermore, we propose an improved approximation algorithm based on maximum matching for the Intersection USNP with C = 3, and prove its tight worst-case ratio is 9/8. In summary, we present some new and improved approximation results when compared to the algorithms reported in the literature.

报告人简介:陈永,杭州电子科技大学数学系教授,中国运筹学会排序分会理事。主要研究兴趣为离散优化问题的近似算法与计算复杂性。在Algorithmica、EJOR、TCS、JOCO等期刊发表论文30多篇,主持国家自然科学基金3项,并参与多项省部级以上科研项目。曾先后访问加拿大阿尔伯塔大学、东京电机大学等,与国内外著名学者开展广泛合作研究。


关闭 打印责任编辑:孔祥立

友情链接