报告题目 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项，并参与多项省部级以上科研项目。曾先后访问加拿大阿尔伯塔大学、东京电机大学等，与国内外著名学者开展广泛合作研究。