1 citations · 1 across the 8 of their papers we have counts for
10 papers
Matroid Intersection under Restricted Oracles
Kristóf Bérczi, Tamás Király, Yutaro Yamaguchi +1
Matroid intersection is one of the most powerful frameworks of matroid theory that generalizes various problems in combinatorial optimization. Edmonds' fundamental theorem provides…
Solving the Maximum Popular Matching Problem with Matroid Constraints
Gergely Csáji, Tamás Király, Yu Yokoi
We consider the problem of finding a maximum popular matching in a many-to-many matching setting with two-sided preferences and matroid constraints. This problem was proposed by Ka…
Maximum Stable Matching with Matroids and Partial Orders
Gergely Csáji, Tamás Király, Yu Yokoi
The Stable Marriage problem (SM), solved by the famous deferred acceptance algorithm of Gale and Shapley (GS), has many natural generalizations. If we allow ties in preferences, th…
On the complexity of packing rainbow spanning trees
Kristóf Bérczi, Gergely Csáji, Tamás Király
One of the most important questions in matroid optimization is to find disjoint common bases of two matroids. The significance of the problem is well-illustrated by the long list o…
Manipulating the outcome of stable matching and roommates problems
Kristóf Bérczi, Gergely Csáji, Tamás Király
The stable marriage and stable roommates problems have been extensively studied due to their high applicability in various real-world scenarios. However, it might happen that no st…
Hypergraph characterization of split matroids
Kristóf Bérczi, Tamás Király, Tamás Schwarcz +2
We provide a combinatorial study of split matroids, a class that was motivated by the study of matroid polytopes from a tropical geometry point of view. A nice feature of split mat…
The popular assignment problem: when cardinality is more important than popularity
Telikepalli Kavitha, Tamás Király, Jannik Matuschke +2
We consider a matching problem in a bipartite graph where nodes in are agents having preferences in partial order over their neighbors, while nodes in are o…
Approximation by Lexicographically Maximal Solutions in Matching and Matroid Intersection Problems
Kristóf Bérczi, Tamás Király, Yutaro Yamaguchi +1
We study how good a lexicographically maximal solution is in the weighted matching and matroid intersection problems. A solution is lexicographically maximal if it takes as many he…
Popular Branchings and Their Dual Certificates
Telikepalli Kavitha, Tamás Király, Jannik Matuschke +2
Let be a digraph where every node has preferences over its incoming edges. The preferences of a node extend naturally to preferences over branchings, i.e., directed forests; a…
Scheduling with Non-Renewable Resources: Minimizing the Sum of Completion Times
Kristóf Bérczi, Tamás Király, Simon Omlor
The paper considers single-machine scheduling problems with a non-renewable resource. In this setting, we are given a set jobs, each of which is characterized by a processing time,…