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 the matroid secretary problem on linear matroids, therefore settling the strong secretary conjecture in this class of matroids. The result holds both…
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…