Publications

Preprints

  1. K. Bérczi, K. Chandrasekaran, T. Király, S. Kulkarni, Hypergraph Connectivity Augmentation in Strongly Polynomial Time, arXiv:2402.10861, 2024.
  2. Y. Bai, K. Bérczi, G. Csáji, T. Schwarcz, Approximating maximum-size properly colored forests, arXiv:2402.00834, 2024.
  3. K. Bérczi, B. Mátravölgyi, T. Schwarcz, Reconfiguration of basis pairs in regular matroids, arXiv:2311.07130, 2023.
  4. K. Bérczi, K. Chandrasekaran, T. Király, S. Kulkarni, Splitting-off in Hypergraphs, arXiv:2307.08555, 2023.
  5. K. Bérczi, L. M. Mendoza-Cadena, K. Varga, Newton-type algorithms for inverse optimization I: weighted bottleneck Hamming distance and $\ell_\infty$-norm objectives, arXiv:2302.13411, 2023.
  6. K. Bérczi, L. M. Mendoza-Cadena, K. Varga, Newton-type algorithms for inverse optimization II: weighted span objective, arXiv:2302.13414, 2023.
  7. K. Bérczi, L. Codazzi, J. Golak, A. Grigoriev, Envy-free dynamic pricing schemes, arXiv:2301.01529, 2023.
  8. K. Bérczi, G. K. Csáji, T. Király, Manipulating the outcome of stable matching and roommates problems, arXiv:2204.13485, 2022.
  9. K. Bérczi, A. Göke, L. M. Mendoza-Cadena, M. Mnich, Resolving Infeasibility of Linear Systems: A Parameterized Approach, arXiv:2209.02017, 2022.
  10. 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, arXiv:2006.04428, 2020.

Journal articles

  1. K. Bérczi, B. Mátravölgyi, T. Schwarcz, Weighted exchange distance of basis pairs, Discrete Applied Mathematics, to appear, 2024.
  2. K. Bérczi, E. Boros, M. Kazuhisa, Hypergraph Horn functions, SIAM Journal on Discrete Mathematics, to appear, 2024.
  3. K. Bérczi, E. Boros, M. Kazuhisa, Matroid Horn functions, Journal of Combinatorial Theory A, to appear, 2023.
  4. K. Bérczi, T. Schwarcz, Partitioning into common independent sets via relaxing strongly base orderability, Journal of Combinatorial Theory A, to appear, 2023.
  5. K. Bérczi, T. Schwarcz, Exchange distance of basis pairs in split matroids, SIAM Journal on Discrete Mathematics, to appear, 2023.
  6. K. Bérczi, H. P. Hoang, L. Tóthmérész, On approximating the rank of graph divisors, Discrete Mathematics, to appear, 2023.
  7. 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, to appear, 2023.
  8. K. Bérczi, T. Király, Y. Yamaguchi, and Y. Yokoi, Matroid intersection under restricted oracles, SIAM Journal on Discrete Mathematics, to appear, 2023.
  9. K. Bérczi, G. K. Csáji, T. Király, On the complexity of packing rainbow spanning trees, Discrete Mathematics, 346(4), 2023.
  10. K. Bérczi, L. M. Mendoza-Cadena, K. Varga, Inverse optimization problems with multiple weight functions, Discrete Applied Mathematics, 327, pp. 134-147, 2023.
  11. K. Bérczi, M. Mnich, and R. Vincze, Approximations for many-visits multiple traveling salesman problems, Omega, 116, 2023.
  12. K. Bérczi, K. Chandrasekaran, T. Király, and A. Pillai, Analyzing Residual Random Greedy for monotone submodular maximization, Information Processing Letters, 180, 2023.
  13. K. Bérczi, T. Király, and S. Omlor, Scheduling with non-renewable resources: Minimizing the sum of completion times, Journal of Scheduling, to appear, 2022.
  14. 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.
  15. 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.
  16. 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.
  17. 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.
  18. K. Bérczi and T. Schwarcz, Rainbow and monochromatic circuits and cocircuits in binary matroids, Discrete Mathematics, vol. 345, no. 6, 2022.
  19. 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.
  20. 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.
  21. 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.
  22. 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.
  23. 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.
  24. K. Bérczi and T. Schwarcz, Complexity of packing common bases in matroids, Mathematical Programming, pp. 1-18, 2020.
  25. 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.
  26. 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.
  27. 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.
  28. 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.
  29. 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.
  30. 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.
  31. 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.
  32. 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.
  33. 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.
  34. 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.
  35. 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.
  36. K. Bérczi and E. R. Bérczi-Kovács, Directed hypergraphs and Horn minimization, Information Processing Letters, vol. 128, pp. 32-37, 2017.
  37. 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.
  38. 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.
  39. 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.
  40. 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.
  41. K. Bérczi, A. Bernáth, and M. Vizer, Regular graphs are antimagic, Electronic Journal of Combinatorics, vol. 22, no. 3, 2015.
  42. 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.
  43. K. Bérczi and A. Frank, Packing arborescences, Combinatorial Optimization and Discrete Algorithms, RIMS Kôkyûroku Bessatsu B23, pp. 1-31, 2010.
  44. 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.

Refereed conference proceedings

  1. 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).
  2. 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).
  3. 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.
  4. 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.
  5. 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.
  6. K. Bérczi, K. Chandrasekaran, T. Király, and V. Madan, A tight √2-approximation for linear 3-cut. In 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), pp. 1393-1406, 2018.
  7. 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.
  8. 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.
  9. 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.
  10. 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.
  11. 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.
  12. 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.
  13. 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.

Other conference proceedings

  1. K. Bérczi, G. K. Csáji, T. Király, Manipulating the outcome of stable matching and roommates problems, poster, International Workshop on Matching Under Preferences (MATCH-UP 2022).
  2. 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.
  3. K. Bérczi, A. Bernáth, T. Király, and Gy. Pap, Blocking optimal structures. In Proceedings of the 10th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, pp. 67-75, 2017.
  4. K. Bérczi and E. R. Bérczi-Kovács, Directed hypergraphs and Horn minimization. Proceedings of the 10th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, pp. 59-65, 2017.
  5. K. Bérczi, T. Király, and Y. Kobayashi, Algorithmic aspects of covering supermodular functions under matroid constraints. In Proceedings of the 9th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, pp. 301-306, 2015.
  6. K. Bérczi and A. Jüttner, Road surveillance optimization – an Asymmetric vehicle routing problem with visiting frequencies. In Proceedings of the 9th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, pp. 460-464, 2015.
  7. K. Bérczi and A. Frank, Graph optimization problems of common root. In Proceedings of the 9th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, pp. 242-266, 2015.
  8. K. Bérczi, P. Csikvári, E. R. Kovács, and L. A. Végh, Splitting property via shadow systems. In 8th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, pp. 33-44, 2013.
  9. K. Bérczi and E. R. Kovács, A note on strongly edge-disjoint arborescences. In 7th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, pp. 10-18, 2011.

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.

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.

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.

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.