Better approximating SONET k-edge partition for small capacity k

Junhui Ye (), Huihuang Jiang (), Guangting Chen (), Yong Chen (), Guohui Lin () and An Zhang ()
Additional contact information
Junhui Ye: Hangzhou Dianzi University
Huihuang Jiang: Hangzhou Dianzi University
Guangting Chen: Zhejiang University of Water Resources and Electric Power
Yong Chen: Hangzhou Dianzi University
Guohui Lin: University of Alberta
An Zhang: Hangzhou Dianzi University

Journal of Combinatorial Optimization, 2025, vol. 49, issue 4, No 13, 24 pages

Abstract: Abstract We study the SONET edge partition problem that models telecommunication network design to partition the edge set of a given graph into several edge-disjoint subgraphs, such that each subgraph has size no greater than a given capacity k and the sum of the orders of these subgraphs is minimized. The problem is NP-hard when $$k \ge 3$$ k ≥ 3 and admits an $$O(\log k)$$ O ( log k ) -approximation algorithm. For small capacity $$k = 3, 4, 5$$ 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 $$\frac{4}{3}$$ 4 3 -approximation for $$k = 3$$ k = 3 , improving the previous best $$\frac{13}{9}$$ 13 9 -approximation, a $$\frac{4}{3}$$ 4 3 -approximation for $$k = 4$$ k = 4 , improving the previous best $$(\frac{4}{3} + \epsilon )$$ ( 4 3 + ϵ ) -approximation, and a $$\frac{3}{2}$$ 3 2 -approximation for $$k = 5$$ k = 5 , improving the previous best $$\frac{5}{3}$$ 5 3 -approximation. Besides these improved algorithms, our main contribution is the amortization scheme design, which can be helpful for similar algorithms and problems.

Keywords: Edge partition; Synchronous optical networking; Greedy; Amortized analysis; Approximation algorithm. (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-025-01308-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:49:y:2025:i:4:d:10.1007_s10878-025-01308-0

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-025-01308-0

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().