Bejelentkezés
 Fórum
 
 
Témakiírás
 
Vinkó Tamás
Lineáris algebra alapú hatékony algoritmusok hálózattudományban felmerülő optimalizálási feladatok megoldására

TÉMAKIÍRÁS

Intézmény: Szegedi Tudományegyetem
informatikai tudományok
Informatika Doktori Iskola

témavezető: Vinkó Tamás
helyszín (magyar oldal): SZTE
helyszín rövidítés: SZTE


A kutatási téma leírása:

A gráfok kanonikus reprezentációja (mint csúcsok és élek halmaza) és a szomszédsági mátrixuk közötti jól ismert dualitás nagyban kihasználható a hálózattudományban [2] és az ott értelmezett, elsősorban egészértékű lineáris programozási (ILP) feladatok megoldásában [1]. Az elmúlt években egyre nagyobb figyelmet kaptak a hálózattudományban és gráfelméletben felmerülő problémákra mátrix lineáris algebra nyelvén adott megoldások [6]. Jelen témakör ehhez a trendhez kapcsolódik. A kutatási feladat célja, hogy gráfelméleti eredetű optimalizálási problémákra, egyrészt a lineáris algebra számítástudományi szempontból is érdekes eszközeit (úgy mint ritka mátrixok és azok reprezentációi, mátrix-faktorizációs eljárások, különböző félgyűrű struktúrák használata, eliminációs módszerek, stb) [3,4,7,8], másrészt az ILP feladatokhoz kapcsolódó modern eljárásokat (egzakt megoldási módszerek, oszlopgenerálás, dekompozíciók, hálózati algoritmusok, matroidok, folyam hálózatok, stb) [1,5,9,10] felhasználva hatékonyan megvalósítható algoritmikus megoldásokat adjunk.

[1] Alderson, David L. OR FORUM - Catching the “network science” bug: Insight and opportunity for the operations researcher. Operations Research 56 (2008): 1047-1065.

[2] Barabási, Albert-László. Network science. Cambridge University Press, 2016.

[3] Buluc, Aydin, and John R. Gilbert. Linear algebraic primitives for parallel computing on large graphs. University of California, Santa Barbara, 2010.

[4] Horn, William, et al. Graph Programming Interface (GPI): A linear algebra programming model for large scale graph computations. International Journal of Parallel Programming 46 (2018): 412-440.

[5] Jünger, Michael, et al., eds. 50 Years of integer programming 1958-2008: From the early years to the state-of-the-art. Springer Science & Business Media, 2009.

[6] J Kepner and J Gilbert, eds. Graph algorithms in the language of linear algebra, SIAM, 2011.

[7] Kepner, Jeremy, et al. Mathematical foundations of the GraphBLAS. 2016 IEEE High Performance Extreme Computing Conference (HPEC) 2016.

[8] Kepner, Jeremy, et al. Graphs, matrices, and the GraphBLAS: Seven good reasons. Procedia Computer Science 51 (2015): 2453-2462.

[9] Sierksma, Gerard, and Yori Zwols. Linear and integer optimization: theory and practice. Chapman and Hall/CRC, 2015.

[10] Shi, Guodong, Brian D Anderson, and Uwe Helmke. Network flows that solve linear equations. IEEE Transactions on Automatic Control 62 (2016): 2659-2674.

ajánlott nyelvtudás (magyar oldal): angol
felvehető hallgatók száma: 1

Jelentkezési határidő: 2020-05-31

 
Minden jog fenntartva © 2007, Országos Doktori Tanács - a doktori adatbázis nyilvántartási száma az adatvédelmi biztosnál: 02003/0001. Program verzió: 2.2358 ( 2017. X. 31. )