On the <i>Embed and Project</i> 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 <i>Embed and Project A...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2021-08-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/9/17/2030 |
| _version_ | 1797521082110967808 |
|---|---|
| author | Janez Povh |
| author_facet | Janez Povh |
| author_sort | Janez Povh |
| collection | DOAJ |
| description | 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 <i>Embed and Project Algorithm</i> (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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>n</mi><mo>≤</mo><mn>1000</mn></mrow></semantics></math></inline-formula>. |
| first_indexed | 2024-03-10T08:07:36Z |
| format | Article |
| id | doaj.art-2d58b4d5780742a0a1ac28838d491956 |
| institution | Directory Open Access Journal |
| issn | 2227-7390 |
| language | English |
| last_indexed | 2024-03-10T08:07:36Z |
| publishDate | 2021-08-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj.art-2d58b4d5780742a0a1ac28838d4919562023-11-22T10:56:52ZengMDPI AGMathematics2227-73902021-08-01917203010.3390/math9172030On the <i>Embed and Project</i> Algorithm for the Graph Bandwidth ProblemJanez Povh0Faculty of Mechanical Engineering, University of Ljubljana, Aškerčeva ulica 6, SI-1000 Ljubljana, SloveniaThe 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 <i>Embed and Project Algorithm</i> (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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>n</mi><mo>≤</mo><mn>1000</mn></mrow></semantics></math></inline-formula>.https://www.mdpi.com/2227-7390/9/17/2030graph bandwidth problemsemidefinite programmingcombinatorial optimizationembed and project algorithmapproximation algorithm |
| spellingShingle | Janez Povh On the <i>Embed and Project</i> Algorithm for the Graph Bandwidth Problem Mathematics graph bandwidth problem semidefinite programming combinatorial optimization embed and project algorithm approximation algorithm |
| title | On the <i>Embed and Project</i> Algorithm for the Graph Bandwidth Problem |
| title_full | On the <i>Embed and Project</i> Algorithm for the Graph Bandwidth Problem |
| title_fullStr | On the <i>Embed and Project</i> Algorithm for the Graph Bandwidth Problem |
| title_full_unstemmed | On the <i>Embed and Project</i> Algorithm for the Graph Bandwidth Problem |
| title_short | On the <i>Embed and Project</i> Algorithm for the Graph Bandwidth Problem |
| title_sort | on the i embed and project i algorithm for the graph bandwidth problem |
| topic | graph bandwidth problem semidefinite programming combinatorial optimization embed and project algorithm approximation algorithm |
| url | https://www.mdpi.com/2227-7390/9/17/2030 |
| work_keys_str_mv | AT janezpovh ontheiembedandprojectialgorithmforthegraphbandwidthproblem |