3 papers
math.OC2025
Minimum Cut Representability of Stable Matching Problems
Yuri Faenza, Ayoub Foussoul, Chengyue He
We introduce and study Minimum Cut Representability, a framework to solve optimization and feasibility problems over stable matchings by representing them as minimum s-t cut proble…
cs.DM2024
Scarf's Algorithm on Arborescence Hypergraphs
Karthekeyan Chandrasekaran, Yuri Faenza, Chengyue He +1
Scarf's algorithm--a pivoting procedure that finds a dominating extreme point in a down-monotone polytope--can be used to show the existence of a fractional stable matching in hype…
math.CO2023
Scarf's algorithm and stable marriages
Yuri Faenza, Chengyue He, Jay Sethuraman
Scarf's algorithm gives a pivoting procedure to find a special vertex -- a dominating vertex -- in down-monotone polytopes. This paper studies the behavior of Scarf's algorithm whe…