Blocking problems in combinatorial optimization  Page description

Help  Print 
Back »

 

Details of project

 
Identifier
120254
Type K
Principal investigator Király, Tamás
Title in Hungarian Lefogási problémák a kombinatorikus optimalizálásban
Title in English Blocking problems in combinatorial optimization
Keywords in Hungarian gráf, hálózat, összefüggőség, szubmoduláris optimalizálás
Keywords in English graph, network, connectivity, submodular optimization
Discipline
Mathematics (Council of Physical Sciences)100 %
Ortelius classification: Discrete mathematics
Panel Mathematics and Computing Science
Department or equivalent Department of Operations Research (Eötvös Loránd University)
Starting date 2016-10-01
Closing date 2021-09-30
Funding (in million HUF) 5.364
FTE (full time equivalent) 3.20
state running project





 

Final report

 
Results in Hungarian
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.
Results in English
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.
Full text https://www.otka-palyazat.hu/download.php?type=zarobeszamolo&projektid=120254
Decision
Yes





 

List of publications

 
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




Back »