6 papers
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…
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…
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,…
A New Conjecture on Hardness of Low-Degree 2-CSP's with Implications to Hardness of Densest -Subgraph and Other Problems
Julia Chuzhoy, Mina Dalirrooyfard, Vadim Grinberg +1
We propose a new conjecture on hardness of low-degree -CSP's, and show that new hardness of approximation results for Densest -Subgraph and several other problems, including…
How to hide a clique?
Uriel Feige, Vadim Grinberg
In the well known planted clique problem, a clique (or alternatively, an independent set) of size is planted at random in an Erdos-Renyi random graph, and the goal is…
Approximating Star Cover Problems
Buddhima Gamlath, Vadim Grinberg
Given a metric space , we consider star covers of with balanced loads. A star is a pair where and , and the load of a star…