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 aktív projekt





 

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 »