On the Embed and Project Algorithm for the graph bandwidth problem

Povh, Janez (author)

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.

• Language: English
• 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
• Year: 2021
• Number of pages: 15 str.
• Numbering: Vol. 9, iss. 17, art. 2030
• PID: 20.500.12556/RUL-129286
• UDC: 519.178
• ISSN on article: 2227-7390
• DOI: 10.3390/math9172030
• COBISS.SI-ID: 74852611
• Publication date in RUL: 01.09.2021

Record is a part of a journal

• Title: Mathematics
• Shortened title: Mathematics
• Publisher: MDPI AG
• ISSN: 2227-7390
• COBISS.SI-ID: 523267865

Licences

• License: CC BY 4.0, Creative Commons Attribution 4.0 International
• Link: http://creativecommons.org/licenses/by/4.0/
• 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

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