On the Embed and Project Algorithm for the graph bandwidth problem
ID Povh, Janez (Author)

.pdfPDF - Presentation file, Download (370,28 KB)
MD5: 4785D9B145E56C7CD95B6C314D6BF18B
URLURL - Source URL, Visit https://www.mdpi.com/2227-7390/9/17/2030 This link opens in a new window

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.

Keywords:graph bandwidth problem, semidefinite programming, combinatorial optimization, Embed and Project Algorithm, approximation algorithm
Work type:Article
Typology:1.01 - Original Scientific Article
Organization:FS - Faculty of Mechanical Engineering
Publication status:Published
Publication version:Version of Record
Number of pages:15 str.
Numbering:Vol. 9, iss. 17, art. 2030
PID:20.500.12556/RUL-129286 This link opens in a new window
ISSN on article:2227-7390
DOI:10.3390/math9172030 This link opens in a new window
COBISS.SI-ID:74852611 This link opens in a new window
Publication date in RUL:01.09.2021
Copy citation
Share:Bookmark and Share

Record is a part of a journal

Shortened title:Mathematics
Publisher:MDPI AG
COBISS.SI-ID:523267865 This link opens in a new window


License:CC BY 4.0, Creative Commons Attribution 4.0 International
Description:This is the standard Creative Commons license that gives others maximum freedom to do what they want with the work as long as they credit the author.
Licensing start date:01.09.2021

Secondary language

Keywords:problem pasovne širine grafa, semidefinitno programiranje, kombinatorična optimizacija, algoritem vložitve in projekcije, aproksimacijski algoritem


Funder:ARRS - Slovenian Research Agency
Project number:N1-0071
Name:Razširitev algoritmov prvega in drugega reda za izbrane razrede optimizacijskih problemov s ciljem rešiti računsko zahtevne industrijske probleme

Funder:ARRS - Slovenian Research Agency
Project number:J1-2453
Name:Matrično konveksne množice in realna algebraična geometrija

Funder:ARRS - Slovenian Research Agency
Project number:J2-2512
Name:Stohastični modeli za logistiko proizvodnih procesov

Funder:ARRS - Slovenian Research Agency
Project number:J1-1691
Name:Weissova domneva in posplošitve

Funder:ARRS - Slovenian Research Agency
Project number:P2-0162
Name:Tranzientni dvofazni tokovi

Similar documents

Similar works from RUL:
Similar works from other Slovenian collections: