Showing 2025Show all
2 papers · 1 filter
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,…