Gráfelméleti problémák adatközpontokban
| Témavezető: | Tapolcai János |
| BME VIK TMIT | |
| email: | tapolcai@tmit.bme.hu |
Témavezetők
- Bérczi-Kovács Erika Renáta (ELTE, Operációkutatási Tanszék)
Projekt leírás
A felhő (Cloud) alkalmazások hátterében nagy adatközpontok vannak. Egy adatközpontban számítógépek tízezreit üzemeltetnek, amelyeket egy speciális topológiájú hálózatban kapcsolják. A főbb felhő szolgáltatásokat biztosító cégek (mint például Goolge, Facebook, Amazon, Alibaba stb.) más-más hálózatai topológiát favorizálnak az adatközpontjaikban. Ezek jellemzően kis fokszámú, kis átmérőjű hálózatok, amelyek a lehetőségekhez képest sokszorosan összefüggőek, mint például az ú.n. félbehajtott clos gráfok. Az algoritmikus problémák pedig elég sajátosak és gyakran NP-nehéz feladatok, mint diszjunkt fák pakolása mélységkorlátokkal. A hallgató feladata előszőr a adatközpont topológia gráfok konstruktív karakterizációja lenne. Vizsgálnánk, hogy léteznek-e olyan karakterizációk, amely segítségével később már könnyen megoldhatóak az általános gráfokra NP-nehéz optimalizálási feladatok.
Előfeltételek
- Angol nyelvtudás szükséges.
- A feladat lehet programozói, de nem feltétlen.
Hivatkozások
[https://arxiv.org/abs/1409.0034](https://arxiv.org/abs/1409.0034(