1 citations · 2 across the 19 of their papers we have counts for
8 papers · 1 filter
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…
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…
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…
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…