Theorem 3.1 — the LP-rounding-and-splitting algorithm is a 3k-approximation, k = ⌊3 log m / log log m⌋, for complement-free bidders

There is $m_0$ such that the following holds for every number of items $m\ge m_0$ and every number of bidders $n$. Let $v_1,\dots,v_n$ be normalized, monotone, complement-free valuations, let $x$ be an optimal solution of the LP relaxation with value $OPT^*$, and let $k=\lfloor 3\log m/\log\log m\rfloor$. Write $OPT$ for the welfare of any allocation $(O_1,\dots,O_n)$.

1. Step (i) succeeds. If $OPT^*>3\max_i v_i(M)$, then with probability greater than $1/6$ the randomized-rounding preallocation $(S_1,\dots,S_n)$ satisfies both: every item appears in at most $k$ of the $S_i$, and $\sum_i v_i(S_i)\ge OPT^*/3$.
2. The guarantee. For every preallocation $(S_1,\dots,S_n)$ with these two properties, every best layer $r$ of step (iii), and every admissible bidder of step (iv), the algorithm's output is an allocation, and its welfare $W$ satisfies

3. The small case. If $OPT^*\le 3\max_i v_i(M)$, then giving all of $M$ to a bidder $i_0$ maximizing $v_i(M)$ has welfare $v_{i_0}(M)\ge\sum_i v_i(O_i)/3$ for every allocation $(O_i)$.

This is Theorem 3.1 of the paper: for complement-free bidders the algorithm produces an allocation that is an $O(\log m/\log\log m)$-approximation to the optimal one.

Formalization Note The paper writes $O(k)=O(\log m/\log\log m)$; its proof yields the explicit ratio $3k$ with $k=\lfloor3\log m/\log\log m\rfloor$ (natural logarithm), for $m\ge m_0$, and $m_0$ is existential because Lemma 3.1 holds for sufficiently large $m$. The paper's w.l.o.g. scaling $\max_i v_i(M)=1$ with the case split $OPT^*\le3$ / $OPT^*>3$ is replaced by the scale-free split $OPT^*\le 3\max_i v_i(M)$ / $OPT^*>3\max_i v_i(M)$, written as $3v_i(M)<OPT^*$ for all $i$. Step (i) is a randomized search; part 1 is the success probability of one rounding, and the probability is the finite-sum rounding law of the LP definition file. The choices of $r$ in step (iii) and of the bidder in step (iv) are left open by the paper and are universally quantified. Running time is not modeled.