Balanced Stable Marriage: How Close is Close Enough?

Sushmita Gupta, Sanjukta Roy, Saket Saurabh +1

The Balanced Stable Marriage problem is a central optimization version of the classic Stable Marriage problem. Here, the output cannot be an arbitrary stable matching, but one that…