2021/05/31 by Angelika Wiegele, Shudian Zhao
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics #Complexity and Algorithms in Graphs #Discrete mathematics #Equipartition theorem #Graph #Graph partition #Heuristics #Knapsack problem #Mathematical optimization #Mathematics #Partition (number theory) #Upper and lower bounds #Vehicle Routing Optimization Methods #math.OC
paper · pdf · doi:10.1007/s10589-022-00355-1
40 pages, 3 figures, 14 tables. Comput Optim Appl (2022)
openalex publication_date 2022/03/17 · arxiv created 2022/03/22 · arxiv updated 2022/03/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
We study two NP-complete graph partition problems, k-equipartition problems and graph partition problems with knapsack constraints (GPKC). We introduce tight SDP relaxations with nonnegativity constraints to get lower bounds, the SDP relaxations are solved by an extended alternating direction method of multipliers (ADMM). In this way, we obtain high quality lower bounds for k-equipartition on large instances up to n =1000 vertices within as few as five minutes and for GPKC problems up to n=500 vertices within as little as one hour. On the other hand, interior point methods fail to solve instances from n=300 due to memory requirements. We also design heuristics to generate upper bounds from the SDP solutions, giving us tighter upper bounds than other methods proposed in the literature with low computational expense.