Department of Operations Research (Eötvös Loránd University)
Participants
Bérczi, Kristóf Bérczi-Kovács, Erika Renáta Bernáth, Attila Fleiner, Tamás Herskovics, Dávid Jankó, Zsuzsanna Jordán, Tibor Jüttner, Alpár Kaszanitzky, Viktória Eszter Király, Csaba Király, Tamás Király, Zoltán Korom, Mátyás Pap, Gyula
Starting date
2013-09-01
Closing date
2018-08-31
Funding (in million HUF)
71.256
FTE (full time equivalent)
31.28
state
closed project
Summary in Hungarian
A kutatás összefoglalója, célkitűzései szakemberek számára Itt írja le a kutatás fő célkitűzéseit a témában jártas szakember számára. A diszkrét optimalizálás az alkalmazott matematika egyik gyorsan fejlődő ága olyan problémák algoritmikus kezelésére, melyeknél a feladat egy nagy diszkrét struktúrában történő optimumkeresés. Közismert például a legrövidebb út keresésének problémája hálózatokban vagy munkák elosztásánál az optimális hozzárendelés megtalálása. Az új, komplex problémák új algoritmusok kifejlesztését igénylik, és ehhez a háttérben húzódó struktúrák megértésére és feltárására van szükség.
Kutatásunk célja olyan új algoritmikus eszközök fejlesztése, amik hatékonyan használhatóak a diszkrét matematikán kívüli területeken is, mint például a bioinformatikában, a közgazdasági játékelméletben és a mérnöki tudományokban. A pályázatban résztvevő kutatók eddig is folytattak kutatásokat az említett irányban és alapvető eredményeket értek el merevségelméletben, játékelméletben és telekommunikációban. Az elméleti vizsgálatokat elősegíti és a gyakorlati kicsatolását biztosítja a kutatócsoport által fejlesztett LEMON programozási csomag.
A kutatás öt fő területre fókuszál: hálózati optimalizálás, fák és fenyők, merev szerkezetek, változós mátrixok alkalmazásai és stabil párosítások. Mindnek fontos alkalmazásai vannak a matematikán kívül: a változós mátrixokat és a merevségelméletet a molekulák szerkezetének vizsgálatánál használják, a stabil párosítások és általánosításaik alapvető eszközök a közgazdaságtanban, a fákkal és hálózati optimalizálással kapcsolatos eredmények pedig a kommunikációs hálózatok tervezésénél. A projekt célja olyan algoritmikus eredmények elérése, melyek komoly hatással lehetnek az említett területekre.
Mi a kutatás alapkérdése? Ebben a részben írja le röviden, hogy mi a kutatás segítségével megválaszolni kívánt probléma, mi a kutatás kiinduló hipotézise, milyen kérdéseket válaszolnak meg a kísérletek. A diszkrét optimalizálás az alkalmazott matematika egyik gyorsan fejlődő ága. Ez a terület olyan problémákat közelít meg algoritmikusan, melyeknél a feladat egy nagy diszkrét struktúrában történő optimumkeresés. Ilyenek például legrövidebb út keresése hálózatokban vagy munkák elosztásánál az optimális hozzárendelés megtalálása. Az ilyen típusú feladatok megoldásához új algoritmusok kifejlesztésére valamint a háttérben húzódó struktúrák megértésére van szükség.
Kutatásunk célja olyan új algoritmikus eszközök fejlesztése, melyek hatékonyan használhatóak a diszkrét matematikán kívüli területeken is, mint például a bioinformatikában, a közgazdasági játékelméletben és a mérnöki tudományokban. A kutatás az alábbi öt terület főbb nyitott problémáira fog fókuszálni: hálózati optimalizálás, fák és fenyők, merev szerkezetek, változós mátrixok alkalmazásai és stabil párosítások. Mind az öt téma szorosan kapcsolódik a matroidelmélethez és a szubmoduláris optimalizáláshoz, valamint mindnek fontos, matematikán kívüli alkalmazásai is vannak. Az alapvető nyitott kérdések között szerepel például a merevségi mátrixok rangjának kiszámítása, változós mátrixok rangmeghatározásának bonyolultsága valamint közelítő algoritmus keresése a Steiner-fa pakolásokra.
Mi a kutatás jelentősége? Röviden írja le, milyen új perspektívát nyitnak az alapkutatásban az elért eredmények, milyen társadalmi hasznosíthatóságnak teremtik meg a tudományos alapját. Mutassa be, hogy a megpályázott kutatási területen lévő hazai és a nemzetközi versenytársaihoz képest melyek az egyediségei és erősségei a pályázatának! Kutatásunk célja olyan új algoritmikus eszközök fejlesztése, melyek hatékonyan használhatóak a diszkrét matematikán kívüli területeken is, mint például a bioinformatikában, a közgazdasági játékelméletben és a mérnöki tudományokban. A projekt magában foglalja a kutatócsoport által fejlesztett új szoftverösszetevők fejlesztését is.
A kutatás az alábbi öt területre fog fókuszálni: hálózati optimalizálás, fák és fenyők, merev szerkezetek, változós mátrixok alkalmazásai és stabil párosítások. Mind az öt témának fontos alkalmazásai vannak a matematikán kívül. A változós mátrixok és a merevségelméletet a molekulák szerkezetének vizsgálatánál és hálózati lokalizációs problémák megoldásakor használhatóak. A stabil párosítások és általánosításaik alapvető fogalmakká váltak a közgazdaságtanban (mint azt a legutóbbi közgazdasági Nobel-díj is jelzi). A fákkal, fenyőkkel és hálózati optimalizálással kapcsolatos eredmények központi eszközök vezetékes és vezeték nélküli telekommunikációs hálózatok tervezésénél. A projekt célja az említett témák mögötti matematikai struktúrákba való mélyebb betekintés és ennek alkalmazása olyan algoritmikus eredmények elérésére, melyek lényeges hatással lehetnek ezen területekre.
A kutatás összefoglalója, célkitűzései laikusok számára Ebben a fejezetben írja le a kutatás fő célkitűzéseit alapműveltséggel rendelkező laikusok számára. Ez az összefoglaló a döntéshozók, a média, illetve az érdeklődők tájékoztatása szempontjából különösen fontos az NKFI Hivatal számára. A diszkrét optimalizálás az alkalmazott matematika egyik gyorsan fejlődő ága. Ez a terület olyan problémákat közelít meg algoritmikusan, melyeknél a feladat egy nagy diszkrét struktúrában történő optimumkeresés. Ilyenek például legrövidebb út keresése hálózatokban vagy munkák elosztásánál az optimális hozzárendelés megtalálása. Az ilyen típusú feladatok megoldásához új algoritmusok kifejlesztésére valamint a háttérben húzódó struktúrák megértésére van szükség.
Kutatásunk célja olyan új algoritmikus eszközök fejlesztése, melyek hatékonyan használhatóak a diszkrét matematikán kívüli területeken is, mint például a bioinformatikában, a közgazdasági játékelméletben és a mérnöki tudományokban. A pályázatban résztvevő kutatók eddig is folytattak kutatásokat az említett irányban és alapvető eredményeket értek el merevségelméletben, játékelméletben és telekommunikációban. Ezen kezdeményezések támogatása az adott témák diszkrét optimalizálási szemszögből való kutatásán túl elősegíti - a kutatócsoport által fejlesztett LEMON programozási csomag keretében - új szoftverösszetevők fejlesztését is.
A kutatás a diszkrét optimalizálás öt alapvető problémájára fog fókuszálni, melyek közül mindnek van fontos, a korábbiakban már említett, matematikán kívüli alkalmazása is. A projekt célja olyan algoritmikus eredmények elérése, melyek nagy hatással lehetnek ezen területek fejlődésére.
Summary
Summary of the research and its aims for experts Describe the major aims of the research for experts. Discrete Optimization is a fast-growing branch of applicable mathematics, dealing with algorithmic approaches to finding optimal objects in large discrete structures, such as shortest paths in networks, or best assignments in a crew assignment problem. The subject requires the development of efficient algorithms as well as the mathematical understanding of the underlying structures.
Our project aims at developing new algorithmic tools that can be efficiently used in fields beyond discrete mathematics, such as bioinformatics, economic game theory, and engineering. This sort of expansion into new territories has already started, with members of the project already achieving fundamental results in rigidity theory, game theory and telecommunications. Amplifying upon this initiative will not only involve investigations from a discrete optimization point of view but will also lead to the development of software components by building upon the LEMON software library developed by the research group.
The research in the project will focus on major open problems in five areas: Network optimization, Trees and arborescences, Rigid structures, Applications of polynomial matrices, and Stable matchings. All five topics have have important applications beyond mathematics: polynomial matrices and rigidity theory are used in the analysis of molecular structures, stable matchings and generalizations are fundamental concepts in economics, while the results on trees and network optimization are basic tools in the design of communication networks. The goal of the project is to obtain algorithmic results that will have significant impact in these areas.
What is the major research question? Describe here briefly the problem to be solved by the research, the starting hypothesis, and the questions addressed by the experiments. Discrete Optimization is a fast-growing branch of applicable mathematics, dealing with algorithmic approaches to finding optimal objects in large discrete structures, such as shortest paths in networks, or best assignments in a crew assignment problem. The subject requires the development of efficient algorithms as well as the mathematical understanding of the underlying structures.
Our project aims at developing new algorithmic tools that can be efficiently used in fields beyond discrete mathematics, such as bioinformatics, economic game theory, and engineering. The research will focus on major open problems in five areas: Network optimization, Trees and arborescences, Rigid structures, Applications of polynomial matrices, and Stable matchings. All five topics have strong ties to matroid theory and submodular optimization, and all of them have important applications beyond mathematics. Fundamental open problems include the characterization of the rank of rigidity matrices, the complexity of computing the rank of polynomial matrices, and approximation algorithms for Steiner tree packing.
What is the significance of the research? Describe the new perspectives opened by the results achieved, including the scientific basics of potential societal applications. Please describe the unique strengths of your proposal in comparison to your domestic and international competitors in the given field. Our project aims at developing new algorithmic tools that can be efficiently used in fields beyond discrete mathematics, such as bioinformatics, economic game theory, and engineering. This will not only involve investigations from a discrete optimization point of view but will also lead to the development of software components by building upon the LEMON software library developed by the research group.
The research in the project will focus on major open problems in five areas: Network optimization, Trees and arborescences, Rigid structures, Applications of polynomial matrices, and Stable matchings. All five topics have important applications beyond mathematics. Polynomial matrices and rigidity theory are used in the analysis of molecular structures and in network localization problems. Stable matchings and generalizations became fundamental concepts in economics, as exemplified by the latest Nobel prize. The results on trees, arborescences and network optimization are basic tools in the design of communication networks, both wired and wireless. The goal of the project is to obtain new insights into the mathematical structures behind these concepts, and use them in the development of algorithms that will have significant impact in these fields.
Summary and aims of the research for the public Describe here the major aims of the research for an audience with average background information. This summary is especially important for NRDI Office in order to inform decision-makers, media, and others. Discrete Optimization is a fast-growing branch of applicable mathematics, dealing with algorithmic approaches to finding optimal objects in large discrete structures, such as shortest paths in networks, or best assignments in a crew assignment problem. The subject requires the development of efficient algorithms as well as the mathematical understanding of the underlying structures.
Our project aims at developing new algorithmic tools that can be efficiently used in fields beyond discrete mathematics, such as bioinformatics, economic game theory, and engineering. This sort of expansion into new territories has already started, with members of the project already achieving fundamental results in rigidity theory, game theory and telecommunications. Amplifying upon this initiative will not only involve investigations from a discrete optimization point of view but will also lead to the development of software components by building upon the LEMON software library developed by the research group.
The research in the project will focus on major open problems in five areas of discrete optimization, which all have important applications beyond mathematics, in the previously mentioned fields. The goal of the project is to obtain algorithmic results that will have significant impact in these areas.
Final report
Results in Hungarian
A projekt során a pályázat támogatásait is felhasználva 5 PhD értekezés, 6 könyvfejezet és több mint 100 tudományos publikáció született. Olyan nagy presztizsű tudományos folyóiratokban jelentek meg, mint a SIAM J. Disc. Math. (7 db), a J. Comb. Ser. B (2 db), a Math. Op. Res. (3 db), Math. Prog. (2 db) és a Combinatorica (1 db). A fentieken túl a résztvevők számos meghívott és reguláris előadást tartottak olyan tudományos összejöveteleken, mint a bonni Hausdorff intézetben szervezett Komb. Opt. trimeszter keretében tartott workshopok, a BIRS, a CIRM és az ICMS által szervezett workshopok valamint az ISCO, SODA és az Eurocomb konferenciák.
A fő eredmények:
1. A vezető kutató és Bérczi a közös háttér feltárásával számos olyan problémára adott jó karakterizációt és polinomiális algoritmust, melyek súlyozott változata már NP-nehéz.
2. Fenyőpakolások témakörében egy új elmélet alakult ki főként a projekt résztvevőinek közreműködésével. Ezzel párhuzamosan fenyőpakolások blokkolása témában is számos eredmény született.
3. A matematika egyéb területeihez is kapcsolódó chip-firing témakörében több algoritmikus és komplexitási eredményt sikerült adni.
4. A network coding témakörén keresztül sikerült egy eddig főként mérnökök által vizsgált területebe matematikai szemlélettel bekapcsolódni.
5. A merevségelmélet számos területén sikerült a komb. opt.-os ismereteket felhasználni összetettebb geomteriai struktúrájú szerkezetek merevségi tulajdonságának vizsgálatára is.
Results in English
Based on the financial support of the project its participants published 5 PhD theses, 6 book chapters and more than 100 other scientific publications. The main results of the project were published in high prestige journals such as SIAM J. Disc. Math. (7), a J. Comb. Ser. B (2), a Math. Op. Res. (3), Math. Prog. (2) és a Combinatorica (1). The members of the group were invited or regular speakers on prestigious scientific meetings such as the workshops organized during the CO trimester program of the Hausdorff Institute, the workshops organized by the BIRS, the CIRM and the ICMSn and conferences like the ISCO, SODA and Eurocomb.
The main results:
1. The PI and Bérczi, by exploring the common background, developed characterizations and polynomial algorithms for several problems whose weighted versions are already NP-hard.
2. In the topic of packing arborescences, a new theory arose with a significant impact of the participants of this project. Besides, several results were proved in the topic of blocking arborescence packings.
3. Several algorithmic and complexity results were shown for the chip-firing games which topic is connected to other branches of mathematics.
4. It succeeded to join the researches in network coding - a topic mainly researched by engineers - with a mathematical point of view.
5. The results from CO were used in rigidity theory for the examination of the rigidity properties of frameworks with rather complex geometrical properties too.
Kristóf Bérczi, Karthekeyan Chandrasekaran, Tamás Király, and Vivek Madan: A tight √ 2-approximation for Linear 3-Cut, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018
Csaba Király, Shin-ichi Tanigawa: Rigidity of Body-Bar-Hinge Frameworks (Chapter 20), in: Handbook of Geometric Constraint Systems Principles (M. Sitharam, A. St. John, J. Sidman eds.). Chapman & Hall, 2018, 2018
Bill Jackson, Tibor Jordán, and Shin-Ichi Tanigawa: Global Rigidity of Two-Dimensional Frameworks (Chapter 21), in: Handbook of Geometric Constraint Systems Principles (M. Sitharam, A. St. John, J. Sidman eds.). Chapman & Hall, 2018, 2018
Tibor Jordán, Water Whiteley: Global Rigidity (Chapter 63), in: Handbook of Discrete and Computational Geometry, (J.E. Goodman, J. O'Rourke, and C. D. Tóth eds.), 3rd edition, CRC Press, Boca Raton, 2017
Attila Bernáth, Gyula Pap: Blocking unions of arborescences, EGRES Technical Report no. 2014-02, Proceedings of the 9th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications (2015), 291-300, 2014
Katarina Cechlarova, Tamás Fleiner, Zsuzsanna Jankó: House-swapping with divorcing and engaged pairs, Proceedings of the 9th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, 2015
Alija Pasic, János Tapolcai, Péter Babarczi, Erika R. Bérczi-Kovács, Zoltán Király, L. Rónyai: Survivable Routing Meets Diversity Coding, 14th International IFIP TC6 Networking Conference, Networking 2015, Toulouse, France, May 20-22, 2015
Zoltán Király, Sándor Kisfaludi-Bak: Succinct tree coding for greedy navigation, Proceedings of the 9th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, 2015
Attila Bernáth, Tamás Király: Blocking optimal k-arborescences, Proceeding SODA '16 Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms Pages 1682-1694, 2016
András Frank, Tibor Jordán: Graph connectivity augmentation, In: K. Thulasiraman, S. Arumugam, A. Brandstadt, T. Nishizeki (eds.), Handbook of Graph Theory, Combinatorial Optimization, and Algorithms, pp. 313-346 (Chapter 14), 2015
János Tapolcai, Gábor Rétvári, Péter Babarczi, Erika R. Bérczi-Kovács, Panna Kristóf, Gábor Enyedi: Scalable and efficient multipath routing: Complexity and algorithms, 23rd IEEE International Conference on Network Protocols, ICNP 2015. San Francisco, USA Piscataway: IEEE Computer Society, 2016. pp. 376-385., 2016
Kristóf Bérczi, Alpár Jüttner: Road surveillance optimization—an asymmetric vehicle routing problem with visiting frequencies, In The 9th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, Fukuoka, Japan, jun 2015., 2015
Péter Madarasi, Alpár Jüttner: Improved Algorithms for Matching Biological Graphs, ECCO XXIX, 29th Conference of the European Chapter on Combinatorial Optimization (ECCO), May 26 - 28, 2016, Budapest, Hungary, 2016
Bill Jackson, Tibor Jordán, Shin-ichi Tanigawa: Unique Low Rank Completability of Partially Filled Matrices, Journal of Combinatorial Theory, Series B Volume 121, Pages 432–462 (Special Issue: Fifty years of The Journal of Combinatorial Theory.), 2016
Kristóf Bérczi, Karthekeyan Chandrasekaran, Tamás Király, Euiwoong Lee, Chao Xu: Global and fixed-terminal cuts in digraphs, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017) Klaus Jansen and José D. P. Rolim and David Williamson and Sa, 2017
Kristóf Bérczi, Erika R. Bérczi-Kovács: Directed hypergraphs and Horn minimization, Information Processing Letters, 128, 32-37, 2017
Tamás Fleiner, Zsuzsanna Jankó: On Weighted Kernels of Two Posets, ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS 33:(1) pp. 51-65., 2016
Péter Babarczi, János Tapolcai, Alija Pašić, Lajos Rónyai, Erika R. Bérczi-Kovács, Muriel Médard: Diversity Coding in Two-Connected Networks, IEEE/ACM Transactions on Networking, 2017
Kristóf Bérczi, Attila Bernáth, Tamás Király, Gyula Pap: Blocking optimal structures, Proceedings of the 10th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications May 22-25, 2017, Budapest, Hungary. 67-76, 2017
Viktória E. Kaszanitzky, Bernd Schulze: Sufficient connectivity conditions for rigidity of symmetric frameworks, 10th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, 2017
Tibor Jordán: Extremal problems and results in combinatorial rigidity, 10th Japanese-Hungarian Symposium, 2017
Alpár Jüttner, Péter Madarasi: A Primal-Dual Approach for Large Scale Integer Problems, 10th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, Budapest, 2017
