3 papers
cs.GT2026
Tight Efficiency Bounds for the Probabilistic Serial and Related Mechanisms
Jugal Garg, Yixin Tao, László A. Végh
The Probabilistic Serial (PS) mechanism -- also known as the simultaneous eating algorithm -- is a canonical solution for the random assignment problem under ordinal preferences. I…
math.CO2025
Matroids are Equitable
Hannaneh Akrami, Siyue Liu, Roshan Raj +1
We show that if the ground set of a matroid can be partitioned into bases, then for any given subset of the ground set, there is a partition into bases such that t…
cs.DS2025
From Incremental Transitive Cover to Strongly Polynomial Maximum Flow
Daniel Dadush, James B. Orlin, Aaron Sidford +1
We provide faster strongly polynomial time algorithms solving maximum flow in structured -node -arc networks. Our results imply an -time strongly polynomial tim…