Publications of Tamás Király

 

Published and submitted papers

K. Bérczi, K. Chandrasekaran, T. Király, S. Kulkarni, Hypergraph Splitting-off and Covering Skew-Supermodular Functions in Strongly Polynomial Time, arXiv:2307.08555

K. Bérczi, G. Csáji, T. Király, On the complexity of packing rainbow spanning trees, Discrete Mathematics (2023) available online, arXiv:2206.11924

K. Bérczi, K. Chandrasekaran, T. Király, A. Pillai, Analyzing Residual Random Greedy for monotone submodular maximization, Information Processing Letters (2022), available online.

G. Gombos, D. Kis, L. Tóthmérész, T. Király, S. Nádas and S. Laki, Flow Fairness with Core-Stateless Resource Sharing in Arbitrary Topology, in IEEE Access (2022), available online.

K. Bérczi, T. Király, Y. Yamaguchi, Y. Yokoi, Matroid Intersection under Restricted Oracles, SIAM Journal on Discrete Mathematics 37:2 (2023), arXiv:2209.14516 (2022)

G. Csáji, T. Király, Y. Yokoi, Solving the Maximum Popular Matching Problem with Matroid Constraints, arXiv:2209.02195 (2022)

S. Fujishige, T. Király, K. Makino, K. Takazawa, S. Tanigawa, Minimizing submodular functions on diamonds via generalized fractional matroid matchings, Journal of Combinatorial Theory, Series B, Volume 157 (2022) 294-345

G. Csáji, T. Király, Y. Yokoi, Approximation Algorithms for Matroidal and Cardinal Generalizations of Stable Matching, arXiv:2208.09583 (2022), accepted to SOSA 2023

K. Bérczi, G. Csáji, T. Király, Manipulating the outcome of stable matching and roommates problems, arXiv:2204.13485 (2022)

K. Bérczi, T. Király, T. Schwarcz, Y. Yamaguchi, Y. Yokoi, Hypergraph characterization of split matroids, Journal of Combinatorial Theory, Series A Volume 194, February 2023, 105697, arXiv link (2022)

T. Kavitha, T. Király, J. Matuschke, I. Schlotter, U. Schmidt-Kraepelin, The popular assignment problem: when cardinality is more important than popularity, arXiv:2110.10984 (2021), conference version: SODA 2022

K. Bérczi, T. Király, Y. Yamaguchi, Y. Yokoi, Approximation by Lexicographically Maximal Solutions in Matching and Matroid Intersection Problems, Theoretical Computer Science Volume 910, 48-53 (2022)

T. Kavitha, T. Király, J. Matuschke, I. Schlotter, U. Schmidt-Kraepelin, Popular Branchings and Their Dual Certificates, Mathematical Programming volume 192, pages 567-595 (2022).

K. Bérczi, T. Király, S. Omlor, Scheduling with Non-Renewable Resources: Minimizing the Sum of Completion Times, 2019, arXiv link, ISCO 2020 Proceedings.

T. Király, Y. Yokoi, Equitable Partitions into Matchings and Coverings in Mixed Graphs, Discrete Mathematics 345 (2022), available online, arXiv link.

K. Bérczi, K. Chandrasekaran, T. Király, V. Madan, Improving the Integrality Gap for Multiway Cut, Mathematical Programming (2020) 183:171-193, available online. Conference version: Integer Programming and Combinatorial Optimization (IPCO 2019). Full version: arXiv link.

K. Bérczi, K. Chandrasekaran, T. Király, V. Madan, A tight $\sqrt{2}$-approximation for Linear 3-Cut, Mathematical Programming (2020) 184:411-443, available online.

K. Bérczi, K. Chandrasekaran, T. Király, E. Lee, C. Xu, Beating the 2-approximation factor for global bicut, Mathematical Programming Ser. A (2019) 177:291-320, view-only version.

K. Bérczi, A. Bernáth, T. Király, Gy. Pap, Blocking optimal structures, Discrete Mathematics 341 (2018) 1864-1872. Technical report: EGRES Technical Report no. 2017-07.

T. Király, Zs. Mészáros-Karkus, Finding strongly popular b-matchings in bipartite graphs, European Journal of Combinatorics Volume 88, August 2020

K. Bérczi, K. Chandrasekaran, T. Király, E. Lee, C. Xu, Global and fixed-terminal cuts in digraphs, arXiv link. Accepted to APPROX 2017 (extended abstract)

K. Bérczi, T. Király, Y. Kobayashi, Covering intersecting bi-set families under matroid constraints, SIAM Journal on Discrete Mathematics 30 (2016), 1758-1774, DOI link. Preliminary version: EGRES Technical Report no. 2013-06.

T. Király, Base polyhedra and the linking property, Journal of Combinatorial Optimization 36 (2018), 671-677, DOI link, EGRES Technical Report no. 2016-06.

A. Bernáth, T. Király, Blocking optimal k-arborescences, Proc. 27th Annual ACM-SIAM Symposium on Discrete Algorithms (2016), 1682-1694, DOI link, EGRES Technical Report no. 2015-09.

T. Király, J. Pap, An extension of Lehman's theorem and ideal set functions, Discrete Applied Mathematics 209 (2016), 251-263 DOI link. Preliminary version: EGRES Technical Report no. 2013-09.

A. Frank, T. Király, J. Pap, D. Pritchard, Characterizing and recognizing generalized polymatroids, Mathematical Programming, Volume 146, Issue 1-2 (2014), pp 245-273, journal link. Preliminary version: EGRES Technical Report no. 2012-03

T. Király, J. Pap, PPAD-completeness of polyhedral versions of Sperner's Lemma, Discrete Mathematics 313:15 (2013), 1594-1599, journal link, EGRES link.

T. Király, J. Pap, Stable multicommodity flows, Algorithms 6:1 (2013), 161-168, journal link (open access).

T. Király, L.C. Lau, M. Singh, Degree bounded matroids and submodular flows, Combinatorica 32 (2012), 703-720, journal link .

A. Bernáth, T. Király, A unifying approach to splitting-off, Combinatorica 32 (2012), 373-401. Preliminary version: EGRES Technical Report no. 2008-02.

A. Bernáth, T. Király, E.R. Kovács, G. Mádi-Nagy, Gy. Pap, J. Pap, J. Szabó, L. Végh, Algorithms for multiplayer multicommodity flow problems, Central European Journal of Operations Research 21 (2013), 699-712. Preliminary version: EGRES Technical Report no. 2012-09.

N.J.A. Harvey, T. Király, L.C. Lau, On disjoint common bases in two matroids, SIAM Journal on Discrete Mathematics 25 (2011), 1792-1803. (Preliminary version: EGRES Technical Report no. 2010-10.)

T. Király, L.C. Lau, Degree bounded forest covering, Proceedings of 15th International Conference IPCO 2011, LNCS 6655 (2011), 315-323. (Preliminary version: EGRES Technical Report no. 2010-08.)

T. Király, J. Pap, Ideal set functions, 7th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, Kyoto (2011), 332-340.

T. Király, A. Bernáth, L. Végh, L. Bajzik, E. Kovács, K. Bérczi, A. Jüttner, T. Jordán, Worst case bin packing for OTN electrical layer networks dimensioning, 13th International Conference on Transparent Optical Networks (2011), journal link.

T. Király, J. Pap, A note on kernels and Sperner's Lemma, Discrete Applied Mathematics, Volume 157, Issue 15 (2009), 3327-3331.

A. Bernáth, T. Király, Covering skew-supermodular functions by hypergraphs of minimum total size, Operations Research Letters, Volume 37, Issue 5 (2009), 345-350.

T. Király, J. Pap, Kernels, stable matchings, and Scarf's Lemma, RIMS Kôkyuroku Bessatsu B23 (2010), 131-145. (Preliminary version: EGRES Technical Report no. 2008-13)

A. Frank, T. Király, A survey on covering supermodular functions, in: Research Trends in Combinatorial Optimization, W.J. Cook, L. Lovász, J. Vygen, eds., Springer (2009), pp. 87-126.

T. Király, J. Szabó, A note on parity constrained orientations, Combinatorica Volume 29, Number 5 (2009), 619-628. (Preliminary version: EGRES Technical Report no. 2003-11.)

T. Király, L.C. Lau, Approximate min-max theorems for Steiner rooted-orientations of graphs and hypergraphs, Journal of Combinatorial Theory B 98 (2008), 1233-1252.

A. Bernáth, S. Iwata, T. Király, Z. Király, Z. Szigeti, Recent results on well-balanced orientations, Discrete Optimization 5 (2008), 663-676. (Preliminary version: EGRES Technical Report no. 2006-11)

T. Király, J. Pap, Total dual integrality of Rothblum's description of the stable marriage polyhedron, Mathematics of Operations Research 33(2) (2008), 283-290. (Preliminary version: EGRES Technical Report no. 2005-01)

T. Király, L.C. Lau, Tight Approximate Min-Max Relations for Steiner Rooted-Orientations of Graphs and Hypergraphs, Proceedings of 47th IEEE FOCS, 283-292. (Preliminary version: EGRES Technical Report no. 2006-13)

T. Király, M. Makai, On polyhedra related to even factors, Proc. IPCO X, LNCS 3064: 416-430, 2004. (Preliminary version: EGRES Technical Report no. 2003-09)

T. Király, Covering symmetric supermodular functions by uniform hypergraphs, Journal of Combinatorial Theory Series B 91 (2004), 185-200. (Preliminary version: EGRES Technical Report no. 2002-02)

A. Frank, T. Király, Combined connectivity augmentation and orientation problems, Discrete Applied Mathematics 131 (2003), 401-419. (Preliminary version: EGRES Technical Report no. 2001-07)

A. Frank, T. Király, Z. Király, On the orientation of graphs and hypergraphs, Discrete Applied Mathematics 131 (2003), 385-400. (Preliminary version: EGRES Technical Report no. 2001-06)

A. Frank, T. Király, M. Kriesell, On decomposing a hypergraph into k connected sub-hypergraphs, Discrete Applied Mathematics 131 (2003), 373-383. (Preliminary version: EGRES Technical Report no. 2001-02)

Technical reports and Quick proofs

T. Király, Zs. Mészáros-Karkus, Complexity of the NTU International Matching Game, EGRES Technical Report no. 2019-12.

T. Király, L. Lomoschitz, Online 2-dimensional rectangular bin packing, EGRES Technical Report no. 2019-11.

T. Király, Á. Antal, Casper's performance under different validator strategies, EGRES Quick Proof no. 2019-02.

T. Király, L. Lomoschitz, Profitability of the coin-hopping strategy, EGRES Quick Proof no. 2018-03.

T. Király, Zs. Mészáros-Karkus, Finding strongly popular matchings in certain bipartite preference systems, EGRES Technical Report no. 2016-16, 10th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications

T. Király, J. Pap, Finding equilibria in linear service-providing games, EGRES Technical Report no. 2016-15.

K. Bérczi, T. Király, Y. Kobayashi, Algorithmic aspects of covering supermodular functions under matroid constraints, EGRES Technical Report no. 2015-05.

A. Bernáth, T. Király, L. Végh, Special skew-supermodular functions and a generalization of Mader's splitting-off theorem, EGRES Technical Report no. 2011-10.

T. Király, J. Pap, On the list colouring of two matroids, EGRES Quick Proof no. 2010-01.

T. Király, Computing the minimum cut in hypergraphic matroids, EGRES Quick Proof no. 2009-05.

T. Király, A result on crossing families of odd sets, EGRES Technical Report no. 2007-10.

T. Király, L.C. Lau, Degree constrained submodular flows, EGRES Technical Report no. 2007-09.

T. Király, Applications of Eulerian splitting-off, EGRES Technical Report no. 2007-01.

T. Király, Oriented matroids from set-pairs, EGRES Quick Proof no. 2006-02.

T. Király, Minimal feedback sets in binary oriented matroids, EGRES Quick Proof no. 2006-01.

T. Király, Merging hyperedges to meet edge-connectivity requirements, EGRES Technical Report no. 2005-08.

T. Király, M. Makai, A note on hypergraph connectivity augmentation, EGRES Technical Report no. 2002-11.


Theses

T. Király, Edge-connectivity of undirected and directed hypergraphs, Ph.D. dissertation (2004). PDF, ps.GZ, Errata.

T. Király, A leemelési művelet és alkalmazásai , M.Sc. thesis (1999, in Hungarian). Gzipped Postscript.


Papers in Hungarian

T. Király, Élösszefüggőség-növelés hiperélek összevonásával, Matematikai Lapok 13 (2007), 28-31. (in Hungarian)

T. Király, M. Makai, Irányított hipergráfok élösszefüggőség-növelése, Matematikai Lapok 13 (2007), 32-39. (in Hungarian)

T. Király, J. Szabó, Szupermoduláris függvényt fedő adott befok-paritású irányítások, Matematikai Lapok 13 (2007), 40-48. (in Hungarian)