Lefogási problémák a kombinatorikus optimalizálásban  részletek

súgó  nyomtatás 
vissza »
 

Projekt adatai

  
azonosító
120254
típus K
Vezető kutató Király Tamás
magyar cím Lefogási problémák a kombinatorikus optimalizálásban
Angol cím Blocking problems in combinatorial optimization
magyar kulcsszavak gráf, hálózat, összefüggőség, szubmoduláris optimalizálás
angol kulcsszavak graph, network, connectivity, submodular optimization
megadott besorolás
Matematika (Műszaki és Természettudományok Kollégiuma)100 %
Ortelius tudományág: Diszkrét matematika
zsűri Matematika–Számítástudomány
Kutatóhely Operációkutatási Tanszék (Eötvös Loránd Tudományegyetem)
projekt kezdete 2016-10-01
projekt vége 2021-09-30
aktuális összeg (MFt) 5.364
FTE (kutatóév egyenérték) 3.20
állapot lezárult projekt
magyar összefoglaló
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.
Egy véges alaphalmazon adott halmazrendszerre vonatkozó lefogási feladat a következő: mi a legkisebb elemszámú (vagy általánosabban legkisebb súlyú) halmaz, ami a halmazrendszer minden elemét metszi? Egy gráf feszítő fáinak a lefogásához egy vágásra van szükség, így a lefogási feladat a minimális vágás feladatnak felel meg. Más kombinatorikus struktúrákra a lefogási feladat jóval nehezebb lehet: pl. páros gráfban a teljes párosítások minimális lefogása NP-nehéz feladat. A projekt célja előrelépést elérni egyrészt új polinom időben megoldható lefogási feladatok felfedezésével, másrészt jobb közelítő algoritmusok keresésével NP-nehéz feladatokra. A projekt jelentős része irányított gráfok lefogási problémáival foglakozik; ide tartoznak a fenyő- és út-lefogási feladatok, valamint Woodall sejtése. Szeretnénk új eredményeket bizonyítani a lefogó halmazok általános struktúrájával kapcsolatban, illetve a szubmoduláris függvény minimalizálási probléma kapcsán, ami a minimális vágás probléma egy jelentős általánosítása. A projektben vizsgált konkrét nyitott kérdések nagyrészt a projekt résztvevőinek korábbi kutatásaihoz kapcsolódnak.

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.
Egy véges alaphalmazon adott halmazrendszerre vonatkozó lefogási feladat a következő: mi a legkisebb elemszámú (vagy általánosabban legkisebb súlyú) halmaz, ami a halmazrendszer minden elemét metszi? Egy gráf feszítő fáinak a lefogásához egy vágásra van szükség, így a lefogási feladat a minimális vágás feladatnak felel meg. Más kombinatorikus struktúrákra a lefogási feladat jóval nehezebb lehet: pl. páros gráfban a teljes párosítások minimális lefogása NP-nehéz feladat. A projekt célja előrelépést elérni egyrészt új polinom időben megoldható lefogási feladatok felfedezésével, másrészt jobb közelítő algoritmusok keresésével NP-nehéz feladatokra. A projekt jelentős része irányított gráfok lefogási problémáival foglakozik; ide tartoznak a fenyő- és út-lefogási feladatok, valamint Woodall sejtése. Szeretnénk új eredményeket bizonyítani a lefogó halmazok általános struktúrájával kapcsolatban, illetve a szubmoduláris függvény minimalizálási probléma kapcsán, ami a minimális vágás probléma egy jelentős általánosítása. A projektben vizsgált konkrét nyitott kérdések nagyrészt a projekt résztvevőinek korábbi kutatásaihoz kapcsolódnak.

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!
Bár a projekt témájának nincs közvetlen ipari alkalmazása, az irányított gráfok lefogási problémái szorosan kötődnek hálózatok megbízhatóságának illetve hibatűrésének a kérdéseihez. A projekt így hozzájárul a hálózattervezés alapvető elméleti matematikai alapjainak a megértéséhez. A szubmoduláris minimalizálás, a projekt másik fő témaköre, fontos szerepet tölt be a matematika más ágaiban, így a CSP-k, a játékelmélet, és a gépi tanulás területén.

A világon számos kutatócsoport dolgozik hasonló kérdéseken, ezek közül hármat emelünk ki. Az utóbbi időben számos jelentős új eredmény született úgynevezett "interdiction" problémákról, főleg Zürich-i kutatók jóvoltából. Ezek a problémák a lefogási feladatok nehezebb változatának tekinthetők, ahol kombinatorikus struktúrák gyengítését akarjuk elérni egy adott költségkeret felhasználásával. A második nagy aktív terület a többterminálos vágásokra, és ehhez kapcsolódóan a megbízható hálózattervezésre vonatkozó közelítő algoritmusok elmélete. Az elmúlt években született áttörések közül megemlítendő Byrka et al. Steiner-fa közelítő algoritmusa, valamint Sharma és Vondrak 1,297-közelítő algoritmusa az élsúlyozott többterminálos vágás feladatra. Végül kiemelendő japán kutatóknak a munkája a szubmoduláris optimalizálás és diszkrét konvexitás terén, többek között Satoru Fujishige, Kazuo Murota, Satoru Iwata, és Hiroshi Hirai részvételével.

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 kutatás a hálózatok megbízhatóságának és hibatűrésének vizsgálatához használt matematikai modellek elméleti alapjaival foglalkozik. A lefogási feladatok ezt a kérdéskört a támadó szemszögéből vizsgálják: mi a leghatékonyabb módja a hálózat valamilyen tulajdonsága megszüntetésének? Egy klasszikus példa a Maximális Folyam Minimális Vágás Tétel, ami interpretálható úgy, hogy egy adott célnak egy adott forrástól való elvágásához pontosan olyan összsúlyú élt kell törölni, amennyi a maximális folyam értéke a forrásból a célba. A projektben ennek a minimális vágás problémának a különböző általánosításaira vonatkozó nyitott kérdéseket vizsgálunk.
angol összefoglaló
Summary of the research and its aims for experts
Describe the major aims of the research for experts.
The blocking problem for a family of subsets of a finite ground set asks for the minimum number (or, more generally, minimum weight) of elements that intersect every member of the family. For example, blocking all spanning trees requires the removal of edges of a cut, so it is equivalent to the minimum cut problem. Blocking problems for other combinatorial structures can be substantially more difficult; for example, blocking all perfect matchings of a bipartite graph using the minimum number of edges is NP-hard. The aim of the project is to make progress by extending the family of polynomial-time solvable blocking problems and by finding better approximation algorithms for NP-hard ones. The bulk of the project concerns blocking problems in directed graphs, including blocking k-arborescences, Woodall's conjecture, and blocking both s-t and t-s paths. We also wish to make progress on open problems on the general structure of blockers and on submodular minimization, a powerful generalization of the minimum cut problem. The project focuses on specific open questions that are related to the participants' earlier work on the topic.

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.
The blocking problem for a family of subsets of a finite ground set asks for the minimum number (or, more generally, minimum weight) of elements that intersect every member of the family. For example, blocking all spanning trees requires the removal of edges of a cut, so it is equivalent to the minimum cut problem. Blocking problems for other combinatorial structures can be substantially more difficult; for example, blocking all perfect matchings of a bipartite graph using the minimum number of edges is NP-hard. The aim of the project is to make progress by extending the family of polynomial-time solvable blocking problems and by finding better approximation algorithms for NP-hard ones. The bulk of the project concerns blocking problems in directed graphs, including blocking k-arborescences, Woodall's conjecture, and blocking both s-t and t-s paths. We also wish to make progress on open problems on the general structure of blockers and on submodular minimization, a powerful generalization of the minimum cut problem. The project focuses on specific open questions that are related to the participants' earlier work on the topic.

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.
Although the topics of the project have no direct applications in industry, blocking problems in directed graphs are closely related to network reliability, the discipline studying the resistance of networks to various types of failures. The project thus contributes to the understanding of the fundamental theoretical foundations of network design. Submodular minimization, which is another main topic of the project, has applications in other areas of mathematics like constraint satisfaction problems, game theory, and machine learning.

Several research groups are doing active research in related areas, of which we highlight three. There have been important advances recently on interdiction problems, due mainly to researchers in Zurich. Interdiction problems are typically harder versions of blocking problems, where the aim is to weaken combinatorial structures as much as possible using a given budget. In the last few years, new results have been obtained on flow, matching, and connectivity interdiction problems. The second big active area is approximation algorithms for multiway cut problems, and the related problem of survivable network design. These areas had several breakthrough results in recent years, like the improved approximation algorithm for Steiner trees by Byrka at al., or the 1.297-approximation for edge-weighted multiway cut by Sharma and Vondrak. Finally, there is a large group of researchers in Japan working on submodular optimization and discrete convexity, including Satoru Fujishige, Kazuo Murota, Satoru Iwata, and Hiroshi Hirai.

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.
The research focuses on the theoretical foundations of mathematical models used for evaluating the robustness and reliability of networks. Blocking problems consider these questions from the viewpoint of an attacker: what is the most efficient way of destroying a certain property of the network? A classic example is the Maximum Flow Minimum Cut Theorem, which states that total weight of the arcs that have to be removed in order to disconnect a given destination from a given source in a network equals the maximum flow from source to destination. The project studies open questions about various generalizations of this minimum cut problem.




 

Zárójelentés

  
kutatási eredmények (magyarul)
A gráfok vágásaival és különféle gráf-struktúrák lefogásával illetve blokkolásával kapcsolatos optimalizációs problémák alapvető eszközök egyrészt a hálózattervezésben a biztonsági és megbízhatósági szempontok matematikai modellezésére, másrészt a szociális mechanizmus-tervezés elméletében (igazságos hozzárendelések és szavazási mechanizmusok). A projekt számos új matematikai eredményt tudott elérni ezeken a területeken. Kiemelendő a 3-terminálos lineáris vágás probléma teljes megoldása, egy jelentős előrelépés a multi-vágás feladat közelíthetőségének a megválaszolásában, és új, hatékony (polinom idejű) algoritmusok a népszerű fenyő és népszerű hozzárendelés feladatokra, amik a szociális mechanizmus-tervezésben hasznosíthatók. Az eredményeket a szakterület vezető konferenciáin mutattuk be: SODA 2018, IPCO 2019 és 2020, valamint egy új elfogadott cikk a SODA 2022 konferenciára. További konferencia-szereplések: APPROX 2017, Eurocomb 2017, ISCO 2020, valamint a Japán-Magyar Diszkrét Matematikai Szimpózium (2017 and 2019) és a Magyar Operációkutatási Konferencia (2017 és 2019). A projekt 9 folyóiratcikke közül 4 D1-es folyóiratban jelent meg, 7 Q1-esben.
kutatási eredmények (angolul)
Optimization problems related to cuts in graphs and the blocking of graph structures are fundamental mathematical tools in network design for the modeling of network security and reliability issues, as well as in the theory of social choice (fair assignments, voting mechanisms). The project obtained important new mathematical results for a variety of problems in this area. Highlights include the complete solution of the 3-terminal linear cut problem, a significant advancement on the approximability of the multiway cut problem, and the first polynomial-time algorithms for the popular branching and popular assignment problems, which are relavant to social choice. The results of the project have been presented in top conferences of the area: SODA 2018, IPCO 2019 and 2020, and a new paper has been accepted to SODA 2022. Additional presentations at conferences include APPROX 2017, Eurocomb 2017, ISCO 2020, the Japanese-Hungarian Symposium on Discrete Mathematics (2017 and 2019) and the Hungarian Operations Research Conference (2017). 9 papers have appeared or have been accepted to refereed journals, of which 4 are in D1 journals and 7 in Q1.
a zárójelentés teljes szövege https://www.otka-palyazat.hu/download.php?type=zarobeszamolo&projektid=120254
döntés eredménye
igen





 

Közleményjegyzék

  
T. Kavitha, T. Király, J. Matuschke, I. Schlotter, U. Schmidt-Kraepelin: Popular Branchings and Their Dual Certificates, Mathematical Programming, 2021
K. Bérczi, K. Chandrasekaran, T. Király, E. Lee, C. Xu: Global and fixed-terminal cuts in digraphs, Proceedings of Approximation, Randomization, and Combinatorial Optimization (APPROX/RANDOM 2017), 2017
K. Bérczi, T. Király, Y. Yamaguchi, Y. Yokoi: Approximation by Lexicographically Maximal Solutions in Matching and Matroid Intersection Problems, arxiv:2107.09897 (közlésre elfogadva: Theoretical Computer Science), 2021
K. Bérczi, A. Bernáth, T. Király, Gy. Pap: Blocking optimal structures, Proceedings of the 10th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, 2016
T. Király, Zs. Mészáros-Karkus: Finding strongly popular b-matchings in bipartite graphs, Proceedings of EUROCOMB 2017, Electronic Notes in Discrete Mathematics Volume 61 (2017), 735-741, 2017
T. Király, Zs. Mészáros-Karkus: Finding strongly popular matchings in certain bipartite preference systems, Proceedings of the 10th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, 2016, 2016
K. Bérczi, K. Chandrasekaran, T. Király, V. Madan: A tight $\sqrt{2}$-approximation for Linear 3-Cut, EGRES Technical Report 2017-10, 2017
K. Bérczi, A. Bernáth, T. Király, Gy. Pap: Blocking optimal structures, Discrete Mathematics, Volume 341, Issue 7, July 2018, 1864-1872, 2018
K. Bérczi, K. Chandrasekaran, T. Király, V. Madan: A tight $\sqrt{2}$-approximation for Linear 3-Cut, Proceeding SODA '18 Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms Pages 1393-1406, 2018
K. Bérczi, K. Chandrasekaran, T. Király, E. Lee, C. Xu: Beating the 2-approximation factor for global bicut, Mathematical Programming Series A, available online (2018), 2018
K. Bérczi, K. Chandrasekaran, T. Király, V. Madan: Improving the Integrality Gap for Multiway Cut, arXiv:1807.09735, 2018
T. Király, Zs. Mészáros-Karkus: Finding strongly popular b-matchings in bipartite graphs, Proceedings of EUROCOMB 2017, Electronic Notes in Discrete Mathematics Volume 61 (2017), 735-741 (accepted to European Journal on Combinatorics), 2017
K. Bérczi, K. Chandrasekaran, T. Király, V. Madan: A tight $\sqrt{2}$-approximation for Linear 3-Cut, Mathematical Programming, available online, 2019
K. Bérczi, K. Chandrasekaran, T. Király, V. Madan: Improving the Integrality Gap for Multiway Cut, In: Lodi A., Nagarajan V. (eds) Integer Programming and Combinatorial Optimization. IPCO 2019. Lecture Notes in Computer Science, vol 11480. Springer, 2019
T. Király, Y. Yokoi: Equitable Partitions into Matchings and Coverings in Mixed Graphs, arxiv:1811.07856, 2019
T. Király, Zs. Mészáros-Karkus: Complexity of the NTU International Matching Game, EGRES Technical Report TR-2019-12, 2019
T. Király, Zs. Mészáros-Karkus: Erősen népszerű párosítások keresése bizonyos páros preferencia-rendszerekben, Alkalmazott Matematikai Lapok 36 (2019), 1-7., 2019
K. Bérczi, K. Chandrasekaran, T. Király, V. Madan: New developments on the approximability of Multiway Cut, Proc 11th Japanese-Hungarian Symposium on Discrete Mathematics and its Applications, 41-45, 2019
K. Bérczi, K. Chandrasekaran, T. Király, E. Lee, C. Xu: Global and fixed-terminal cuts in digraphs, Proceedings of Approximation, Randomization, and Combinatorial Optimization (APPROX/RANDOM 2017), 2017
T. Király, Zs. Mészáros-Karkus: Finding strongly popular b-matchings in bipartite graphs, Proceedings of EUROCOMB 2017, Electronic Notes in Discrete Mathematics Volume 61 (2017), 735-741 (accepted to European Journal on Combinatorics), 2017
K. Bérczi, K. Chandrasekaran, T. Király, V. Madan: A tight $\sqrt{2}$-approximation for Linear 3-Cut, Mathematical Programming 184, 411–443 (2020), 2020
K. Bérczi, K. Chandrasekaran, T. Király, E. Lee, C. Xu: Beating the 2-approximation factor for global bicut, Mathematical Programming Series A, volume 177, 291-320 (2019), 2019
K. Bérczi, K. Chandrasekaran, T. Király, V. Madan: Improving the Integrality Gap for Multiway Cut, In: Lodi A., Nagarajan V. (eds) Integer Programming and Combinatorial Optimization. IPCO 2019. Lecture Notes in Computer Science, vol 11480. Springer, 2019
T. Király, Y. Yokoi: Equitable Partitions into Matchings and Coverings in Mixed Graphs, arxiv:1811.07856, 2019
K. Bérczi, K. Chandrasekaran, T. Király, V. Madan: New developments on the approximability of Multiway Cut, Proc 11th Japanese-Hungarian Symposium on Discrete Mathematics and its Applications, 41-45, 2019
T. Király, Zs. Mészáros-Karkus: Finding strongly popular b-matchings in bipartite graphs, European Journal of Combinatorics Volume 88, August 2020, 2020
T. Kavitha, T. Király, J. Matuschke, I. Schlotter, U. Schmidt-Kraepelin: Popular Branchings and Their Dual Certificates, Proceedings of IPCO 2020, LNCS, volume 12125, 223-237, 2020
K. Bérczi, A. Bernáth, T. Király, Gy. Pap: Blocking optimal structures, Discrete Mathematics, Volume 341, Issue 7, July 2018, 1864-1872, 2018
K. Bérczi, T. Király, S. Omlor: Scheduling with Non-Renewable Resources: Minimizing the Sum of Completion Times, Proceedings of ISCO 2020, LNCS, volume 12176, 167-178, 2020
K. Bérczi, K. Chandrasekaran, T. Király, V. Madan: Improving the Integrality Gap for Multiway Cut, Mathematical Programming, Volume 183, 171–193, 2020
T. Király: Base polyhedra and the linking property, Journal of Combinatorial Optimization 36 (2018), 671-677, 2018
T. Király, Y. Yokoi: Equitable Partitions into Matchings and Coverings in Mixed Graphs, arxiv:1811.07856 (közlésre elfogadva: Discrete Mathematics), 2019
T. Kavitha, T. Király, J. Matuschke, I. Schlotter, U. Schmidt-Kraepelin: The popular assignment problem: when cardinality is more important than popularity, arXiv:2110.10984 (közlésre elfogadva: SODA 2022), 2021
K. Bérczi, T. Király, S. Omlor: Scheduling with Non-Renewable Resources: Minimizing the Sum of Completion Times, Proceedings of ISCO 2020, LNCS, volume 12176, 167-178, 2020
K. Bérczi, K. Chandrasekaran, T. Király, E. Lee, C. Xu: Global and fixed-terminal cuts in digraphs, Proceedings of Approximation, Randomization, and Combinatorial Optimization (APPROX/RANDOM 2017), 2017
T. Király, Zs. Mészáros-Karkus: Finding strongly popular matchings in certain bipartite preference systems, Proceedings of the 10th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, 2017



vissza »