7 papers
The Strong Secretary Conjecture is True for Linear Matroids
Kristóf Bérczi, Shaddin Dughmi, Vasilis Livanos +2
We prove a guarantee for Matroid Secretary on linear matroids: each element of a fixed optimal basis is selected with probability at least . This settles the strong secr…
The Rainbow Arborescence Problem on Cycles
Kristóf Bérczi, Tamás Király, Yutaro Yamaguchi +1
The rainbow arborescence conjecture posits that if the arcs of a directed graph with vertices are colored by colors such that each color class forms a spanning arborescen…
Approximating maximum properly colored forests via degree bounded independent sets
Yuhang Bai, Kristóf Bérczi, Johanna K. Siemelink
In the Maximum-size Properly Colored Forest problem, we are given an edge-colored undirected graph and the goal is to find a properly colored forest with as many edges as possible.…
A note on embracing exchange sequences in oriented matroids
Kristóf Bérczi, Benedek Nádor
An open problem in convex geometry asks whether two simplices , both containing the origin in their convex hulls, admit a polynomial-length sequence of ve…
Fixed-parameter tractability and hardness for Steiner rooted and locally connected orientations
Kristóf Bérczi, Florian Hörsch, András Imolay +1
Finding a Steiner strongly -arc-connected orientation is particularly relevant in network design and reliability, as it guarantees robust communication between a designated set…
Free-Order Online Selection for k-Systems
Kristóf Bérczi, Vasilis Livanos, José A. Soto +1
The Matroid Secretary Problem is a central question in online optimization, modeling sequential decision-making under combinatorial constraints. We introduce a bipartite graph fram…
-Separating Principal Partition Sequence of Submodular Functions
Kristóf Bérczi, Karthekeyan Chandrasekaran, Tamás Király +1
Narayanan showed the existence of the principal partition sequence of a submodular function, a structure with numerous applications in areas such as clustering, fast algorithms, an…