1 citations · 2 across the 19 of their papers we have counts for
22 papers
Weighted Equitability and Matroid-Constrained Discrepancy
Kristóf Bérczi, Siyue Liu, Victor Reis +1
We prove weighted matroid equitability. Let be a matroid whose ground set can be partitioned into bases, and assign a nonnegative weight to every element. T…
Rainbow Arborescence Conjecture
Kristóf Bérczi, Tamás Király, Yutaro Yamaguchi +1
The famous Ryser--Brualdi--Stein conjecture asserts that every Latin square contains a partial transversal of size . Since its appearance, the conjecture has attr…
Matroid Secretary via Labeling Schemes
Kristóf Bérczi, Vasilis Livanos, José Soto +1
The Matroid Secretary Problem (MSP) is one of the most prominent settings for online resource allocation and optimal stopping. A decision-maker is presented with a ground set of el…
Matroid products via submodular coupling
Kristóf Bérczi, Boglárka Gehér, András Imolay +3
The study of matroid products traces back to the 1970s, when Lovász and Mason studied the existence of various types of matroid products with different strengths. Among these, the…
Finding Spanning Trees with Perfect Matchings
Kristóf Bérczi, Tamás Király, Yusuke Kobayashi +2
We investigate the tractability of a simple fusion of two fundamental structures on graphs, a spanning tree and a perfect matching. Specifically, we consider the following problem:…
Multiway Cuts with a Choice of Representatives
Kristóf Bérczi, Tamás Király, Daniel P. Szabo
In this paper, we study several generalizations of multiway cut where the terminals can be chosen as \emph{representatives} from sets of \emph{candidates} . In this…
Matroid Intersection under Minimum Rank Oracle
Mihály Bárász, Kristóf Bérczi, Tamás Király +3
In this paper, we consider the tractability of the matroid intersection problem under the minimum rank oracle. In this model, we are given an oracle that takes as its input a set o…
Quotient-convergence of Submodular Setfunctions
Kristóf Bérczi, Márton Borbényi, László Lovász +1
We introduce the concept of quotient-convergence for sequences of submodular set functions, providing, among others, a new framework for the study of convergence of matroids throug…
Monotonic Decompositions of Submodular Set Functions
Kristóf Bérczi, Boglárka Gehér, András Imolay +2
Submodular set functions are undoubtedly among the most important building blocks of combinatorial optimization. Somewhat surprisingly, continuous counterparts of such functions ha…
Cycle Matroids of Graphings: From Convergence to Duality
Kristóf Bérczi, Márton Borbényi, László Lovász +1
A recent line of research has concentrated on exploring the links between analytic and combinatorial theories of submodularity, uncovering several key connections between them. In…
Hypergraph Connectivity Augmentation in Strongly Polynomial Time
Kristóf Bérczi, Karthekeyan Chandrasekaran, Tamás Király +1
We consider hypergraph network design problems where the goal is to construct a hypergraph that satisfies certain connectivity requirements. For graph network design problems where…
Approximating maximum-size properly colored forests
Yuhang Bai, Kristóf Bérczi, Gergely Csáji +1
In the Properly Colored Spanning Tree problem, we are given an edge-colored undirected graph and the goal is to find a properly colored spanning tree, i.e., a spanning tree in whic…
Splitting-off in Hypergraphs
Kristóf Bérczi, Karthekeyan Chandrasekaran, Tamás Király +1
The splitting-off operation in undirected graphs is a fundamental reduction operation that detaches all edges incident to a given vertex and adds new edges between the neighbors of…
Partitioning into common independent sets via relaxing strongly base orderability
Kristóf Bérczi, Tamás Schwarcz
The problem of covering the ground set of two matroids by a minimum number of common independent sets is notoriously hard even in very restricted settings, i.e.\ when the goal is t…
Matroid Horn functions
Kristóf Bérczi, Endre Boros, Kazuhisa Makino
Hypergraph Horn functions were introduced as a subclass of Horn functions that can be represented by a collection of circular implication rules. These functions possess distinguish…
Envy-free dynamic pricing schemes
Kristóf Bérczi, Laura Codazzi, Julian Golak +1
A combinatorial market consists of a set of indivisible items and a set of agents, where each agent has a valuation function that specifies for each subset of items its value for t…
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…
On approximating the rank of graph divisors
Kristóf Bérczi, Hung P. Hoang, Lilla Tóthmérész
Baker and Norine initiated the study of graph divisors as a graph-theoretic analogue of the Riemann-Roch theory for Riemann surfaces. One of the key concepts of graph divisor theor…
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…
Efficient Approximations for Many-Visits Multiple Traveling Salesman Problems
Kristóf Bérczi, Matthias Mnich, Roland Vincze
A fundamental variant of the classical traveling salesman problem (TSP) is the so-called multiple TSP (mTSP), where a set of salesmen jointly visit all cities from a set of …
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…