Speaker：Yong Chen (Hangzhou Dianzi University)

Time：2024-7-1, 10:00

Location：Conference Room 661 at the 6th floor of Shuli Building at Haiyun Campus

Abstract:

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.