A kutatólaboratórium vezetője: Dr. Tuza Zsolt, egyetemi tanár
A kutatólaboratórium tagjai:
- Dr. Bujtás Csilla, egyetemi docens (CV)
- Dr. Dósa György, egyetemi tanár (CV)
- Dr. Tuza Zsolt, egyetemi tanár (CV)
A kutatólaboratórium tevékenysége:
A kutatólaboratórium számos irányban folytat elméleti kutatásokat. Egyik fő területként a diszkrét matematikai modellek – elsősorban gráfok (hálózatok) és hipergráfok – strukturális és extremális tulajdonságait, valamint és ezzel összefüggésben a kombinatorikus problémák algoritmikus (idő-) komplexitását vizsgálják. Másik fő irányként diszkrét optimalizálási feladatok (például különféle ládapakolási feladatok) approximálhatóságát, valamint offline és online ütemezések versenyképességi arányát tanulmányozzák.
Kutatási eredmények:
A gráfszínezés klasszikus és listás változataira vonatkozó kutatások mellett olyan színezéseket is tanulmányoznak, ahol a színek száma valamilyen lokális feltétellel felülről korlátozott. Strukturális, komplexitási és a felhasználható színek számára vonatkozó eredmények mellett a gráfok elvágó csúcs- és élhalmazaival való szoros kapcsolat került kimutatásra.
Bevezették a hipergráfok színezéseinek, halmazrendszerek partícióinak általános modelljét, és egy cikksorozatban publikálták a rájuk vonatkozó elmélet részleteit. Eközben egy speciális részosztályra (C-színezés) vonatkozóan több, hosszú ideje nyitott problémát oldottak meg. Ezek közül a legrégebbi kérdés az n-elemű halmaz minden k-osztályú partícióját lefogó k-elemű transzverzális-rendszer minimális mérete, amelyre aszimptotikusan pontos megoldást találtak és egy korábbi ezzel kapcsolatos sejtést cáfoltak.
Több megközelítésben tanulmányozták a gráfok és halmazrendszerek felbonthatóságát. Komplexitási eredményeket értek el csúcspartíciók létezésére vonatkozóan, fokszámfeltételek mellett. Új módszereket dolgoztak ki teljes uniform hipergráfok körfelbontásaira.
Két évtizeden át nyitott probléma megoldásaként karakterizálták az olyan hálózatok szerkezetét, amelyeknek minden összefüggő részében létezik egy előírt tulajdonságú domináló részhálózat (vagyis amelyből a részhálózat összes többi eleme is közvetlenül elérhető). Adott minimális fokszámot feltételezve a csúcsok számának függvényében felső korlátokat bizonyítottak a gráfok dominálási számára. Ezek a jelenleg ismert legjobb felső becslések az 5 és 50 közötti minimális fokszám esetére, továbbá a bizonyítás algoritmikus eljárást is ad a korlátot meg nem haladó méretű domináló halmazok konstruálására. Hasonló eredmények születtek a 2-dominálásra vonatkozóan.
A korábban ismerteknél jobb versenyképességi arányt biztosító online ütemezési algoritmusokat konstruáltak, továbbá bebizonyították, hogy több feladatra is az alkalmasan szervezett félig online (részleges információt felhasználó) algoritmusok garantáltan hatékonyabbak, mint ami a teljesen online esetben bármilyen módszerrel elérhető. Négy évtizede nyitott probléma lezárásaként meghatározták a „First Fit Decreasing” és a „First Fit” algoritmusok pontos abszolút approximációs arányát. Új ütemezési és ládapakolási modelleket vezettek be és bizonyították azok approximációs tulajdonságait.
A jelenlegi legjobb alsó-, illetve a jelenlegi legjobb felső becsléseket határozták meg az online ládapakolási feladatra.
Bevezették az úgynevezett Board Packing téglalap-pakolási feladatot, és vizsgálták annak megoldhatóságát különféle algoritmusokkal. Más négyzetpakolási és feladatokkal is foglalkoznak.
Megadták az első tisztán kombinatorikus bizonyítását annak, hogy az 1,2,…,24 méretű négyzetekkel nem lehet lefedni a 70*70-es nagy négyzetet. A feladat nagyjából 100 éves múltra tekint vissza, ez az első tisztán elméleti bizonyítás, amely nem használ fel számítógépes segítséget.
A „kombinatorikus batch kód” olyan halmazrendszer, amellyel adott mennyiségű információ adott számú szerveren történő tárolása és kiolvasása modellezhető. A kikötések az egyszerre dekódolandó adatok maximális számára és az adatvédelemmel kapcsolatos titkosításra vonatkoznak. A feltételeknek eleget tevő halmazrendszer minimális összméretét határozták meg a paraméterek különböző tartományain, továbbá a kombinatorika ehhez kapcsolódó klasszikus problémaköreire (Hall feltétel, Turán-probléma) vonatkozóan is új eredményekre jutottak.
Együttműködések:
Munkánkat széleskörű nemzetközi és hazai együttműködésben végezzük, Az idők folyamán 300-nál több kollégával folytattunk olyan közös kutatásokat, amelyekről nemzetközi fórumokon jelentettünk meg tudományos közleményeket. A fent idézett eredményekben is számos külső társszerző működött közre, név szerint Bacsó Gábor, Balogh János, Cristina Bazgan, Békési József, Leah Epstein, Xin Han, Mike Henning, Lars Magnus Hvattum, Jaskó Szilárd, Hans Kellerer, Keszler Anita, Sandi Klavžar, Asaf Levin, E. Sampathkumar, Jiri Sgall, M. Grazia Speranza, Daniel Vanderpooten.
Pályázatok, konferenciák:
A kutatócsoport tagjai különféle pályázatokat nyertek az elmúlt években (pl. Szlovén-Magyar OTKA), és különféle projektekben vállaltak szerepet, valamint több sikeres konferenciát szerveztek (Discrete Mathematics and Applications Conference, 2018, Veszprém Optimization Workshop 2019, Optimization and Algorithms - Semi online 25, 2023).
Publikációk:
A kutatócsoport tagjainak az elmúlt években egyebek mellett közel 100 impakt faktoros publikációja született a DBLP adatbázis adatai szerint. Az alábbiakban megadunk 10 fontosabb publikációt az elmúlt évekből.
- Gyula Abraham, György Dósa, Lars Magnus Hvattum, Tomas Olaj, Zsolt Tuza: The board packing problem. Eur. J. Oper. Res. 308(3): 1056-1073 (2023)
- József Balogh, Gyula O.H. Katona, Zsolt Tuza, William Linz: The domination number of the graph defined by two levels of the n-cube, II. European J. Combin. 91: 103201 (2021)
- János Balogh, József Békési, György Dósa, Leah Epstein, Asaf Levin: A new and improved algorithm for online bin packing. ESA 2018: 5:1-5:14
- József Békési, György Dósa, Gábor Galambos: A First Fit type algorithm for the coupled task scheduling problem with unit execution time and two exact delays. Eur. J. Oper. Res. 297(3): 844-852 (2022)
- Csilla Bujtás: Domination number of graphs with minimum degree five. Discuss. Math. Graph Theory 41: 763-777 (2021)
- Csilla Bujtás, Mario Gionfriddo, Elena Guardo, Lorenzo Milazzo, Salvatore Milici, Zsolt Tuza: Complex uniformly resolvable decompositions of Kv. Ars Math. Contemp. 21(1): #P1.02 (2021)
- Csilla Bujtás, Günter Rote, Zsolt Tuza: Optimal strategies in fractional games: vertex cover and domination. Ars Math. Contemp. (2024)
- Sylwia Cichacz, Zsolt Tuza: Realization of digraphs in Abelian groups and its consequences. J. Graph Theory 100(2): 331-345 (2022)
- Anita Keszler, Zsolt Tuza: Spectrum of 3-uniform 6-and 9-cycle systems over Kv(3)−I. Discrete Math. 347: 113782 (2024)
- Balázs Patkós, Zsolt Tuza Máté Vizer: Vector sum-intersection theorems. Discrete Math. 346: 113506 (2023)
Problémák, amiket mostanában oldottunk meg:
A kutatólaboratórium vezetőjének bemutatása:
Tuza Zsolt szerteágazó tudományos kutatásokat folytat, 470 angol nyelvű publikáció szerzője. Fő kutatási területei a Kutatólaboratórium profiljába illeszkednek. Emellett számos munkája foglalkozik kombinatorikus módszerek alkalmazásaival más tudományterületeken.
A kutatócsoport két tagja munka közben
