Janez Povh (Avtor)

Povzetek

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.

Ključne besede

graph bandwidth problem;semidefinite programming;combinatorial optimization;embed and project algorithm;approximation algorithm;

Podatki

Jezik: Angleški jezik
Leto izida:
Tipologija: 1.01 - Izvirni znanstveni članek
Organizacija: UL FS - Fakulteta za strojništvo
UDK: 519.178
COBISS: 74852611 Povezava se bo odprla v novem oknu
ISSN: 2227-7390
Št. ogledov: 413
Št. prenosov: 88
Ocena: 0 (0 glasov)
Metapodatki: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Ostali podatki

Sekundarni jezik: Slovenski jezik
Sekundarni povzetek: 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.
Sekundarne ključne besede: problem pasovne širine grafa;semidefinitno programiranje;kombinatorična optimizacija;algoritem vložitve in projekcije;aproksimacijski algoritem;
Vrsta dela (COBISS): Članek v reviji
Strani: str. 1-15
Letnik: ǂVol. ǂ9
Zvezek: ǂiss. ǂ17
Čas izdaje: Sep. 2021
DOI: 10.3390/math9172030
ID: 13303765