3 papers
cs.GT2026
On MMS, APS and XOS
Uriel Feige, Vadim Grinberg
We consider allocations of a set of indivisible goods to agents of equal entitlements that have valuations from the class XOS. A previous sequence of works showed allocatio…
cs.DS2025
Upper bounds on the theta function of random graphs
Uriel Feige, Vadim Grinberg
The theta function of Lovasz is a graph parameter that can be computed up to arbitrary precision in polynomial time. It plays a key role in algorithms that approximate graph parame…
cs.GT2025
Fair allocations with subadditive and XOS valuations
Uriel Feige, Vadim Grinberg
We consider the problem of fair allocation of indivisible goods to agents with either subadditive or XOS valuations, in the arbitrary entitlement case. As fairness notions,…