Publications
Preprints
- K. Bérczi, T. Király, Y. Yamaguchi, Y. Yokoi, Rainbow Arborescence Conjecture, arXiv:2412.15457, 2024. arXiv
- K. Bérczi, V. Livanos, J. Soto, V. Verdugo, Matroid secretary via labeling schemes, arXiv:2411.12069 (2024). arXiv
- K. Bérczi, B. Gehér, A. Imolay, L. Lovász, B. Maga, T. Schwarcz, Matroid products via submodular coupling, arXiv:2411.02197 (2024). arXiv
- K. Bérczi, Á. Jánosik, B. Mátravölgyi, Cyclic ordering of split matroids, arXiv:2411.01061 (2024). arXiv
- K. Bérczi, T. Király, D. P. Szabo, Multiway Cuts with a Choice of Representatives, arXiv:2407.03877, 2024. arXiv Proceedings
- K. Bérczi, T. Király, Y. Yamaguchi, Y. Yokoi, Matroid Intersection under Minimum Rank Oracle, arXiv:2407.03229, 2024. arXiv
- K. Bérczi, M. Borbényi, L. Lovász, L. M. Tóth, Cycle Matroids of Graphings: From Convergence to Duality, arXiv:2406.08945, 2024. arXiv
- K. Bérczi, M. Borbényi, L. Lovász, L. M. Tóth, Quotient-convergence of Submodular Setfunctions, arXiv:2406.08942, 2024. arXiv
- K. Bérczi, B. Gehér, A. Imolay, L. Lovász, T. Schwarcz, Monotonic Decompositions of Submodular Set Functions, arXiv:2406.04728, 2024. arXiv
- K. Bérczi, K. Chandrasekaran, T. Király, S. Kulkarni, Hypergraph Connectivity Augmentation in Strongly Polynomial Time, arXiv:2402.10861, 2024. arXiv Proceedings
- Y. Bai, K. Bérczi, G. Csáji, T. Schwarcz, Approximating maximum-size properly colored forests, arXiv:2402.00834, 2024. arXiv Proceedings
- K. Bérczi, B. Mátravölgyi, T. Schwarcz, Reconfiguration of basis pairs in regular matroids, arXiv:2311.07130, 2023. arXiv Proceedings
- K. Bérczi, K. Chandrasekaran, T. Király, S. Kulkarni, Splitting-off in Hypergraphs, arXiv:2307.08555, 2023. arXiv Proceedings
- K. Bérczi, A. Göke, L. M. Mendoza-Cadena, M. Mnich, Resolving Infeasibility of Linear Systems: A Parameterized Approach, arXiv:2209.02017, 2022. arXiv
Journal articles
- K. Bérczi, T. Király, Y. Kobayashi, Y. Yamaguchi, Y. Yokoi, Finding Spanning Trees with Perfect Matchings, Discrete Applied Mathematics (2025). arXiv Journal
- K. Bérczi, L. Codazzi, J. Golak, A. Grigoriev, Envy-free dynamic pricing schemes, Operations Research, 2025. arXiv Journal
- K. Bérczi, L. M. Mendoza-Cadena, K. Varga, Newton-type algorithms for inverse optimization: weighted bottleneck Hamming distance and $\ell_\infty$-norm objectives, Optimization Letters, 2025. arXiv Journal
- K. Bérczi, L. M. Mendoza-Cadena, On the Complexity of Inverse Bivariate Multi-unit Assignment Valuation Problems, Optimization, pp. 1-16, 2024. arXiv Journal
- K. Bérczi, G. K. Csáji, T. Király, Manipulating the outcome of stable matching and roommates problems, Games and Economic Behavior, 147, pp. 407-428, 2024. arXiv Journal
- K. Bérczi, E. Boros, M. Kazuhisa, Hypergraph Horn functions, SIAM Journal on Discrete Mathematics, 38(2), pp. 1417-1437, 2024. arXiv Journal
- K. Bérczi, T. Király, S. Omlor, Scheduling with non-renewable resources: Minimizing the sum of completion times, Journal of Scheduling, 27, pp. 151-164, 2024. arXiv Journal Proceedings
- K. Bérczi, B. Mátravölgyi, T. Schwarcz, Weighted exchange distance of basis pairs, Discrete Applied Mathematics, 349, pp. 130-143, 2024. arXiv Journal
- K. Bérczi, E. Boros, M. Kazuhisa, Matroid Horn functions, Journal of Combinatorial Theory A, 203, 2024. arXiv Journal
- K. Bérczi, T. Schwarcz, Exchange distance of basis pairs in split matroids, SIAM Journal on Discrete Mathematics, 38(1), pp. 132-147, 2024. arXiv Journal
- K. Bérczi, T. Schwarcz, Partitioning into common independent sets via relaxing strongly base orderability, Journal of Combinatorial Theory A, 202, 2024. arXiv Journal
- K. Bérczi, E. R. Bérczi-Kovács, E. Boros, F. G. Tolessa, N. Kamiyama, K. Telikepalli, Y. Kobayashi, and K. Makino, Envy-free relaxations for goods, chores, and mixed items, Theoretical Computer Science, 1002:114596, 2024. arXiv Journal
- K. Bérczi, H. P. Hoang, L. Tóthmérész, On approximating the rank of graph divisors, Discrete Mathematics, 346(9), 2023. arXiv Journal
- K. Bérczi, E. R. Bérczi-Kovács, and E. Szögi, A dual approach for dynamic pricing in multi-demand markets, SIAM Journal on Discrete Mathematics, 37(3), pp. 1771-1787, 2023. arXiv Journal
- K. Bérczi, T. Király, Y. Yamaguchi, and Y. Yokoi, Matroid intersection under restricted oracles, SIAM Journal on Discrete Mathematics, 37(2), pp. 1311-1330, 2023. arXiv Journal
- K. Bérczi, G. K. Csáji, T. Király, On the complexity of packing rainbow spanning trees, Discrete Mathematics, 346(4), 2023. arXiv Journal
- K. Bérczi, L. M. Mendoza-Cadena, K. Varga, Inverse optimization problems with multiple weight functions, Discrete Applied Mathematics, 327, pp. 134-147, 2023. arXiv Journal
- K. Bérczi, M. Mnich, and R. Vincze, Approximations for many-visits multiple traveling salesman problems, Omega, 116, 2023. arXiv Journal
- K. Bérczi, K. Chandrasekaran, T. Király, and A. Pillai, Analyzing Residual Random Greedy for monotone submodular maximization, Information Processing Letters, 180, 2023. Journal
- K. Bérczi, T. Király, T. Schwarcz, Y. Yamaguchi, Y. Yokoi, Hypergraph characterization of split matroids, Journal of Combinatorial Theory, Series A, 194, 2023. arXiv Journal
- K. Bérczi, M. Mnich, and R. Vincze, A 3/2-approximation for the metric Many-visits Path TSP, SIAM Journal on Discrete Mathematics, 36(4), 2022. arXiv Journal
- K. Bérczi, E. Boros, O. Čepek, P. Kučera, and M. Kazuhisa, Unique key Horn functions, Theoretical Computer Science, 922, pp. 170-178, 2022. arXiv Journal
- K. Bérczi, T. Király, Y. Yamaguchi, and Y. Yokoi, Approximation by lexicographically maximal solutions in matching and matroid intersection problems, Theoretical Computer Science, vol. 910, pp. 48-53, 2022. arXiv Journal
- K. Bérczi and T. Schwarcz, Rainbow and monochromatic circuits and cocircuits in binary matroids, Discrete Mathematics, vol. 345, no. 6, 2022. arXiv Journal
- K. Bérczi, E. Boros, O. Čepek, P. Kučera, and K. Makino, Approximating minimum representations of key Horn functions, SIAM Journal on Computing, vol. 51, no. 1, pp. 116-138, 2022. arXiv Journal
- K. Bérczi, N. Kakimura, and Y. Kobayashi, Market pricing for matroid rank valuations, SIAM Journal on Discrete Mathematics, 35(4), pp. 2662-2678, 2021. arXiv Journal Proceedings
- K. Bérczi, T. Schwarcz, and Y. Yamaguchi, List colouring of two matroids through reduction to partition matroids, SIAM Journal on Discrete Mathematics, vol. 35, no. 3, pp. 2192-2209, 2021. arXiv Journal
- R. Tóbiás, K. Bérczi, Cs. Szabó, and A. G. Császár, autoECART: Automatic Energy Conservation Analysis of Rovibronic Transitions, Journal of Quantitative Spectroscopy and Radiative Transfer, vol. 272, 2021. Journal
- K. Bérczi, E. Boros, O. Čepek, K. Elbassioni, P. Kučera, and K. Makino, Generating clause sequences of a CNF formula, Theoretical Computer Science, vol. 856, pp. 68-74, 2021. arXiv Journal
- K. Bérczi and T. Schwarcz, Complexity of packing common bases in matroids, Mathematical Programming, pp. 1-18, 2020. arXiv Journal
- K. Bérczi, K. Chandrasekaran, T. Király, and V. Madan, A tight √2-approximation for linear 3-cut, Mathematical Programming, vol. 184, no. 1-2, pp. 411-443, 2020. Journal Proceedings
- K. Bérczi, K. Chandrasekaran, T. Király, and V. Madan, Improving the integrality gap for multiway cut, Mathematical Programming, vol. 183, no. 1-2, pp. 171-193, 2020. arXiv Journal Proceedings
- K. Bérczi, Z. Király, C. Liu, and I. Miklós, Packing tree degree sequences, Informatica – Journal of Computing and Informatics, vol. 43, no. 1, pp. 11-17, 2019. arXiv Journal
- K. Bérczi, K. Chandrasekaran, T. Király, E. Lee, and C. Xu, Beating the 2-approximation factor for global bicut, Mathematical Programming, vol. 177, no. 1-2, pp. 291-320, 2019. Journal
- K. Bérczi and A. Frank, Supermodularity in unweighted graph optimization I: Branchings and matchings, Mathematics of Operations Research, vol. 43, no. 3, pp. 726-753, 2018. arXiv Journal
- K. Bérczi and A. Frank, Supermodularity in unweighted graph optimization II: Matroidal term rank augmentation, Mathematics of Operations Research, vol. 43, no. 3, pp. 754-762, 2018. arXiv Journal
- K. Bérczi and A. Frank, Supermodularity in unweighted graph otimization III: Highly connected digraphs, Mathematics of Operations Research, vol. 43, no. 3, pp. 763-780, 2018. arXiv Journal
- K. Bérczi, A. Jüttner, M. Laumanns, and J. Szabó, Arrival time dependent routing policies in public transport, Discrete Applied Mathematics, vol. 251, pp. 93-102, 2018. Journal
- K. Bérczi, A. Bernáth, T. Király, and Gy. Pap, Blocking optimal structures, Discrete Mathematics, vol. 341, no. 7, pp. 1864-1872, 2018. Journal
- K. Bérczi, S. Iwata, J. Kato, and Y. Yamaguchi, Making bipartite graphs DM-irreducible, SIAM Journal on Discrete Mathematics, vol. 32, no. 1, pp. 560-590, 2018. Journal
- K. Bérczi, A. Jüttner, M. Laumanns, and J. Szabó, Stochastic route planning in public transport, Transportation Research Procedia, vol. 27, pp. 1080-1087, 2017. Journal Patent
- K. Bérczi and E. R. Bérczi-Kovács, Directed hypergraphs and Horn minimization, Information Processing Letters, vol. 128, pp. 32-37, 2017. Journal
- K. Bérczi and A. Joó, King-serf duo by monochromatic paths in k-edge-coloured tournaments, Electronic Journal of Combinatorics, vol. 24, no. 1, 2017. Journal
- K. Bérczi and Y. Kobayashi, An algorithm for identifying cycle-plus-triangles graphs, Discrete Applied Mathematics, vol. 226, no. C, pp. 10-16, 2017. Journal
- K. Bérczi, A. Bernáth, and M. Vizer, A note on V-free 2-matchings, Electronic Journal of Combinatorics, vol. 23, no. 4, 2016. arXiv Journal
- K. Bérczi, T. Király, and Y. Kobayashi, Covering intersecting bi-set families under matroid constraints, SIAM Journal on Discrete Mathematics, vol. 30, no. 3, pp. 1758-1774, 2016. Journal
- K. Bérczi, A. Bernáth, and M. Vizer, Regular graphs are antimagic, Electronic Journal of Combinatorics, vol. 22, no. 3, 2015. arXiv Journal
- K. Bérczi and Y. Kobayashi, An Algorithm for (n-3)-connectivity augmentation problem: Jump system approach, Journal of Combinatorial Theory B, vol. 102, no. 3, pp. 565-587, 2012. Journal
- K. Bérczi and A. Frank, Packing arborescences, Combinatorial Optimization and Discrete Algorithms, RIMS Kôkyûroku Bessatsu B23, pp. 1-31, 2010. Journal
- K. Bérczi, S. Fujishige, and N. Kamiyama, A linear-time algorithm to find a pair of arc-disjoint spanning in-arborescence and out-arborescence in a directed acyclic graph, Information Processing Letters vol. 109, no. 23-24, pp. 1227-1231, 2009. Journal
Conference proceedings
- K. Bérczi, B. Gehér, A. Imolay, L. Lovász, B. Maga, T. Schwarcz, Matroid products via submodular coupling, 57th Annual ACM Symposium on Theory of Computing (STOC 2025).
- K. Bérczi, V. Livanos, J. Soto, V. Verdugo, Matroid secretary via labeling schemes, 26th Conference on Integer Programming and Combinatorial Optimization (IPCO 2025).
- K. Bérczi, T. Király, D. Szabó, Multiway Cuts with a Choice of Representatives, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Proceedings
- K. Bérczi, K. Chandrasekaran, T. Király, S. Kulkarni, Hypergraph Connectivity Augmentation in Strongly Polynomial Time, European Symposium on Algorithms (ESA 2024). Proceedings
- Y. Bai, K. Bérczi, G. Csáji, T. Schwarcz, Approximating maximum-size properly colored forests, European Symposium on Algorithms (ESA 2024). Proceedings
- K. Bérczi, K. Chandrasekaran, T. Király, S. Kulkarni, Splitting-off in Hypergraphs, 51st EATCS International Colloquium on Automata, Languages and Programming (ICALP 2024). Proceedings
- K. Bérczi, B. Mátravölgyi, T. Schwarcz, Reconfiguration of basis pairs in regular matroids, 56th Annual ACM Symposium on Theory of Computing (STOC 2024). Proceedings
- K. Bérczi, L. M. Mendoza-Cadena, K. Varga, Newton-type algorithms for inverse optimization: weighted span objective, Latin American Theoretical Informatics (LATIN 2024). Proceedings
- K. Bérczi, E. R. Bérczi-Kovács, and E. Szögi, A dual approach for dynamic pricing in multi-demand markets, International Workshop on Matching Under Preferences (MATCH-UP 2022).
- K. Bérczi, N. Kakimura, and Y. Kobayashi, Market pricing for matroid rank valuations, In 31st International Symposium on Algorithms and Computation (ISAAC 2020), pp. 1-15, Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020. Proceedings
- K. Bérczi, T. Király, and S. Omlor, Scheduling with non-renewable resources: Minimizing the sum of completion times, In 6th International Symposium on Combinatorial Optimization (ISCO 2020), pp. 167-178, 2020. Proceedings
- K. Bérczi, E. Boros, O. Čepek, P. Kučera, and K. Makino, Approximating minimum representations of key Horn functions, In 16th International Symposium on Artificial Intelligence and Mathematics (ISAIM 2020), pp. 1-8, 2020.
- K. Bérczi, K. Chandrasekaran, T. Király, and V. Madan, Improving the integrality gap for multiway cut, In Integer Programming and Combinatorial Optimization (IPCO 2019), pp. 115-127, 2019. Proceedings
- K. Bérczi, K. Chandrasekaran, T. Király, and V. Madan, A tight $\sqrt(2)$-approximation for linear 3-cut, In 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), pp. 1393-1406, 2018. Proceedings
- J. Yalluoz, J. Tapolcai, A. Kőrösi, K. Bérczi, L. Gyimóthi, and A. Orda, Packing strictly-shortest paths in a tree for QoS-aware routing, In 2017 IFIP Networking Conference (IFIP Networking) and Workshops, pp. 1-9, IEEE, 2017. Proceedings
- K. Bérczi and Y. Kobayashi, The directed disjoint shortest paths problem, In 25th Annual European Symposium on Algorithms (ESA 2017), pp. 13:1-13:13, 2017. Proceedings
- K. Bérczi, C. Karthekeyan, T. Király, E. Lee, and X. Chao, Global and fixed-terminal cuts in digraphs, In 20th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX’ 2017), pp. 2:1-2:20, 2017. Proceedings
- K. Bérczi, Z. Király, C. Liu, and I. Miklós, Packing tree degree sequences. In Middle-European Conference on Applied Theoretical Computer Science, pp. 61-64, 2016.
- T. Király, A. Bernáth, L. A. Végh, L. Bajzik, E. R. Kovács, K. Bérczi, A. Jüttner, and T. Jordán, Worst case bin packing for OTN electrical layer networks dimensioning. In 13th International Conference on Transparent Optical Networks (ICTON 2011), pp. 43-49, 2011.
- Z. Lakatos, L. Bajzik, T. Kárász, K. Bérczi, E. R. Kovács, and L. A. Végh, ILP based diverse path routing with node inclusion, In 3rd International Workshop on Reliable Networks Design and Modeling (RNDM 2011) co-located with 3rd international congress on ultra modern telecommunications and control systems and workshops (ICUMT 2011), pp. 750-758, 2011. Proceedings
- K. Bérczi and L. A. Végh, Restricted b-matchings in degree-bounded graphs, In Integer Programming and Combinatorial Optimization (IPCO 2010), pp. 43-56, 2010. Proceedings
Seminars, workshops & summer schools
- K. Bérczi, Matroid Products via Submodular Coupling, KTH Combinatorics Seminar, KTH Royal Institute of Technology, Stockholm (March 2025).
- K. Bérczi, Packing and covering problems in matroids, 20th Summer School in Discrete Mathematics, Vina del Mar (Jan. 2025).
- K. Bérczi, Approximability of multiway cut, Mixed Integer Programming International Workshop, IIT, Mumbai (Dec. 2024)
- K. Bérczi, Matroid reconfiguration problems, Bremen Workshop on Combinatorial Reconfiguration and Beyond, UB, Bremen (Nov. 2024).
- K. Bérczi, Matroid products via submodular coupling, HUN-REN Rényi Institute, Budapest (Nov. 2024).
- K. Bérczi, Relaxing strongly base orderability for matroids, Colloquium of Faculty of Informatics, Brno (Oct. 2024).
- K. Bérczi, Dynamic prices and 2-polymatroids, University of Chile (Jan. 2024).
- K. Bérczi, Reconfiguration of basis pairs in regular matroids, Seminar on Combinatorics, Games and Optimisation, London School of Economics (Dec. 2023).
- K. Bérczi, Dynamic pricing schemes in combinatorial markets, Workshop on Matroids and Applications in Combinatorial Optimization, Quantum Physics, and Statistics, KU, Leuven (Nov. 2023).
- K. Bérczi, Matroid Horn functions, Boolean Seminar, Liblice (Sept. 2023).
- K. Bérczi, Reduction of Matroids and Its Application to Optimization Problems, SIAM Conference on Optimization, Seattle (June 2023).
- K. Bérczi, Newton-type algorithms in inverse optimization, CIAS-CCOR Optimization Seminar, Budapest (May 2023).
- K. Bérczi, Supermodularity in unweighted graph optimization: Algorithms, Combinatorial Optimization Seminar, Grenoble (Apr. 2023).
- K. Bérczi, Exchange distance of basis pairs, RIMS, Kyoto (Jan. 2023).
- K. Bérczi, Paths consisting of short edges of the matroid intersection polytope, Eleventh Cargese Workshop on Combinatorial Optimization (Sept. 2022).
- K. Bérczi, A dual approach for dynamic pricing in multi-demand markets, Annual Meeting of the Canadian Society of Applied and Industrial Mathematics CAIMS (Jun. 2022).
- K. Bérczi, Exchange distance in split matroids, KTH Combinatorics Seminar, KTH Royal Institute of Technology, Stockholm (Apr. 2022).
- K. Bérczi, Structural properties of matroid base families, Trimester Program on Discrete Optimization, Hausdorff Research Institute for Mathematics, Bonn (Nov. 2021).
- K. Bérczi, Dynamic pricing in combinatorial markets, Game Theory Seminar, Corvinus University, Budapest (Oct. 2021).
- K. Bérczi, Supermodularity in unweighted graph optimization, International Workshop on Combinatorial Optimization and Algorithmic Game Theory, RIMS, Kyoto (Jan. 2020).
- K. Bérczi, Complexity of packing common bases, Bellairs Workshop on Discrete Optimization, BRI, Barbados (Apr. 2019).
- K. Bérczi, Matroidal maximum term rank, Combinatorial Geometries: matroids, oriented matroids and applications, CIRM, Marseille (Sept. 2018).
- K. Bérczi, Degree-sequences of highly-connected simple digraphs, Current Trends in Combinatorial Optimization, NII, Shonan (May 2016).
- K. Bérczi, From Digraphs to Dypergraphs: Paths and Arborescences, Horn formulas, directed hypergraphs, lattices and closure systems, LZI, Dagstuhl (May 2014).
- K. Bérczi, Restricted $b$-matchings, Discrete Convexity and Optimization, RIMS, Kyoto (Oct. 2012).
- K. Bérczi, Restricted b-matchings, 21st International Symposium on Mathematical Programming, TU, Berlin (Aug. 2012).
Book chapters
- K. Bérczi and A. Frank, Variations for Lovász’ submodular ideas. In: M. Grötschel and oth. editors, Building Bridges, vol. 19 of Bolyai Society Mathematical Studies, pp. 137-164, Springer Berlin, Heidelberg, 2008. Book
Patents
- K. Bérczi, A. Jüttner, M. Korom, L. Marco, N. Tim, and J. Szabó, Stochastic route planning in public transport, US Patent 9482542, 2016. Patent
Lecture notes
- K. Bérczi, A. Frank, V. Kaszanitzky, Cs. Király, T. Király, E. R. Kovács, Gy. Pap, and J. Pap, Operációkutatási példatár, Typotex Kiadó, Budapest, 2013. Book
Theses
- K. Bérczi, Arborescence packing and restricted b-matchings, PhD thesis, Eötvös Loránd University, Budapest, 2013.
- K. Bérczi, Packings and coverings in directed graphs, Master thesis, Eötvös Loránd University, Budapest, 2008.