Uriel Feige

collaborators

6 papers

cs.DS2025

Large cliques and large independent sets: can they coexist?

Uriel Feige, Ilia Pauzner

For a graph $G$ and a parameter $k$ , we call a vertex $k$ -enabling if it belongs both to a clique of size $k$ and to an independent set of size $k$ , and we call it $k$ -excluding ot…

cs.GT2025

The residual maximin share

Uriel Feige

We consider fair allocations of indivisible goods to agents with general monotone valuations. We observe that it is useful to introduce a new share-based fairness notion, the {\em…

cs.GT2025

From multi-allocations to allocations, with subadditive valuations

Uriel Feige

We consider the problem of fair allocation of $m$ indivisible items to $n$ agents with monotone subadditive valuations. For integer $d \geq 2$ , a $d$ -multi-allocation is an allocati…

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 $m$ indivisible goods to $n$ agents with either subadditive or XOS valuations, in the arbitrary entitlement case. As fairness notions,…

cs.GT2025

Concentration and maximin fair allocations for subadditive valuations

Uriel Feige, Shengyu Huang

We consider fair allocation of $m$ indivisible items to $n$ agents of equal entitlements, with submodular valuation functions. Previously, Seddighin and Seddighin [{\em Artificial…