In the submodular welfare maximization problem, there is a set $M$ of items that should be partitioned among $n$ agents. Each agent $i$ has a value function $v_i: 2^M\to \mathbb{R}_+$. All value functions are monotonically-increasing and submodular. The goal is to find a partition $M = X_1\cup \cdots \cup X_n$, such that the sum of agents' values $\sum_{i=1}^n v_i(X_i)$ is maximized.
It is known that a greedy algorithm attains a $1/2$-approximation to this problem. Vondrak (2008) presented a randomized algorithm that attains a $(1-1/e)$ approximation (in expectation), in the value oracle model; this algorithm has been generalized by Calinescu, Chekuri, Pal and Vondrak (2011), but their algorithm is randomized too.
Feige and Vondrak (2010) present an algorithm that attains an approximation slightly better than $(1-1/e)$ in the demand-oracle model, but their algorithm, too, uses randomized rounding.
What is the best known approximation ratio for this problem, using a deterministic polynomial-time algorithm?
