Thesis supervisor: Tamás Vinkó
Location of studies (in Hungarian): SZTE Abbreviation of location of studies: SZTE
Description of the research topic:
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.
Recommended language skills (in Hungarian): angol Number of students who can be accepted: 1
Deadline for application: 2022-03-15
2024. IV. 17. ODT ülés Az ODT következő ülésére 2024. június 14-én, pénteken 10.00 órakor kerül sor a Semmelweis Egyetem Szenátusi termében (Bp. Üllői út 26. I. emelet).
Login
