20.500.12556/RUL-129286
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.
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
true
false
true
Angleški jezik
Slovenski jezik
Članek v reviji
2021-09-01 13:25:19
2021-09-01 13:25:23
2022-09-08 04:07:45
0000-00-00 00:00:00
2021
0
0
15 str.
iss. 17, art. 2030
Vol. 9
Sep. 2021
0000-00-00
Zaloznikova
Objavljeno
NiDoloceno
0000-00-00
0000-00-00
0000-00-00
519.178
2227-7390
10.3390/math9172030
74852611
RAZ_Povh_Janez_2021.pdf
RAZ_Povh_Janez_2021.pdf
1
4785D9B145E56C7CD95B6C314D6BF18B
88adc78fdc0c9e716dc8f5e2622b19dafe5d0af28b142aec34b865365bbd4b66
f1032b1f-0b17-11ec-a523-00155dcfd717
https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=146262
https://www.mdpi.com/2227-7390/9/17/2030
1
1100dcbb-0b17-11ec-a523-00155dcfd717
https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=146261
Fakulteta za strojništvo
0
0
0