On the Embed and Project Algorithm for the graph bandwidth problem

Povh, Janez (avtor)

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.

• Jezik: Angleški jezik
• Ključne besede: graph bandwidth problem, semidefinite programming, combinatorial optimization, Embed and Project Algorithm, approximation algorithm
• Vrsta gradiva: Članek v reviji
• Tipologija: 1.01 - Izvirni znanstveni članek
• Organizacija: FS - Fakulteta za strojništvo
• Status publikacije: Objavljeno
• Različica publikacije: Objavljena publikacija
• Leto izida: 2021
• Št. strani: 15 str.
• Številčenje: Vol. 9, iss. 17, art. 2030
• PID: 20.500.12556/RUL-129286
• UDK: 519.178
• ISSN pri članku: 2227-7390
• DOI: 10.3390/math9172030
• COBISS.SI-ID: 74852611
• Datum objave v RUL: 01.09.2021

Gradivo je del revije

• Naslov: Mathematics
• Skrajšan naslov: Mathematics
• Založnik: MDPI AG
• ISSN: 2227-7390
• COBISS.SI-ID: 523267865

Licence

• Licenca: CC BY 4.0, Creative Commons Priznanje avtorstva 4.0 Mednarodna
• Povezava: http://creativecommons.org/licenses/by/4.0/deed.sl
• Opis: To je standardna licenca Creative Commons, ki daje uporabnikom največ možnosti za nadaljnjo uporabo dela, pri čemer morajo navesti avtorja.
• Začetek licenciranja: 01.09.2021

Sekundarni jezik

• Jezik: Slovenski jezik
• Ključne besede: problem pasovne širine grafa, semidefinitno programiranje, kombinatorična optimizacija, algoritem vložitve in projekcije, aproksimacijski algoritem