izpis_h1_title_alt

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

.pdfPDF - Predstavitvena datoteka, prenos (370,28 KB)
MD5: 4785D9B145E56C7CD95B6C314D6BF18B
URLURL - Izvorni URL, za dostop obiščite https://www.mdpi.com/2227-7390/9/17/2030 Povezava se odpre v novem oknu

Izvleček
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.

Jezik:Angleški jezik
Ključne besede:graph bandwidth problem, semidefinite programming, combinatorial optimization, Embed and Project Algorithm, approximation algorithm
Vrsta gradiva:Članek v reviji (dk_c)
Tipologija:1.01 - Izvirni znanstveni članek
Organizacija:FS - Fakulteta za strojništvo
Leto izida:2021
Status objave pri reviji:Objavljeno
Verzija članka:Založnikova različica članka
Št. strani:15 str.
Številčenje:Vol. 9, iss. 17, art. 2030
PID:20.500.12556/RUL-129286 Povezava se odpre v novem oknu
UDK:519.178
ISSN pri članku:2227-7390
DOI:10.3390/math9172030 Povezava se odpre v novem oknu
COBISS.SI-ID:74852611 Povezava se odpre v novem oknu
Datum objave v RUL:01.09.2021
Število ogledov:373
Število prenosov:80
Metapodatki:XML RDF-CHPDL DC-XML DC-RDF
:
Objavi na:AddThis
AddThis uporablja piškotke, za katere potrebujemo vaše privoljenje.
Uredi privoljenje...

Gradivo je del revije

Naslov:Mathematics
Skrajšan naslov:Mathematics
Založnik:MDPI
ISSN:2227-7390
COBISS.SI-ID:523267865 Povezava se odpre v novem oknu

Licence

Licenca:CC BY 4.0, Creative Commons Priznanje avtorstva 4.0 Mednarodna
Povezava:http://creativecommons.org/licenses/by/4.0/deed.sl
Opis:To je standardna licenca Creative Commons, ki daje uporabnikom največ možnosti za nadaljnjo uporabo dela, pri čemer morajo navesti avtorja.
Začetek licenciranja:01.09.2021

Sekundarni jezik

Jezik:Slovenski jezik
Ključne besede:problem pasovne širine grafa, semidefinitno programiranje, kombinatorična optimizacija, algoritem vložitve in projekcije, aproksimacijski algoritem

Gradivo je financirano iz projekta

Financer:ARRS - Agencija za raziskovalno dejavnost Republike Slovenije (ARRS)
Številka projekta:N1-0071
Naslov:Razširitev algoritmov prvega in drugega reda za izbrane razrede optimizacijskih problemov s ciljem rešiti računsko zahtevne industrijske probleme

Financer:ARRS - Agencija za raziskovalno dejavnost Republike Slovenije (ARRS)
Številka projekta:J1-2453
Naslov:Matrično konveksne množice in realna algebraična geometrija

Financer:ARRS - Agencija za raziskovalno dejavnost Republike Slovenije (ARRS)
Številka projekta:J2-2512
Naslov:Stohastični modeli za logistiko proizvodnih procesov

Financer:ARRS - Agencija za raziskovalno dejavnost Republike Slovenije (ARRS)
Številka projekta:J1-1691
Naslov:Weissova domneva in posplošitve

Financer:ARRS - Agencija za raziskovalno dejavnost Republike Slovenije (ARRS)
Številka projekta:P2-0162
Naslov:Tranzientni dvofazni tokovi

Podobna dela

Podobna dela v RUL:
Podobna dela v drugih slovenskih zbirkah:

Nazaj