Lemma 4.18, reduced case (Fig. 2, Cases 1–3) — expected make-span at most 7/4 · t_opt

Let $\beta = 4/3$ and $a, b, c, d \ge 0$. Consider the four-task instance of Fig. 2 for two agents: task $k_1$ with times $(a, \beta a)$, $k_2$ with $(b, \beta b)$, $l_1$ with $(c, \beta c)$ and $l_2$ with $(\beta d, d)$ for agents $(1, 2)$. The mechanism gives $k_1, k_2$ to agent 1 and gives each of $l_1, l_2$ to either agent with probability $1/2$; the optimal allocation gives $k_1, l_1$ to agent 1 and $k_2, l_2$ to agent 2. If both agents finish at the same time under the optimal allocation, $t_{opt} = a + c = \beta b + d$, then the expected make-span over the four equally likely allocations satisfies

This is the case to which the paper reduces Lemma 4.18; zero times represent instances with fewer than four tasks.

Formalization Note The three cases of the paper are combined into one inequality with explicit maxima, with $\beta = 4/3$ substituted.