一、报告题目：Better approximating SONET k-edge partition for small capacity k
二、报告人： 陈永 教授
三、时 间：2025年1月13日(周一) 上午 09:00-10:00
四、地 点：A4-216
报告摘要：We study the SONET edge partition problem that models telecommunication network design to partition a given graph into several subgraphs each of size no greater than a given capacity k such that the sum of the orders of these subgraphs is minimized. The problem is NP-hard when k ≥ 3 and admits an O(log k)-approximation algorithm. For small capacity k = 3, 4, 5, by observing that some subgraph structures are more favorable than the others, we propose modifications to existing algorithms and design novel amortization schemes to prove their improved performance. Our algorithmic results include a 4/3-approximation for 3-EP, improving the previous best 13/9-approximation, a 4/3–approximation for 4-EP, improving the previous best (4/3+ ε)-approximation, and a 3/2-approximation for 5-EP, improving the previous best 5/3-approximation. Besides these improved algorithms, our main contribution is the amortization scheme design, which can be helpful for similar algorithms and problems.
报告人简介：陈永，教授，博导，杭州电子科技大学理学院数学系。现任中国运筹学会排序分会理事、中国工业与应用数学学会数学模型专业委员会委员。研究兴趣为算法理论，主要针对组合优化、图论与网络优化和排序理论进行算法设计与分析。已发表高水平SCI期刊论文和算法理论国际会议论文40多篇，主持国家自然科学基金面上项目2项，并参与多项省部级以上科研项目。曾先后访问加拿大阿尔伯塔大学、东京电机大学等，与国内外知名学者开展合作研究。
欢迎广大师生参加！ 联系人：理学院图论团队
