Publications

Preprints

  1. K. Bérczi, T. Király, Y. Yamaguchi, Y. Yokoi, Rainbow Arborescence Conjecture, arXiv:2412.15457, 2024. arXiv
  2. K. Bérczi, V. Livanos, J. Soto, V. Verdugo, Matroid secretary via labeling schemes, arXiv:2411.12069 (2024). arXiv
  3. 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
  4. K. Bérczi, Á. Jánosik, B. Mátravölgyi, Cyclic ordering of split matroids, arXiv:2411.01061 (2024). arXiv
  5. K. Bérczi, T. Király, D. P. Szabo, Multiway Cuts with a Choice of Representatives, arXiv:2407.03877, 2024. arXiv Proceedings
  6. K. Bérczi, T. Király, Y. Yamaguchi, Y. Yokoi, Matroid Intersection under Minimum Rank Oracle, arXiv:2407.03229, 2024. arXiv
  7. 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
  8. K. Bérczi, M. Borbényi, L. Lovász, L. M. Tóth, Quotient-convergence of Submodular Setfunctions, arXiv:2406.08942, 2024. arXiv
  9. K. Bérczi, B. Gehér, A. Imolay, L. Lovász, T. Schwarcz, Monotonic Decompositions of Submodular Set Functions, arXiv:2406.04728, 2024. arXiv
  10. K. Bérczi, K. Chandrasekaran, T. Király, S. Kulkarni, Hypergraph Connectivity Augmentation in Strongly Polynomial Time, arXiv:2402.10861, 2024. arXiv Proceedings
  11. Y. Bai, K. Bérczi, G. Csáji, T. Schwarcz, Approximating maximum-size properly colored forests, arXiv:2402.00834, 2024. arXiv Proceedings
  12. K. Bérczi, B. Mátravölgyi, T. Schwarcz, Reconfiguration of basis pairs in regular matroids, arXiv:2311.07130, 2023. arXiv Proceedings
  13. K. Bérczi, K. Chandrasekaran, T. Király, S. Kulkarni, Splitting-off in Hypergraphs, arXiv:2307.08555, 2023. arXiv Proceedings
  14. 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

  1. K. Bérczi, T. Király, Y. Kobayashi, Y. Yamaguchi, Y. Yokoi, Finding Spanning Trees with Perfect Matchings, Discrete Applied Mathematics (2025). arXiv Journal
  2. K. Bérczi, L. Codazzi, J. Golak, A. Grigoriev, Envy-free dynamic pricing schemes, Operations Research, 2025. arXiv Journal
  3. 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
  4. 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
  5. 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
  6. K. Bérczi, E. Boros, M. Kazuhisa, Hypergraph Horn functions, SIAM Journal on Discrete Mathematics, 38(2), pp. 1417-1437, 2024. arXiv Journal
  7. 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
  8. 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
  9. K. Bérczi, E. Boros, M. Kazuhisa, Matroid Horn functions, Journal of Combinatorial Theory A, 203, 2024. arXiv Journal
  10. 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
  11. K. Bérczi, T. Schwarcz, Partitioning into common independent sets via relaxing strongly base orderability, Journal of Combinatorial Theory A, 202, 2024. arXiv Journal
  12. 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
  13. 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
  14. 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
  15. 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
  16. 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
  17. 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
  18. K. Bérczi, M. Mnich, and R. Vincze, Approximations for many-visits multiple traveling salesman problems, Omega, 116, 2023. arXiv Journal
  19. 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
  20. 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
  21. 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
  22. 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
  23. 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
  24. K. Bérczi and T. Schwarcz, Rainbow and monochromatic circuits and cocircuits in binary matroids, Discrete Mathematics, vol. 345, no. 6, 2022. arXiv Journal
  25. 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
  26. 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
  27. 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
  28. 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
  29. 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
  30. K. Bérczi and T. Schwarcz, Complexity of packing common bases in matroids, Mathematical Programming, pp. 1-18, 2020. arXiv Journal
  31. 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
  32. 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
  33. 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
  34. 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
  35. 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
  36. 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
  37. 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
  38. 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
  39. 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
  40. 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
  41. 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
  42. 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
  43. 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
  44. 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
  45. 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
  46. 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
  47. K. Bérczi, A. Bernáth, and M. Vizer, Regular graphs are antimagic, Electronic Journal of Combinatorics, vol. 22, no. 3, 2015. arXiv Journal
  48. 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
  49. K. Bérczi and A. Frank, Packing arborescences, Combinatorial Optimization and Discrete Algorithms, RIMS Kôkyûroku Bessatsu B23, pp. 1-31, 2010. Journal
  50. 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

  1. 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).
  2. K. Bérczi, V. Livanos, J. Soto, V. Verdugo, Matroid secretary via labeling schemes, 26th Conference on Integer Programming and Combinatorial Optimization (IPCO 2025).
  3. 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
  4. K. Bérczi, K. Chandrasekaran, T. Király, S. Kulkarni, Hypergraph Connectivity Augmentation in Strongly Polynomial Time, European Symposium on Algorithms (ESA 2024). Proceedings
  5. Y. Bai, K. Bérczi, G. Csáji, T. Schwarcz, Approximating maximum-size properly colored forests, European Symposium on Algorithms (ESA 2024). Proceedings
  6. 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
  7. 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
  8. 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
  9. 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).
  10. 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
  11. 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
  12. 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.
  13. 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
  14. 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
  15. 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
  16. 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
  17. 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
  18. 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.
  19. 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.
  20. 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
  21. 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

  1. K. Bérczi, Matroid Products via Submodular Coupling, KTH Combinatorics Seminar, KTH Royal Institute of Technology, Stockholm (March 2025).
  2. K. Bérczi, Packing and covering problems in matroids, 20th Summer School in Discrete Mathematics, Vina del Mar (Jan. 2025).
  3. K. Bérczi, Approximability of multiway cut, Mixed Integer Programming International Workshop, IIT, Mumbai (Dec. 2024)
  4. K. Bérczi, Matroid reconfiguration problems, Bremen Workshop on Combinatorial Reconfiguration and Beyond, UB, Bremen (Nov. 2024).
  5. K. Bérczi, Matroid products via submodular coupling, HUN-REN Rényi Institute, Budapest (Nov. 2024).
  6. K. Bérczi, Relaxing strongly base orderability for matroids, Colloquium of Faculty of Informatics, Brno (Oct. 2024).
  7. K. Bérczi, Dynamic prices and 2-polymatroids, University of Chile (Jan. 2024).
  8. K. Bérczi, Reconfiguration of basis pairs in regular matroids, Seminar on Combinatorics, Games and Optimisation, London School of Economics (Dec. 2023).
  9. 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).
  10. K. Bérczi, Matroid Horn functions, Boolean Seminar, Liblice (Sept. 2023).
  11. K. Bérczi, Reduction of Matroids and Its Application to Optimization Problems, SIAM Conference on Optimization, Seattle (June 2023).
  12. K. Bérczi, Newton-type algorithms in inverse optimization, CIAS-CCOR Optimization Seminar, Budapest (May 2023).
  13. K. Bérczi, Supermodularity in unweighted graph optimization: Algorithms, Combinatorial Optimization Seminar, Grenoble (Apr. 2023).
  14. K. Bérczi, Exchange distance of basis pairs, RIMS, Kyoto (Jan. 2023).
  15. K. Bérczi, Paths consisting of short edges of the matroid intersection polytope, Eleventh Cargese Workshop on Combinatorial Optimization (Sept. 2022).
  16. 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).
  17. K. Bérczi, Exchange distance in split matroids, KTH Combinatorics Seminar, KTH Royal Institute of Technology, Stockholm (Apr. 2022).
  18. K. Bérczi, Structural properties of matroid base families, Trimester Program on Discrete Optimization, Hausdorff Research Institute for Mathematics, Bonn (Nov. 2021).
  19. K. Bérczi, Dynamic pricing in combinatorial markets, Game Theory Seminar, Corvinus University, Budapest (Oct. 2021).
  20. K. Bérczi, Supermodularity in unweighted graph optimization, International Workshop on Combinatorial Optimization and Algorithmic Game Theory, RIMS, Kyoto (Jan. 2020).
  21. K. Bérczi, Complexity of packing common bases, Bellairs Workshop on Discrete Optimization, BRI, Barbados (Apr. 2019).
  22. K. Bérczi, Matroidal maximum term rank, Combinatorial Geometries: matroids, oriented matroids and applications, CIRM, Marseille (Sept. 2018).
  23. K. Bérczi, Degree-sequences of highly-connected simple digraphs, Current Trends in Combinatorial Optimization, NII, Shonan (May 2016).
  24. K. Bérczi, From Digraphs to Dypergraphs: Paths and Arborescences, Horn formulas, directed hypergraphs, lattices and closure systems, LZI, Dagstuhl (May 2014).
  25. K. Bérczi, Restricted $b$-matchings, Discrete Convexity and Optimization, RIMS, Kyoto (Oct. 2012).
  26. K. Bérczi, Restricted b-matchings, 21st International Symposium on Mathematical Programming, TU, Berlin (Aug. 2012).

Book chapters

  1. 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

  1. 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

  1. 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

  1. K. Bérczi, Arborescence packing and restricted b-matchings, PhD thesis, Eötvös Loránd University, Budapest, 2013.
  2. K. Bérczi, Packings and coverings in directed graphs, Master thesis, Eötvös Loránd University, Budapest, 2008.