izpis_h1_title_alt

On the embed and project algorithm for the graph bandwidth problem
Povh, Janez (Author)

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

Abstract
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-planelike 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 (less than or equal to) 1000.

Language:English
Keywords:graph bandwidth problem, semidefinite programming, combinatorial optimization, embed and project algorithm, approximation algorithm
Work type:Article (dk_c)
Tipology:1.01 - Original Scientific Article
Organization:FS - Faculty of Mechanical Engineering
Year:2021
Number of pages:Str. 1-15
Numbering:Vol. 9, iss. 17, art. 2030
UDC:519.178
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
Views:144
Downloads:40
Metadata:XML RDF-CHPDL DC-XML DC-RDF
 
Average score:(0 votes)
Your score:Voting is allowed only to logged in users.
:
Share:AddThis
AddThis uses cookies that require your consent. Edit consent...

Record is a part of a journal

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

Document is financed by a project

Funder:ARRS - Agencija za raziskovalno dejavnost Republike Slovenije (ARRS)
Project no.: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 - Agencija za raziskovalno dejavnost Republike Slovenije (ARRS)
Project no.:J1-2453
Name:Matrično konveksne množice in realna algebraična geometrija

Funder:ARRS - Agencija za raziskovalno dejavnost Republike Slovenije (ARRS)
Project no.:J2-2512
Name:Stohastični modeli za logistiko proizvodnih procesov

Funder:ARRS - Agencija za raziskovalno dejavnost Republike Slovenije (ARRS)
Project no.:J1-1691
Name:Weissova domneva in posplošitve

Funder:ARRS - Agencija za raziskovalno dejavnost Republike Slovenije (ARRS)
Project no.:P2-0162
Name:Tranzientni dvofazni tokovi

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:24.08.2021

Secondary language

Language:Slovenian
Abstract:
Problem pasovne širine grafa, kjer iščemo tako oštevilčenje točk grafa, ki daje minimalno razliko med števili na koncih povezav, je klasičen NP-težak problem, ki je v zadnjih desetletjih pritegnil veliko pozornosti. V tem prispevku se osredotočamo na tako imenovani Vloži in projiciraj algoritem (EPA), ki so ga predstavili Blum et al. leta 2000. Osrednja naloga tega algoritma je, da reši semidefinitne program z eksponentno veliko linearnimi omejitvami. V članku najprej predstavimo nekaj novih teoretičnih lastnosti tega semidefinitnega programa, nato pa nov algoritem, ki temelji na metodi prereznih ravnin. Ta algoritem deluje zelo učinkovito v kombinaciji z metodami notranje točke in z metodo svežnjev. Obsežni številčni rezultati dokazujejo, da ta algoritem daje v praksi zelo dobro oštevilčenje za grafe z n <= 1000.

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

Similar documents

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

Comments

Leave comment

You have to log in to leave a comment.

Comments (0)
0 - 0 / 0
 
There are no comments!

Back