Matroidal optimization  Page description

Help  Print 
Back »
 

Details of project

  
Identifier
128673
Type FK
Principal investigator Bérczi, Kristóf
Title in Hungarian Matroid-optimalizálási problémák
Title in English Matroidal optimization
Keywords in Hungarian matroid metszet; közös bázisok pakolása; fenyők pakolása; kombinatorikus merevség; irányított hipergráfok
Keywords in English matroid intersection; packing common bases; arborescence packing; combinatorial rigidity; directed hypergraphs
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)
Participants Csehi, Csongor György
Frank, András
Kaszanitzky, Viktória Eszter
Király, Csaba
Mendoza Cadena, Lydia Mirabel
Schwarcz, Tamás Bence
Tóthmérész, Lilla
Starting date 2018-09-01
Closing date 2023-09-30
Funding (in million HUF) 19.860
FTE (full time equivalent) 11.20
state running project





 

Final report

  
Results in Hungarian
A projekt során csaknem 60 tudományos publikáció született, melyek olyan nagy presztizsű tudományos folyóiratokban jelentek meg, mint a Mathematics of Operations Research, Mathematical Programming, SIAM Journal on Discrete Mathematics, Journal of Combinatorial Theory Ser. A, és a Discrete Mathematics. A cikkeken túl a projekthez kapcsolódóan két PhD értekezés is születni fog. A kutatás résztvevői előadást tartottak olyan tudományos összejöveteleken, mint a Cargese-ben szervezett kutatási workshop, a bonni Hausdorff intézetben szervezett kombinatorikus optimalizálási workshop, a Bellairs-ben tartott diszkrét optimalizálási workshop, valamint az OP, ISCO, és SODA konferenciák. A kutatás során elért főbb eredmények a következők: 1. A pályázat fő célkitűzése közös bázisok pakolásának vizsgálata volt matroidok metszetében. Sikerült megmutatnunk, hogy a feladat általában orákulum-nehéz, így nem adható rá hatékony algoritmus. 2. Számos strukturális eredményt sikerült igazolni matroidok független halmazaira vonatkozóan, melyek régóta nyitott sejtések részleges megoldásához vezetett. 3. A csoport aktívan részt vett a dinamikus árazások témakörének kidolgozásában, elsősorban a matroidokkal kapcsolatos irányra koncentrálva. 4. Sikerült algoritmust adni a matematika több területéhez is kapcsolódó inverz optimalizálási problémákra. 5. A csoport tagjai a merevségelmélet számos területén értek el új eredményeket.
Results in English
The financial support of the project resulted in almost 60 scientific publications. The main results of the project were published in high prestige journals such as Mathematics of Operations Research, Mathematical programming, SIAM Journal on Discrete Mathematics, Journal of Combinatorial Theory Ser. A, and Discrete Mathematics. In addition, we expect the defense of two PhD theses related to the topic of the project in the next year. The members of the group gave talks on scientific meetings such as the Cargese workshop on combinatorial optimization, the Hausdorff workshop in Bonn, and the Bellairs workshop on discrete optimization, and conferences like OP, ISCO and SODA. The main objective of the project was to settle the complexity of packing common bases in the intersection of two matroids. The main results are as follows: 1. We showed that the problem is oracle-hard in general, hence there is no hope for giving an efficient algorithm. 2. Several structural results were shown on the structure of independent sets of matroids, which in turn lead to progress in several long-standing open problems. 3. Recently, the theory of dynamic pricing received great interest with significant impact of the participants of the project. In particular, we concentrated on the matroidal aspects of the problem. 4. Several algorithmic results were given for inverse optimization problems, a topic that is related to various areas of mathematics. 5. The participants achieved interesting results in rigidity theory.
Full text https://www.otka-palyazat.hu/download.php?type=zarobeszamolo&projektid=128673
Decision
Yes





 

List of publications

  
Kristóf Bérczi, Tamás Schwarcz: Partitioning into common independent sets via relaxing strongly base orderability, Journal of Combinatorial Theory A, 2024
Bérczi Kristóf, Király Tamás, Schwarcz Tamás, Yamaguchi Yutaro, Yokoi Yu: Hypergraph characterization of split matroids, JOURNAL OF COMBINATORIAL THEORY SERIES A 194: 105697, 2023
Bérczi Kristóf, Csáji Gergely, Király Tamás: On the complexity of packing rainbow spanning trees, DISCRETE MATHEMATICS 346: (4) 113297, 2023
Alpár Jüttner, Csaba Király, Lydia Mirabel Mendoza-Cadena, Gyula Pap, Ildikó Schlotter, Yutaro Yamaguchi: Shortest Odd Paths in Undirected Graphs with Conservative Weight Functions, arXiv (submitted to DAM), 2023
Bérczi Kristóf, Mendoza-Cadena Lydia Mirabel, Varga Kitti: Inverse optimization problems with multiple weight functions, DISCRETE APPLIED MATHEMATICS 327: pp. 134-147., 2023
Berczi Kristof, Kiraly Tamas, Yamaguchi Yutaro, Yokoi Yu: MATROID INTERSECTION UNDER RESTRICTED ORACLES, SIAM JOURNAL ON DISCRETE MATHEMATICS 37: (2) pp. 1311-1330., 2023
József Pintér, Kitti Varga: Color-avoiding connected spanning subgraphs with minimum number of edges, Proceedings of the 12th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, 2023
András Frank, Kazuo Murota: Decreasing minimization on base-polyhedra: relation between discrete and continuous cases, Mathematical Programming 40, pages 183–221, 2023
Bérczi Kristóf, Hoang H.P., Tóthmérész L.: On approximating the rank of graph divisors, DISCRETE MATHEMATICS 346: (9) 113528, 2023
Bérczi Kristóf, Bérczi-Kovács Erika R., Szögi Evelin: A Dual Approach for Dynamic Pricing in Multidemand Markets, SIAM JOURNAL ON DISCRETE MATHEMATICS 37: (3) pp. 1771-1787., 2023
Bérczi Kristóf, Chandrasekaran Karthekeyan, Király Tamás, Pillai Aditya: Analyzing Residual Random Greedy for monotone submodular maximization, INFORMATION PROCESSING LETTERS 180: 106340, 2023
Csaba Király: On the size of highly redundantly rigid graphs, Proceedings of the 12th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, 2023
Bérczi Kristóf, Mnich Matthias, Vincze Roland: Approximations for many-visits multiple traveling salesman problems, OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE 116: 102816, 2023
Csaba Király, András Mihálykó: Fast algorithms for sparsity matroids and the global rigidity augmentation problem, EGRES TR 2022-05, 2023
Bérczi Kristóf, Mnich Matthias, Vincze Roland: Approximations for many-visits multiple traveling salesman problems, OMEGA-INTERNATIONAL JOURNAL OF MANAGEMENT SCIENCE 116: 102816, 2023
Bérczi Kristóf, Boros Endre, Čepek Ondřej, Kučera Petr, Makino Kazuhisa: Approximating Minimum Representations of Key Horn Functions, SIAM JOURNAL ON COMPUTING 51: (1) pp. 116-138., 2022
András Frank, Kazuo Murota: Decreasing minimization on M-convex sets: background and structures, Mathematical Programming 195, pages 977–1025, 2022
Dániel Garamvölgyi, Tibor Jordán, Csaba Király: Count and cofactor matroids of highly connected graphs, EGRES TR-2022-12 (submitted to JCTB), 2022
Kristóf Bérczi, Alexander Göke, Lydia Mirabel Mendoza-Cadena, and Matthias Mnich: Resolving Infeasibility of Linear Systems: A Parameterized Approach, arXiv:2209.02017, 2022
Tamás Kálmán, Lilla Tóthmérész: Root polytopes and Jaeger-type dissections for directed graphs, Mathematika Volume 68, Issue 4 p. 1176-1220, 2022
Bérczi Kristóf, Mnich Matthias, Vincze Roland: A 3/2-Approximation for the Metric Many-Visits Path TSP, SIAM JOURNAL ON DISCRETE MATHEMATICS 36: (4) pp. 2995-3030., 2022
András Frank, Kazuo Murota: A Discrete Convex Min-Max Formula for Box-TDI Polyhedra, Mathematics of Operations Research, Volume 47, Issue 2, Pages 847-1705, 2022
András Frank, Kazuo Murota: Fair Integral Network Flows, Mathematics of Operations Research Volume 48, Issue 3 August 2023 Pages 1213-1809, C2, 2022
Csaba Király: Rigid realizations of planar graphs with few locations in the plane, European Journal of Combinatorics 94, 2021
András Frank, Gergely Hajdu: Simple algorithm and min-max formula for the inverse arborescence problem, Discrete Applied Mathematics Volume 295, 31 May 2021, Pages 85-93, 2021
Bill Jackson, Viktoria Kaszanitzky, Bernd Schulze: Scene analysis with symmetry, Proceedings for Developments in Computer Science, 2021
Tamás Kálmán, Lilla Tóthmérész: Root polytopes and Jaeger-type dissections for directed graphs, Mathematika, 2022
Dániel Garamvölgyi, Tibor Jordán, Csaba Király: Count and cofactor matroids of highly connected graphs, EGRES Technical Report, 2022
Csaba Király, Zoltán Szigeti, Sin-ichi Tanigawa: Packing of arborescences with matroid constraints via matroid intersection, Mathematical Programming A, 181, pages 85–117, 2020
Quentin Fortier, Csaba Király, Zoltán Szigeti, Shin‐ichi Tanigawa: On packing spanning arborescences with matroid constraint, Journal of Graph Theory 93 (2), p. 230-252, 2020
Kristóf Bérczi, Karthekeyan Chandrasekaran, Tamás Király, Vivek Madan: A tight sqrt(2)-approximation for linear 3-cut, Mathematical Programming 184, pages 411–443, 2020
Csaba Király: Rigid realizations of graphs with few locations in the plane, EUROPEAN JOURNAL OF COMBINATORICS, 2021
Király Cs., Mihálykó A.: Sparse Graphs and an Augmentation Problem, MATHEMATICAL PROGRAMMING, 2022
Kaszanitzky V.E., Király Cs., Schulze B.: Sufficient conditions for the global rigidity of periodic graphs, DISCRETE AND COMPUTATIONAL GEOMETRY, 2022
Bérczi Kristóf, Boros Endre, Čepek Ondřej, Kučera Petr, Makino Kazuhisa: Approximating Minimum Representations of Key Horn Functions, SIAM JOURNAL ON COMPUTING 51: (1) pp. 116-138., 2022
Bérczi Kristóf, Boros Endre, Čepek Ondřej, Kučera Petr, Makino Kazuhisa: Unique key Horn functions, THEORETICAL COMPUTER SCIENCE, 2022
Bérczi Kristóf, Király Tamás, Yamaguchi Yutaro, Yokoi Yu: Approximation by lexicographically maximal solutions in matching and matroid intersection problems, THEORETICAL COMPUTER SCIENCE 910: pp. 48-53., 2022
Bérczi Kristóf, Schwarcz Tamás: Rainbow and monochromatic circuits and cocircuits in binary matroids, DISCRETE MATHEMATICS 345: (6) 112830, 2022
Kristóf Bérczi, Alexander Göke, Lydia Mirabel Mendoza-Cadena, and Matthias Mnich: Resolving Infeasibility of Linear Systems: A Parameterized Approach, , 2022
Kristóf Bérczi, Lydia Mirabel Mendoza-Cadena, Kitti Varga: Inverse optimization problems with multiple weight functions, , 2022
Kristóf Bérczi, Matthias Mnich, Roland Vincze: Efficient Approximations for Many-Visits Multiple Traveling Salesman Problems, , 2022
Kristóf Bérczi, Tamás Király, Tamás Schwarcz, Yutaro Yamaguchi, Yu Yokoi: Hypergraph characterization of split matroids, , 2022
Bérczi Kristóf, Boros Endre, Čepek Ondřej, Elbassioni Khaled, Kučera Petr, Makino Kazuhisa: Generating clause sequences of a CNF formula, THEORETICAL COMPUTER SCIENCE 856: pp. 68-74., 2021
Berczi Kristof, Kakimura Naonori, Kobayashi Yusuke: MARKET PRICING FOR MATROID RANK VALUATIONS\ast, SIAM JOURNAL ON DISCRETE MATHEMATICS 35: (4) pp. 2662-2678., 2021
Berczi Kristof, Schwarcz Tamas: Complexity of packing common bases in matroids, MATHEMATICAL PROGRAMMING 188: (1) pp. 1-18., 2021
Bérczi Kristóf, Schwarcz Tamás, Yamaguchi Yutaro: List Coloring of Two Matroids through Reduction to Partition Matroids, SIAM JOURNAL ON DISCRETE MATHEMATICS 35: (3) pp. 2192-2209., 2021
Kristof Berczi, Tamas Kiraly, Yutaro Yamaguchi, Yu Yokoi: Approximation by Lexicographically Maximal Solutions in Matching and Matroid Intersection Problems, , 2021
Kristóf Bérczi, Tamás Schwarcz: Rainbow and monochromatic circuits and cuts in binary matroids, , 2021
Viktória Kaszanitzky: A Physical Zero-knowledge Proof for the Mainarizumu Puzzle, Proceedings of the 11th Hungarian-Japanese Symposium on Discrete Mathematicsand Its Applications, 2019
András Frank, Kazuo Murota: Discrete Decreasing Minimization, Part I: Base-polyhedra with Applications in Network Optimization, ArXiv, 2019
András Frank, Kazu Murota: Discrete Decreasing Minimization, Part II: Views from Discrete Convex Analysis, ArXiv, 2019
András Frank, Kazuo Murota: Discrete Decreasing Minimization, Part III: Network Flows, ArXiv, 2019
Tamás Kálmán, Seunghun Lee, Lilla Tóthmérész: The sandpile group of a trinity and a canonical definition for the planar Bernardi action, ArXiv, 2019
Csongor Gy. Csehi: Sufficient condition for almost-irreducibility of matroids, Solving an old conjecture, Proceedings of the 11th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, 2019
Csaba Király, Zoltán Szigeti, Sin-ichi Tanigawa: Packing of arborescences with matroid constraints via matroid intersection, Mathematical Programming, 2019
Kristóf Bérczi, Tamás Schwarcz: Complexity of packing common bases in matroids, ArXiv, 2019
Quentin Fortier, Csaba Király, Zoltán Szigeti, Shin‐ichi Tanigawa: On packing spanning arborescences with matroid constraint, Journal of Graph Theory, 2019
Csaba Király: Rigid realizations of planar graphs with few locations in the plane, Proceedings of the 11th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, 2019
Tamás Kálmán, Seunghun Lee, Lilla Tóthmérész: The sandpile group of a trinity and a canonical definition for the planar Bernardi action, ArXiv, 2019
Kristóf Bérczi, Tamás Schwarcz: Complexity of packing common bases in matroids, Mathematical Programming, 2020
Kristóf Bérczi, Karthekeyan Chandrasekaran, Tamás Király, Vivek Madan: A tight sqrt(2)-approximation for linear 3-cut, Mathematical Programming, 2019
Kristóf Bérczi, Karthekeyan Chandrasekaran, Tamás Király, Euiwoong Lee, Chao Xu: Beating the 2-approximation factor for Global Bicut, Mathematical Programming, 2019
Kristóf Bérczi, André Berger, Matthias Mnich, Roland Vincze: Degree-bounded generalized polymatroids and approximating the metric many-visits TSP, arXiv, 2019
Kristóf Bérczi, Tamás Schwarcz, Yutaro Yamaguchi: List colouring of two matroids through reduction to partition matroids, arXiv, 2019
Kristóf Bérczi, Endre Boros, Ondřej Čepek, Khaled Elbassioni, Petr Kučera, Kazuhisa Makino: Generating clause sequences of a CNF formula, arXiv, 2020
Kristóf Bérczi, Tamás Király, Simon Omlor: Scheduling with Non-renewable Resources: Minimizing the Sum of Completion Times, International Symposium on Combinatorial Optimization ISCO 2020, 2020
Kristóf Bérczi, Erika R Bérczi-Kovács, Endre Boros, Fekadu Tolessa Gedefa, Naoyuki Kamiyama, Telikepalli Kavitha, Yusuke Kobayashi, Kazuhisa Makino: Envy-free Relaxations for Goods, Chores, and Mixed Items, arXiv, 2020
Kristóf Bérczi, Naonori Kakimura, Yusuke Kobayashi: Market Pricing for Matroid Rank Valuations, International Symposium on Algorithms and Computation ISAAC 2020, 2020
Kristóf Bérczi, Matthias Mnich, Roland Vincze: A 3/2-Approximation for the Metric Many-visits Path TSP, arXiv, 2020
Király Csaba: An efficient algorithm for testing (k,l)-sparsity when l<0, EGRES Quick Proof, 2019
Király Csaba, Mihálykó András: Sparse graphs and an augmentation problem, Integer Programming and Combinatorial Optimization IPCO 2020, 2020
Király Csaba, Mihálykó András: Globally rigid augmentation of minimally rigid graphs in R^2, EGRES Technical Report, 2020
Viktor Kiss, Lionel Levine, Lilla Tóthmérész: The devil's staircase for chip-firing on random graphs and on graphons, arXiv, 2020
András Frank, Gergely Hajdu: Simple algorithm and min-max formula for the inverse arborescence problem, EGRES Technical Report, 2020
András Frank, Kazuo Murota: A Discrete Convex Min-Max Formula for Box-TDI Polyhedra, EGRES Technical Report, 2020
V.E. Kaszanitzky, B. Schulze, S. Tanigawa: Global rigidity of periodic graphs under fixed-lattice representations, Journal of Combinatorial Theory, Series B, 2021
Csaba Király: Rigid realizations of graphs with few locations in the plane, Eur. J. Comb., 2021
Király Cs., Mihálykó A.: Sparse Graphs and an Augmentation Problem, Math. Program. (B), 2021
Király Cs., Mihálykó A.: Globally Rigid Augmentation of Minimally Rigid Graphs in R^2, Calamoneri T., Corò F. (eds) Algorithms and Complexity. CIAC 2021, 2021
Kaszanitzky V.E., Király Cs., Schulze B.: Sufficient conditions for the global rigidity of periodic graphs, Disc. Comp. Geom., 2021
Király Cs., Mihálykó A: Localizable sensor networks with optimal anchor sets I.: A min-max theorem, Proc. of Developments in Computer Science, 2021
Király Cs., Mihálykó A.: Localizable sensor networks with optimal anchor sets II.: An algorithm., Proc. of Developments in Computer Science, 2021
Király Cs., Mihálykó A.: Globally rigid augmentation of rigid graphs, EGRES Technical Report No. TR-2021-04, 2021
Kristóf Bérczi, Matthias Mnich, Roland Vincze: A 3/2-Approximation for the Metric Many-visits Path TSP, ArXiv preprint, submitted to Transactions on Algorithms, 2020
Kristóf Bérczi, Tamás Schwarcz: Rainbow and monochromatic circuits and cuts in binary matroids, ArXiv preprint, submitted to Discrete Mathematics, 2020
Kristóf Bérczi, Endre Boros, Ondřej Čepek, Khaled Elbassioni, Petr Kučera, Kazuhisa Makino: Generating clause sequences of a CNF formula, Theoretical Computer Science, 2021
Roland Tóbiás, Kristóf Bérczi, Csaba Szabó, Attila G Császár: autoECART: Automatic Energy Conservation Analysis of Rovibronic Transitions, Journal of Quantitative Spectroscopy and Radiative Transfer, 2021
Kristóf Bérczi, Erika R Bérczi-Kovács, Evelin Szögi: A dual approach for dynamic pricing in multi-demand markets, ArXiv preprint, 2021
Kristóf Bérczi, Tamás Király, Yutaro Yamaguchi, Yu Yokoi: Approximation by Lexicographically Maximal Solutions in Matching and Matroid Intersection Problems, ArXiv preprint, 2021
Kristóf Bérczi, Naonori Kakimura, Yusuke Kobayashi: Market Pricing for Matroid Rank Valuations, SIAM Journal on Discrete Mathematics, 2021
Kristóf Bérczi, Tamás Schwarcz, Yutaro Yamaguchi: List coloring of two matroids through reduction to partition matroids, SIAM Journal on Discrete Mathematics, 2021
K Bérczi, E Boros, O Čepek, P Kučera, K Makino: Approximating minimum representations of key Horn functions, SIAM Journal on Computing, 2021
Kristóf Bérczi, Karthekeyan Chandrasekaran, Tamás Király, Euiwoong Lee, Chao Xu: Beating the 2-approximation factor for Global Bicut, Mathematical Programming 177, pages 291–320, 2019




 

Events of the project

  
2020-07-10 14:27:04
Résztvevők változása
2020-01-22 14:36:19
Résztvevők változása
2019-03-29 17:08:08
Résztvevők változása



Back »