Improved approximation algorithms for the SONET k-edge partition problem for small capacity k

：陈永（杭州电子科技大学）
：2024-07-01 10:00
：海韵园数理大楼661

报告人：陈永（杭州电子科技大学）

时  间：2024年7月1日10:00

地  点：海韵园数理大楼661

内容摘要:

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 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.

个人简介：

陈永，杭州电子科技大学数学系教授，博士生导师。2011年毕业于浙江大学数学系，曾在加拿大阿尔伯塔大学和日本东京大学进行访问研究。陈永教授的主要研究领域包括离散优化和图论算法，专注于近似算法研究，如图划分、排序及相关问题。他在多个知名期刊如Information and Computation、Algorithmica、TCS、EJOR等上发表了多篇重要论文。

 

联系人：刘龙城