On the Embed and Project Algorithm for the graph bandwidth problem
The graph bandwidth problem, where one looks for a labeling of graph vertices that gives the minimum difference between the labels over all edges, is a classical NP-hard problem that has drawn a lot of attention in recent decades. In this paper, we focus on the so-called Embed and Project Algorithm (EPA) introduced by Blum et al. in 2000, which in the main part has to solve a semidefinite programming relaxation with exponentially many linear constraints. We present several theoretical properties of this special semidefinite programming problem (SDP) and a cutting-plane-like algorithm to solve it, which works very efficiently in combination with interior-point methods or with the bundle method. Extensive numerical results demonstrate that this algorithm, which has only been studied theoretically so far, in practice gives very good labeling for graphs with n ≤ 1000.
2021
2021-09-01 13:25:19
1033
graph bandwidth problem, semidefinite programming, combinatorial optimization, Embed and Project Algorithm, approximation algorithm
problem pasovne širine grafa, semidefinitno programiranje, kombinatorična optimizacija, algoritem vložitve in projekcije, aproksimacijski algoritem
dk_c
Janez
Povh
70
UDK
4
519.178
ISSN pri članku
9
2227-7390
DOI
15
10.3390/math9172030
COBISS_ID
3
74852611
RAZ_Povh_Janez_2021.pdf
379170
Predstavitvena datoteka
2021-09-01 13:31:40
0
Izvorni URL
2021-09-01 13:25:24