 |
Here you can view and search the projects funded by NKFI since 2004
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 |
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 gráfokkal kapcsolatos optimalizálási problémák gyakran kezelhetőek matoridelméleti eszközökkel. Ezen eredmények egyik kiindulópontja Edmonds matroid metszet tétele, mely karakterizálja két matroid közös független halmazainak maximális méretét. A tétel segítségével meghatározható, hogy a két matroidnak mikor létezik közös bázisa, vagy hogy egy matroidnak mikor létezik k diszjunkt bázisa. A két probléma közös általánosítása azonban, mely k diszjunkt közös bázis létezésére kérdez rá, egyelőre megoldatlan, és már a k=2 esetben is nyitott.
A feladat fontosságát mutatja, hogy több ismert gráfelméleti és kombinatorikus sejtés megfogalmazható közös bázisok pakolásának problémájaként. Ilyen például Woodall sejtése diszjunkt vágás-lefogások pakolásáról irányított gráfokban, vagy éppen a k-fenyők pakolásának problémája adott kapacitások alatt, de Rota híres sejtése is a kérdés egy speciális esetének tekinthető. A probléma jelentősége ellenére csak kevés pozitív eredmény ismert. Ezen eredmények elsősorban elégséges feltételeket adnak diszjunkt közös bázisok létezésére, vagy matroidok egy-egy speciális osztályára adnak karakterizációt.
Kutatásunk célja a probléma egy más irányú megközelítése. Olyan nem-triviális szükséges feltételeket szeretnénk meghatározni, melyek együttesen közelebb vihetnek az általános eset megoldásához. A kutatási tervben részletesen ismertetjük azon kérdéseket és területeket, melyek vizsgálata komoly előrelépést hozhat a témában. A pályázatban résztvevő kutatók eddig is folytattak matroidokhoz kapcsolódó kutatásokat, és az együttműködés során elért eredmények várhatóan fontos alkalmazásokra találnak a kombinatorikus optimalizálás több területén is.
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.
Matroidok, vagy általánosabban, szubmoduláris áramok segítségével hatékony algoritmusok adhatóak diszkrét optimalizálási feladatokra. Bizonyos problémák azonban még ezen absztrakt eszközök segítségével sem kezelhetőek. Nem alkalmazhatóak például a megszokott poliéderes technikák azon esetekben, mikor az elemszám-optimalizálási változat megoldható, ugyanakkor a súlyozott változat már nehéz. De még ezen kérdések jó része is megválaszolható szupermoduláris fedési tételek segítségével.
Kutatásaink a matroidelmélet egy olyan központi kérdésére összpontosulnak, melyet ezidáig nem sikerült beilleszteni a korábbi absztrakt modellek egyikébe sem. A kérdésnek több megfogalmazása és változata létezik, mi elsősorban két matroid k diszjunk közös bázisának létezését szeretnénk vizsgálni. Viszonylag kevés pozitív eredmény ismert a témához kapcsolódóan, és ezek többsége elégséges feltételt ad a kérdéses bázis-pakolás létezésére.
A kutatási terv azon ígéretes kérdéseket, ötleteket és lehetséges irányokat foglalja össze, melyek eddigi vizsgálataink során felmerültek. Egy nemrég tett megfigyelésünkből kiindulva, miszerint a Hermite-tétel bizonyos esetekben magyarázatot ad a megoldás hiányára, elsősorban olyan nem triviális szükséges feltételek megfogalmazását tűztük ki célul, melyek együttesen közelebb vihetnek az általános eset megoldásához. Ehhez kapcsolódóan vizsgálni szeretnénk fenyők, fokszámkorlátos fák és vágáslefogások pakolását, hipergráfok fejdiszjunkt irányításait, valamint a merevségelméleti problémákat.
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!
A kutatási terv olyan kombinatorikus optimalizálási problémák vizsgálatát tűzi ki célul, melyek közelebb vihetnek minket a kombinatorikus optimalizálás egyik fontos kérdésének, matroidok közös bázisainak pakolásának a megoldásához. A feladat nehézsége abból fakad, hogy nem kezelhető a már ismert szubmoduláris és poliéderes eszközök segítségével.
Absztrakt volta ellenére a problémával kapcsolatos bármilyen eredmény jelentős előrelépés lenne, hiszen több gráfelméleti probléma megfogalmazható a kérdés speciális eseteként. A fenyők pakolásának vizsgálatát például az elméleti fontossága mellett gyakorlati szempontok is motiválják, hiszen a fenyőkkel kapcsolatos eredmények lényeges eszközök vezetékes és vezeték nélküli telekommunikációs hálózatok tervezésénél. A kutatás tervben áttekintést adunk azon problémákról, melyek vizsgálata a kutatás elsődleges, rövidtávú célja. Hosszútávú célunk ezen eredményekből kiindulva olyan absztrakt szükségességi feltételek meghatározása, melyek előrelépést jelentenek az általános eset mögötti matematikai struktúra mélyebb megértésében.
A témavezető mellett a kutatáshoz három fiatal és egy szenior kutató is csatlakozik. A résztvevők a témához kapcsolódó területeken szerzett szerteágazó tapasztalatainak egyeítésével célunk olyan eredmények igazolása, melyek fontos alkalmazásokra találhatnak a kombinatorikus optimalizálás több területén is. A tervezett kutatáshoz erős hátteret biztosít az Operációkutatási Tanszéken működő MTA-ELTE Egerváry Kutatócsoport (EGRES). A kutatócsoportban dolgozó diákok, fiatal és szenior kutatók részvételével heti rendszerességgel zajló EGRES szeminárium kiváló fórum az elért eredmények folyamatos prezentálására és megvitatására, míg azok gyors publikálása EGRES Technical Report-ként (ISSN 1587-4451) lehetséges.
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 matroidelmélet a vektorok kapcsán jól ismert lineáris függetlenség és összefüggőség fogalmát próbálja absztrakt módon általánosítani. Matroid alatt olyan nem üres halmazrendszert értünk, mely egyrészt leszálló (azaz a rendszer tetszőleges X elemére annak minden részhalmaza a rendszerben van), másrészt bármely két eltérő méretű elemét véve a kisebbik halmaz kibővíthető a nagyobból úgy, hogy a bővített halmaz szintén a rendszerhez tartozik. Ezen halmazrendszer elemeit független halmazoknak nevezzük, míg a maximális méretü független halmazok a matroid bázisai.
Annak ellenére, hogy egy nagyon absztrakt fogalomról van szó, a matroidoknak rengeteg alkalmazása ismert a gráfelméletben, geometriában, vagy akár az áramkörök analízisében. Ez elsősorban annak köszönhető, hogy több matroid-optimalizálási feladatra ismert hatékony algoritmus. Így ha egy problémáról sikerül megmutatni, hogy a hátterérben álló struktúra matroidot alkot, akkor ezen algoritmusok direkt módon alkalmazhatóak.
Kutatásunk egy olyan matroidelméleti problémára koncentrál, melyre még nem ismert ilyen hatékony algoritmus. A probléma lényege a következő: két matroidnak keressük k páronként diszjunkt közös bázisát. Ez a látszólag egyszerű kérdés már a k=2 esetben is nyitott, és jelentőségét mutatja, hogy több ismert nyitott sejtés megfogalmazható ilyen formában. 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. Célunk a kérdés minél általánosabb formában történő megválaszolása.
| Summary Summary of the research and its aims for experts
Describe the major aims of the research for experts.
Various graph characterization and optimization problems can be treated conveniently by applying the basic tools of matroid theory. One of the most powerful results is due to Edmonds who gave a min-max characterization for the maximum size of common independent sets of two matroids. Edmonds' theorem can be used for characterizing the existence of a common basis in the intersection of two matroids, or to decide if a matroid has k pairwise disjoint bases. However, the common generalization of these two problems, namely finding k pairwise disjoint common bases of two matroids, remains open even for k=2.
The importance of packing disjoint bases is supported by the fact that several well-known graph theoretic conjectures can be formulated as special cases, such as Woodall’s conjecture on disjoint packing of dijoins, the capacitated packing of k-arborescences, or Rota’s conjecture. Finding sufficient conditions is well-investigated, and characterizations were given for special classes of matroids.
The project aims at identifying first further special cases of the problem that are efficiently solvable, and, by following a different approach than previous results, formulating non-trivial necessary conditions for the existence of disjoint common bases in the intersection of two matroids. The research plan gives a detailed list of promising questions and ideas that could give new insights into the mathematical structures behind the problem. The investigation of these problems would have significant impact in matroid theory.
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.
Matroid theory, or more generally, submodular flows provide a basic tool to treat conveniently various discrete optimization problems. A common feature of these problems is the polyhedral background which implies that the weighted (or minimum cost) versions are typically also tractable. Although pretty natural graph optimization problems are known in which the minimum cardinality case was shown to be polynomially solvable while the weighted version turned out to be NP-complete, these problems are still often solvable using supermodular coverings.
The research proposal focuses on central question of matroid theory that does not seem to fit in any of the previous abstract frameworks. There are several apparently analogous questions to be considered, we mainly concentrate on the existence of k disjoint common bases of two matroids. There are only a few positive results, mostly giving sufficient conditions for the existence of the required bases.
The research plan gives a detailed list of promising questions and ideas that could give new insights into the mathematical structures behind the problem. Starting from a recent observation that Hermite’s theorem on integer solutions of linear systems explains the lack of solution in certain cases, we would like to give non-trivial necessary conditions that could help us in solving the general case as well. The list of topics to be investigated includes the packing of arborescences, degree-prescribed trees and disjoins, as well as head-disjoint orientations of hypergraphs and problems from rigidity theory.
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.
The proposal aims at examining combinatorial optimization problems whose understanding would mean a significant step toward the solution of one of the most intriguing questions in matroid theory, the problem of packing disjoint common bases in two matroids. The difficulty of the basis packing problem is cased by the fact that it does not seem to fit in any of the previous abstract frameworks.
The research is motivated by the wide list of graph theoretic problems that can be formulated as special cases. For example, results on packing arborescences may be useful in practice as well as arborescences are basic tools in the design of communication networks, both wired and wireless. The short term impact of the research would be the solution of the problems presented in the research plan. For the long term, we would like to determine abstract sufficient conditions for the existence of k disjoint common bases, thus providing a deeper understanding of the mathematical structure behind the problem.
Besides the PI, the project will be joined by three young researchers and a senior researcher, too. The aim of the joint work is to obtain interesting results that will have significant impact in the corresponding areas. The MTA-ELTE Egerváry Research Group, affiliated with the Department of Operations Research, means a strong background for the research process. The EGRES weekly seminar provides a great opportunity to present the results and to discuss with other students, young and senior researchers. The fast dissemination of the results is also achieved through publication in the EGRES Technical Report series of the Egerváry Research Group (ISSN 1587-4451).
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.
Matroid theory serves as an abstract generalization of the notion of linear independence and dependence in vector spaces. Informally, a matroid is a non-empty set family which is hereditary (that is, if a set X is member of the family then so are all of its subsets), and for any two members of the family with different cardinalities, the smaller set can be extended from the larger one in such a way that the resulting set is also member of the family. The members of the family are called independent, while inclusionwise maximal independent sets are called the bases of the matroid.
Despite their abstract nature, matroids are widely used in graph theory, geometry and even in the analysis of electrical circuits. This is due to the fact that efficient algorithms were given for several matroid-optimization problems. If a the structure of a problem turns out to form a matroid, these algorithms can be directly applied and provide a solution.
The research proposal focuses on the following unsettled matroid-optimization problem: given two matroids, find k pairwise disjoint common bases. This simple-looking problem is open even for k=2. However, its importance is indicated by the wide list of graph theoretic conjectures that can be formulated as special cases. The goal of the project is to obtain new insights into the mathematical structures behind these problems, and use them for making progress in the general case as well.
|
|
|
|
|
|
|
|
| |
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 |
|
|
|
|
|
|
|
|
|
