# The Submodular Santa Claus Problem

Étienne Bamas111Post-Doctoral Fellow, ETH AI Center, Switzerland.
<EMAIL_ADDRESS>Sarah Morell222TU Berlin, Germany<EMAIL_ADDRESS>berlin.de. Funded by the Deutsche Forschungsgemeinschaft (DFG, German Research
Foundation) under Germany´s Excellence Strategy – The Berlin Mathematics
Research Center MATH+ (EXC-2046/1, project ID: 390685689). Lars
Rohwedder333Maastricht University, Netherlands.
<EMAIL_ADDRESS>Supported by Dutch Research Council (NWO)
project “The Twilight Zone of Efficiency: Optimality of Quasi-Polynomial Time
Algorithms” [grant number OCEN.W.21.268].

###### Abstract

We consider the problem of allocating indivisible resources to players so as
to maximize the minimum total value any player receives. This problem is
sometimes dubbed the Santa Claus problem and its different variants have been
subject to extensive research towards approximation algorithms over the past
two decades.

In the case where each player has a potentially different additive valuation
function, Chakrabarty, Chuzhoy, and Khanna [FOCS’09] gave an
$O(n^{\varepsilon})$-approximation algorithm with polynomial running time for
any constant $\varepsilon>0$ and a polylogarithmic approximation algorithm in
quasi-polynomial time. We show that the same can be achieved for monotone
submodular valuation functions, improving over the previously best algorithm
due to Goemans, Harvey, Iwata, and Mirrokni [SODA’09], which has an
approximation ratio of more than $\sqrt{n}$.

Our result builds up on a sophisticated LP relaxation, which has a recursive
block structure that allows us to solve it despite having exponentially many
variables and constraints.

##  1 Introduction

The egalitarian welfare is the value of the least happy player. Other natural
welfare functions include utilitarian welfare, the sum of values, and Nash
social welfare, the product of values. Egalitarian welfare can be seen as the
trade-off that emphasizes most extremely on fairness. In this paper we study
the problem of allocating indivisible resources with the goal of maximizing
egalitarian welfare, which is sometimes called the Santa Claus problem or max-
min fair allocation.

#### Problem setting.

Given resources $R$ and players $P$, we wish to find an allocation
$\sigma:R\rightarrow P$ such that

$\min_{p\in P}\ f_{p}(\\{r\in R:\sigma(r)=p\\})$

is maximized. Here $f_{p}:2^{R}\rightarrow\mathbb{R}_{\geq 0}$ with $p\in P$
is the function that specifies the value that player $p$ receives from a set
of resources. When considering polynomial-time approximation algorithms, one
typically assumes the function can be accessed by value queries, i.e., an
oracle that returns $f_{p}(A)$ for some given $p$ and $A$ in polynomial time.
Strong assumptions on the functions are necessary in order to hope for any
meaningful algorithmic guarantees. At the same time, the functions should
still remain expressive enough to capture realistic scenarios.

A natural assumption is that each $f_{p}$ is non-negative and additive (a
linear function), which means that there are values
$v_{p,r}\in\mathbb{R}_{\geq 0}$ for each $p\in P,r\in R$ and
$f_{p}(A)=\sum_{r\in A}v_{p,r}$ for each $A\subseteq R$. Already for this
class of functions, the study of approximation algorithms for the Santa Claus
problem has proven to be extremely challenging. The best algorithm due to
Chakrabarty, Chuzhoy, and Khanna [11] achieves an
$n^{\varepsilon}$-approximation in polynomial time, for every fixed constant
$\varepsilon>0$, or a $(\log^{O(1)}n)$-approximation in quasi-polynomial time,
more precisely in time $n^{O(\log n/\log\log n)}$. The best lower bound on the
approximation ratio of a polynomial-time algorithm is $2$ (assuming
P$\neq$NP). Closing the gap remains a big open question in approximation
algorithms and is connected to the similar task of minimizing makespan on
unrelated parallel machines, see [5].

An important generalization of additive functions is the class of monotone
submodular functions. A function $f$ is submodular if it satisfies the
_diminishing marginal returns property_ , which means that

$f(A\cup\\{r\\})-f(A)\geq f(B\cup\\{r\\})-f(B)\text{ for all }A\subseteq
B\text{ and }r\notin B.$

Monotonicity states that $f(A)\leq f(B)$ for $A\subseteq B$. As is standard in
approximation algorithms, we also assume that any monotone submodular function
is normalized such that $f(\emptyset)=0$. Staying the metaphor of Santa Claus,
an example of the diminishing marginal returns property is that the value of
an apple is higher for a child, when the child does not have a donut than when
it does.

For utilitarian welfare or Nash social welfare, the class of monotone
submodular functions still admits good algorithms [21, 24], which raises the
question whether the restriction to additive functions is necessary in
egalitarian welfare.

Even more general than monotone submodular functions are subadditive
functions, which only need to satisfy $f(A\cup B)\leq f(A)+f(B)$ for all
$A,B$. Next to additive functions, submodular and subadditive functions are
arguably the most fundamental classes of valuation functions. Both submodular
and subadditive functions are also briefly mentioned by Chakrabarty, Chuzhoy,
and Khanna [11] who emphasize that at the time the best lower bound for both
in the Santa Claus problem was also only $2$. Since then however, Barman,
Bhaskar, Krishna, and Sundaram [8] have proven that for XOS functions, a class
of functions that lies between monotone submodular and subadditive, any
$O(n^{1-\varepsilon})$-approximation algorithm requires exponentially many
value queries, which therefore also forms a lower bound on subadditive
functions. This lower bound is in the value query model. In literature there
are more powerful query models, for example demand queries, see e.g. [8, 16],
which we do not detail here.

Monotone submodular functions are not subject to the mentioned lower bound and
a sublinear approximation rate is indeed possible: Goemans, Harvey, Iwata, and
Mirrokni [17] gave a reduction to the additive case, which loses a factor of
$O(\sqrt{n}\log n)$ and thus leads to an
$O(n^{1/2+\varepsilon})$-approximation algorithm when combined with [11].

#### Contribution and outline.

In this paper we achieve a direct generalization from the additive to the
monotone submodular case, without the reduction of Goemans, Harvey, Iwata, and
Mirrokni [17], and match the state-of-the-art from the additive case.

######  Theorem 1.

For the Submodular Santa Claus problem there is a polylogarithmic
approximation algorithm with running time $n^{O(\log n/\log\log n)}$ and an
$n^{\varepsilon}$-approximation algorithm with running time
$n^{O(1/\varepsilon)}$ for any constant $\varepsilon>0$.

Similar to Chakrabarty, Chuzhoy, and Khanna [11], our techniques can be
divided into three steps:

  1. 1.

Reducing to a carefully designed layered flow problem, the _augmentation
problem_.

  2. 2.

Formulating and solving a strong linear programming relaxation of the
augmentation problem.

  3. 3.

Obtaining integral solution of the augmentation problem via randomized
rounding.

The most challenging part to generalize is the second step. In order to
include submodular valuation functions in the linear programming relaxation,
we use the standard concept of configuration variables, i.e., a variable for
each set of resources that has a sufficiently large value. The natural way of
writing a configuration LP, however, is not sufficient even for the additive
case, see e.g. [7]. The formulation used by Chakrabarty, Chuzhoy, and Khanna
for the additive case is highly non-trivial. It is closely related to using a
constant or logarithmic number of rounds of the Sherali-Adams hierarchy on a
naive formulation, see [9]. Notably, their linear program is strong for the
augmentation problem, to which they give a non-trivial reduction (step 1), but
not for the original problem.

Combining their approach with configuration variables as above leads to a
linear program that has both an exponential number of variables and
constraints, an issue that does not occur in the additive case. Typically, one
needs to have either a polynomial number of variables or constraints in order
to even hope to solve a linear program efficiently. Otherwise, already the
encoding of a solution might require exponential space. Exceptions are very
rare, see e.g. [18]. The distinct feature of our linear programming relaxation
is that it has a recursive block structure. Specifically, the matrix consists
of an exponentially large number of blocks along the diagonal which are linked
by a polynomial number of constraints. The blocks on the diagonal exhibit the
same structure recursively up to a recursion depth of $h$, see Figure 1. It
can be shown that if in addition the feasible region of each block (ignoring
the linking constraints) forms a polyhedral cone, then indeed such matrices
always have solutions of support $n^{O(h)}$ (if any exist). This is then
polynomial for constant recursion depth $h$. We solve our specific formulation
using ideas from the Dantzig-Wolfe decomposition [12], where the pricing
problem requires a combination of recursively solving a linear program with
lower recursion depth and the search for a configuration of high submodular
function value. For the latter we use the multilinear extension and continuous
Greedy in a non-standard variant. This way we arrive at a sufficiently good
approximation of the linear program.

$\ddots$$\ddots$$\ddots$polyexpexp Figure 1: Block structure of non-zero
entries in constraint matrix of linear programming relaxation

As an additional contribution, we significantly simplify the reduction step of
Chakrabarty, Chuzhoy, and Khanna which used very intricate techniques and non-
trivial graph theory results. In contrast, our reduction only uses standard
flow arguments.

#### Further related work.

If all functions are identical and additive, then there exists a PTAS for the
Santa Claus problem [25, 14]. If they are identical and monotone submodular,
then a Greedy type of algorithm still achieves a constant approximation [19].

A substantially harder variant, which has received a lot of attention is the
so-called restricted assignment case. Here, the valuation functions are
identical ($f_{p}=f_{p^{\prime}}$ for $p,p^{\prime}\in P$), but each player
$p$ can only receive resources from a specific set $R(p)\subseteq R$. This can
equivalently be phrased as $f_{p}(A)=f(A\cap R(p))$ for some uniform function
$f$, or in the additive case, that $v_{p,r}\in\\{0,v_{r}\\}$ for some uniform
value $v_{r}$ for each resource $r\in R$. Most of this work focuses on the
mentioned additive case, leading to a constant factor approximation for this
case [7, 15, 2, 13, 22, 3]. For the submodular case, an $O(\log\log
n)$-approximation algorithm is known [4]. These works heavily rely on the
configuration LP, a linear programming relaxation, which is known to have a
high integrality gap outside of the restricted assignment variant [7].
Therefore these techniques have only limited impact towards the goals of this
paper.

Outside the restricted assignment problem, some progress towards a constant
approximation is due to Bamas and Rohwedder [6] who gave a $(\log^{O(1)}\log
n)$-approximation algorithm in quasi-polynomial time for the so-called max-min
degree arborescence problem, a special case of the additive variant, where the
configuration LP already has a high integrality gap.

The dual problem of minimizing the maximum instead of maximizing the minimum
function value is usually motivated by machine scheduling, specifically
makespan minimization. Here, the additive case is well known to admit a
constant approximation [20] and the reduction by Goemans, Harvey, Iwata, and
Mirrokni [17] works in the same way, yielding a polynomial-time
$O(\sqrt{n}\log n)$-approximation algorithm for makespan minimization with
monotone submodular load functions. Interestingly, this is known to be the
best possible up to logarithmic factors in the value query model, see [23],
and therefore behaves differently to the problem studied in this paper.

##  2 Algorithmic framework

In this chapter, we introduce the augmentation problem as well as the linear
programming relaxation for it. Those are the pillars of our algorithm that
connect the three steps outlined in the introduction. In Section 3 we then
show how to reduce to the augmentation problem, in Section 4 we explain how to
solve its linear programming relaxation, and in Section 5 we present the
rounding algorithm for the relaxation.

###  2.1 The augmentation problem

As the name suggests, the augmentation problem is related to augmenting some
partial solution of the Submodular Santa Claus problem to a better solution.
This can be seen as a much more involved variant of finding augmenting paths
to solve bipartite matching. Similar to there, we will later invoke it several
times in order to arrive at the final solution for the Santa Claus problem. We
formulate the augmentation problem in purely graph theoretical terms.

An instance of the augmentation problem contains several levels. We will start
by introducing the structure within one level.

#### One level of the augmentation problem.

Let $G=(V,E)$ be a directed graph and let $S,T\subseteq V$ denote disjoint
sets of sources and sinks. Each source in $S$ has exactly one outgoing edge
and no incoming edges. Each sink in $T$ has only incoming edges. Furthermore,
for all $v\in T$ let $f_{v}:2^{\delta(v)}\rightarrow\mathbb{R}_{\geq 0}$ be
monotone, submodular functions. Here, $\delta(v)$ are the edges incident to
$v$.

The solution for this level is a binary flow $g:E\rightarrow\\{0,1\\}$ from
$S$ to $T$, i.e., flow conservation is satisfied on $V\setminus(S\cup T)$. We
write $E(g)=\\{e\in E:g(e)>0\\}$ and $V(g)=\bigcup_{(u,v)\in E(g)}\\{u,v\\}$.
Furthermore, in slight abuse of notation we write $V^{\prime}\cap
g=V^{\prime}\cap V(g)$ for some $V^{\prime}\subseteq V$ and $E^{\prime}\cap
g=E^{\prime}\cap E(g)$ for some $E^{\prime}\subseteq E$. We say that sink
$v\in T$ is $\alpha$-covered by $g$ if $f_{v}(g\cap\delta(v))\geq 1/\alpha$.
We give an example in Figure 2.

Figure 2: An instance of the one-level augmentation problem. The top sink on
the left has valuation function equal to the total flow received, and the sink
at the bottom has valuation function equal to the total flow received divided
by $2$. The set of bold orange edges forms a feasible solution which covers
all the sinks in $T$.

#### Augmentation problem.

For $h\in\mathbb{N}$, an $h$-level instance of the augmentation problem
consists of levels $(G_{i},S_{i},T_{i})$ with $G_{i}=(V_{i},E_{i})$ for
$i=1,2,\dotsc,h$ with the structure as above and monotone submodular functions
$f_{v}:2^{\delta(v)}\rightarrow\mathbb{R}_{\geq 0}$ for $v\in T_{1}\cup
T_{2}\cup\dotsc\cup T_{h}$. In addition, there are _linking edges_
$L_{i}\subseteq T_{i+1}\times S_{i}$ for $i=1,2,\dotsc,h-1$. Each set $L_{i}$
forms a matching, i.e., the edges are disjoint. For $U\subseteq S_{i}$ we
write $L_{i}(U)=\\{v\in T_{i+1}:(v,u)\in L_{i}\text{ for some }u\in U\\}$.

A solution consists of a flow $g_{i}$ for each level $i$, as described above.
The $h$ levels depend on each other in that for the source $g\cap S_{i}$ is
used by the flow in level $i$, $g_{i+1}$ must cover $L_{i}(g\cap S_{i})$. In
other words, if $s\in g\cap S_{i}$ and there is no edge $(u,s)\in L_{i}$ for
any $u\in T_{i+1}$, i.e., $L_{i}(\\{s\\})=\emptyset$, then there is no further
requirement and if indeed there exists such an edge then we may informally
think of the flow leaving source $s$ to arrive through the linking edge and
indirectly from $u$. Note, however, that $u$ may require an incoming flow
higher than the amount of flow leaving $s$. The sinks of the first level
$T_{1}$ and the sources of the last level $S_{h}$ have no dependencies with
other levels.

To conclude the description of the problem, a solution is feasible for some
$T^{*}\subseteq T_{1}$ if

  * •

$g_{1}$ $\alpha$-covers each $v\in T^{*}$ and

  * •

for $i=1,2,\dotsc,h-1$, solution $g_{i+1}$ $\alpha$-covers each $v\in
L_{i}(g_{i}\cap S_{i})$.

We refer the reader to Figure 3 for an example. In the remainder we denote by
$n$ the total number of vertices in all $h$ graphs. This will be polynomial in
the size of the original instance.

Figure 3: An instance of $2$-level augmentation problem. The two levels are
copies of the one level of Figure 2, with the same valuation functions for the
sinks in each level. The second and fourth source in $S_{1}$ have a linking
edge with the first and second sinks in $T_{2}$. The set of bold orange edges
forms a feasible solution which covers all of $T_{1}$.

#### Congestion.

A technically very useful notion is the following relaxation of the problem:
we allow each $g_{i}(e)$ to be an integer number in $\\{0,1,\dotsc,\beta\\}$
instead of $\\{0,1\\}$. The rest of the definition remains the same. We say
that such a solution has congestion $\beta$.

We will reduce the Submodular Santa Claus problem to the following gap
problem: for some $T^{*}\subseteq T_{1}$ either find a feasible solution
$g_{1},g_{2},\dotsc,g_{h}$ with coverage $1/\alpha$ and congestion at most
$\beta$ or determine that there is no such solution with coverage $1$ and
congestion $1$. We call an algorithm that solves this problem an
_$(\alpha,\beta)$ -approximation algorithm_. The lower the values of $\alpha$
and $\beta$ are, the better the approximation rate for the Submodular Santa
Claus problem. The reduction to the augmentation problem follows a very
similar strategy to Chakrabarty, Chuzhoy, and Khanna [11]. Formally, we prove
in section 3 the following theorem.

######  Theorem 2.

Let $\mathcal{A}$ be an $(\alpha,\beta)$-approximation algorithm for the
augmentation problem and let $h,\gamma\in\mathbb{N}$ with $\gamma\geq
1000\alpha^{3}\beta^{3}h^{4}\log^{2}(n)$ and $h\geq 1+\log(\beta
n^{2})/\log(\gamma/(2\alpha))$. Then there is a $\gamma$-approximation
algorithm for the Submodular Santa Claus problem that uses polynomially many
calls to $\mathcal{A}$ on $h$-level instances and has polynomial time
overhead.

The main technical novelty is in proving that the augmentation problem can
indeed be approximated well.

######  Theorem 3.

There is an $(\alpha,\beta)$-approximation algorithm for the $h$-level routing
problem with running time $n^{O(h)}$ with $\alpha=O(1)$ and
$\beta=\mathrm{polylog}(n)$.

These two theorems imply the main theorem.

###### Proof of Theorem 1.

Let $\alpha,\beta$ as in Theorem 3. By setting $h=\lceil 1+\log(\beta
n^{2})/\log\log(n)\rceil=O(\log n/\log\log n)$ and $\gamma=\lceil
1000\alpha^{3}\beta^{3}h^{4}\log^{2}(n)\rceil=\mathrm{polylog}(n)$ we obtain a
polylogarithmic approximation in time $n^{O(\log n/\log\log n)}$.

On the other hand, for $\gamma=n^{\varepsilon}$ and $h=\lceil 1+\log(\beta
n^{2})/\log(\gamma/(2\alpha))\rceil=O(1/\varepsilon)$ we have for sufficiently
large $n$ that $\gamma\geq 1000\alpha^{3}\beta^{3}h^{4}\log^{2}(n)$. Hence,
there is a $n^{\varepsilon}$-approximation algorithm with running time
$n^{O(1/\varepsilon)}$. ∎

###  2.2 Definition of the linear programming relaxation

Consider a solution to the augmentation problem without congestion. This
solution exhibits the following hierarchical structure: after an arbitrary
path decomposition of the flows $g_{1},\dotsc,g_{h}$, we can associate with
each sink $u\in T_{i}$ the set of sources $A\subseteq S_{i}$, for which in the
decomposition some path ends in $u$ and starts in $A$. Moreover, we associate
$L_{i}(A)\subseteq T_{i+1}$ with $u$ and by the fact that each source has only
one outgoing edge, effectively enforcing a vertex capacity of $1$ on it, each
sink in $T_{i+1}$ is only associated to one sink in $T_{i}$. Recursively, this
results in a forest-like structure of sinks. Based on this structure, we
design our linear programming formulation recursively.

For each suffix of the levels $i,i+1,\dotsc,h$. We define $E_{\geq
i}=E_{i}\cup\cdots\cup E_{h}$. For each level $i$, set of sinks
$T^{*}\subseteq T_{i}$, and $\alpha,\beta\geq 1$, we define the linear program
$\mathrm{CLP}_{\geq i}(T^{*},\alpha,\beta)$. Here, $\alpha$ is a parameter
that stands for the coverage requirement, i.e., that every covered sink
receives value at least $1/\alpha$, and $\beta$ stands for the allowed
congestion.

In order to model the submodular function requirement, we make use of
configuration sets $\mathcal{C}(v,\alpha,\beta)$ for each sink $v\in T^{*}$.
These configurations are the integral flows $g$ in $G_{i}$ starting in the
sources $S_{i}$ and ending in $v$, such that the congestion of $g$ is at most
$\beta$ and the coverage of $v$, that is, $f_{v}(g\cap\delta(v))$, is at least
$1/\alpha$. Each sink in $T^{*}$ needs to pick one configuration subject to
constraints that will be explained below. The sum of all configurations stands
for the flow $g_{i}$ in level $i$.

The linear program $\mathrm{CLP}_{\geq i}(T^{*},\alpha,\beta)$ contains the
variable sets $b_{v,g}\in\mathbb{R}_{\geq 0}^{E_{\geq i}}$ and
$x_{v,g}\in\mathbb{R}_{\geq 0}$ for all $v\in
T^{*},g\in\mathcal{C}(v,\alpha,\beta)$, as well as parameter (fixed constant)
$b\in[0,\beta]^{E_{\geq i}}$. Here, $b(e)$ describes a ”budget” of how much
flow is allowed to pass through edge $e$, i.e., an upper bound on $g_{i}(e)$
where $E_{i}\ni e$. Including $b$ is necessary for the recursive definition.
The budget is decomposed further into $b_{v,g}(e)$, which describes how much
of $b(e)$ is used by the sink $v\in T^{*}$ together with configuration $g$,
using the intuition of a fixed path decomposition as before, which allows us
to trace each unit of flow back to one of the sinks in $T^{*}$. We write
$(b,b_{v,g},x_{v,g})\in\mathrm{CLP}_{\geq i}(T^{*},\alpha,\beta)$ if these
variables and parameters are feasible. Let $\mathrm{B}_{\geq
i}(T^{*},\alpha,\beta)$ be the set of feasible values $b\in[0,\beta]^{E_{\geq
i}}$ for $\mathrm{CLP}_{\geq i}(T^{*},\alpha,\beta)$, i.e.,
$b\in\mathrm{B}_{\geq i}(T^{*},\alpha,\beta)$ if and only if there exist
$b_{v,g},x_{v,g}$ such that $(b,b_{v,g},x_{v,g})\in\mathrm{CLP}_{\geq
i}(T^{*},\alpha,\beta)$. $\mathrm{B}_{\geq i}(T^{*},\alpha,\beta)$ forms a
polytope, which can be seen from turning $b$ into variables in $\mathrm{CLP}$
and then projecting to $b$. We are now ready to state the linear program
completely.

Multi-level configuration LP, $\mathrm{CLP}_{\geq i}(T^{*},\alpha,\beta)$
$\displaystyle\sum_{g\in\mathcal{C}(v,\alpha,\beta)}x_{v,g}$
$\displaystyle\geq 1$ $\displaystyle\forall v\in T^{*}$ (1)
$\displaystyle\sum_{v\in
T^{*}}\sum_{g\in\mathcal{C}(v,\alpha,\beta)}b_{v,g}(e)$ $\displaystyle\leq
b(e)$ $\displaystyle\forall e\in E_{\geq i}$ (2) $\displaystyle g(e)\cdot
x_{v,g}$ $\displaystyle=b_{v,g}(e)$ $\displaystyle\forall v\in
T^{*},g\in\mathcal{C}(v,\alpha,\beta),$ (3) $\displaystyle e\in E_{i},$
$\displaystyle(b_{v,g}(e))_{e\in E_{\geq i+1}}$ $\displaystyle\in
x_{v,g}\cdot\mathrm{B}_{\geq i+1}(L_{i}(g\cap S_{i}),\alpha,\beta)$
$\displaystyle\forall v\in T^{*},g\in\mathcal{C}(v,\alpha,\beta)$ (4)
$\displaystyle x_{v,g}$ $\displaystyle\geq 0$ $\displaystyle\forall v\in
T^{*},g\in\mathcal{C}(v,\alpha,\beta)$ (5) $\displaystyle b_{v,g}(e)$
$\displaystyle\geq 0$ $\displaystyle\forall v\in
T^{*},g\in\mathcal{C}(v,\alpha,\beta),$ (6) $\displaystyle e\in E_{\geq i}$

For the last level $i=h$ we omit Constraint (4).

Constraint (1) ensures that each sink in $T^{*}$ selects one configuration.
Constraint (2) enforces the relationship between $b(e)$ and $b_{v,g}(e)$.
Constraint (3) guarantees that $b_{v,g}(e)$ correctly represents the amount of
flow on edge $e$ caused by $v$ and $g$ in level $i$.

The last Constraint (4) requires some more elaboration. First, we verify that
it is indeed a polyhedral constraint: for some $v,g$, the values $x_{v,g}$ and
$b_{v,g}(e)$, $e\in E_{\geq i+1}$, that satisfy (4) are exactly those
generated by the polyhedral cone with extreme rays $x_{v,g}=1$ and
$b_{v,g}(e)$, $e\in E_{\geq i+1}$, being a vertex of $\mathrm{B}_{\geq
i+1}(L_{i}(g\cap S_{i}),\alpha,\beta)$.

The intuition of the constraint is that if $v$ is covered via the flow $g$,
then $L_{i}(g\cap S_{i})$ need to be covered in the next level. However, it is
not sufficient that $\mathrm{CLP}_{\geq i+1}(L_{i}(g\cap S_{i}),\alpha,\beta)$
is feasible, since several sinks in $T_{i}$ (not just $v$) share the budget on
edges in $E_{\geq i+1}$. Hence, we use $b_{v,g}(e)$ to store the budget used
by $v$ (together with configuration $g$). Constraint 2 then ensures that the
flow used by all sinks together does not exceed the budget. In the uncongested
case and with the intuition of the forest-like structure, this simply says
that the trees rooted in different sinks of $T^{*}$ are edge-disjoint.
Formally, the fact that we can separately consider solutions induced by the
different sinks $L_{i}(g\cap S_{i})$ in the next level is justified by the
following lemma.

######  Lemma 4.

Let $T^{*},T^{**}$ be disjoint sets of sinks and let $b\in[0,\beta]^{E_{\geq
i}}$. Then $b\in\mathrm{B}_{\geq i}(T^{*}\cup T^{**},\alpha,\beta)$ if and
only if there exist $b^{\prime}+b^{\prime\prime}=b$ with
$b^{\prime}\in\mathrm{B}_{\geq i}(T^{*},\alpha,\beta)$ and
$b^{\prime\prime}\in\mathrm{B}_{\geq i}(T^{**},\alpha,\beta)$.

This means that for an integral uncongested solution Constraint (4) is
equivalent to

$(b(e))_{e\in E_{\geq i+1}}\in B_{\geq i+1}(L_{i}(g_{i}\cap S_{i}),1,1)\ ,$

where $g_{i}=\sum_{v\in T^{*}}\sum_{g\in\mathcal{C}(v,\alpha,\beta)}x_{v,g}g$.
The implication uses the fact that $L_{i}(g^{\prime}\cap S_{i})$ and
$L_{i}(g^{\prime\prime}\cap S_{i})$ must be disjoint for different
$g^{\prime},g^{\prime\prime}$ used by the solution: $g^{\prime}\cap S_{i}$ and
$g^{\prime\prime}\cap S_{i}$ are disjoint since each vertex in $S_{i}$ has
out-degree $1$, enforcing a vertex capacity of $1$ on $S_{i}$ and
$L_{i}(\cdot)$ is injective. The proof of the lemma is straight-forward and
deferred to Appendix B.

##  3 Reduction to the augmentation problem

We now present the reduction of the Submodular Santa Claus problem to the
augmentation problem that we have introduced in Section 2.1.

In order to devise a $\gamma$-approximation algorithm, by a standard binary
search framework it suffices for a given $\eta$ to either find a solution of
value at least $\eta/\gamma$ or to determine that $\mathrm{OPT}<\eta$.
Furthermore, by scaling all functions $f_{p}$ we may assume that $\eta=1$.

###  3.1 From general instances to canonical instances.

We will first reduce to the following _canonical instances_.

#### Canonical instance.

As mentioned above we need to either determine that $\mathrm{OPT}<1$ or find a
solution of value at least $1/\gamma$. We distinguish between _basic players_
$B$ and _complex players_ $C$.

For a basic player $p\in B$, we have that $f_{p}(S)\in\\{0,1\\}$ for all
$S\subseteq R$. Notice that $f_{p}(S)=1$ if and only if $S$ contains a
resource $r$ with $f_{p}(\\{r\\})=1$. We may therefore assume without loss of
generality that each basic player gets exactly one resource of value $1$ in a
solution.

Each complex player $p$ has a private resource $r(p)$ with
$f_{p}(\\{r(p)\\})=1$ and $f_{q}(\\{r(p)\\})=0$ for all complex players $q\neq
p$. Similar to before, we may assume that if player $p$ gets $r(p)$ in a
solution then $p$ does not get any other resources. For all resources $r\neq
r(p)$, we have $f_{p}(\\{r\\})<1/\gamma$.

#### Reduction to canonical instances.

In a general instance, we split each player $p\in P$ into a basic player
$p^{\prime}$ and a complex player $p^{\prime\prime}$ and we introduce an
additional resource $r(p^{\prime\prime})$ which has value
$f_{p^{\prime}}(\\{r(p^{\prime\prime})\\})=f_{p^{\prime\prime}}(\\{r(p^{\prime\prime})\\})=1$
for $p^{\prime}$ and $p^{\prime\prime}$ and value $0$ for all other players.
For player $p$, we define $R_{p}^{(b)}$ the set of resources $r$ such that
$f_{p}(\\{r\\})\geq 1/\gamma$ (i.e. the big resources for $p$). Then, we can
define the submodular valuation function for player $p^{\prime}$ as follows.

$f_{p^{\prime}}(S):=\begin{cases}1\mbox{ if
$S\cap(R_{p}^{(b)}\cup\\{r(p^{\prime\prime})\\})\neq\emptyset$,}\\\ 0\mbox{
otherwise.}\end{cases}$

For player $p^{\prime\prime}$, we define the submodular valuation function as
follows

$f_{p^{\prime\prime}}(S):=\begin{cases}1\mbox{ if $r(p^{\prime\prime})\in
S$,}\\\ f_{p}(S\setminus R_{p}^{(b)})\mbox{ otherwise.}\end{cases}$

Note that the resource $r(p^{\prime\prime})$ can cover either $p^{\prime}$ or
$p^{\prime\prime}$. This corresponds intuitively to the fact that $p$ needs
either small resources that sum up to a large value or a single resource of
sufficiently large value. Note that in the above construction $p^{\prime}$ is
a basic player which values only the additional resource $r(p^{\prime\prime})$
or the big resources of $p$, while $p^{\prime\prime}$ is a complex player
which values only the additional resource or the small resources of $p$.

It is easy to see that a solution of value at least $1$ in the original
instance can be transformed to a solution of value at least $1$ in the
canonical instance: if a player $p$ receives at least one big resource $r$ in
the orginal instance such that $f_{p}(r)\geq 1/\gamma$, we give that same
resource to the corresponding basic player $p^{\prime}$ in the canonical
instance, and the complex player $p^{\prime\prime}$ is given the additional
resource $r(p^{\prime\prime})$. On the other hand, if a player $p$ does not
receive any big resource, we give the resource $r(p^{\prime\prime})$ to the
basic player $p^{\prime}$ in the canonical instance, and the complex player
$p^{\prime\prime}$ receives the same resources as $p$ receives in the original
instance.

Conversely, it is easy to see that a solution of value at least $1/\gamma$ in
the canonical instance can be transformed to a solution of value at least
$1/\gamma$ in the original instance. Indeed, if a pair of players
$p^{\prime},p^{\prime\prime}$ (corresponding to one player $p$ in the original
instance) both receive value at least $1/\gamma$, it must be that either (a)
$p^{\prime}$ does not receive the resource $r(p^{\prime\prime})$ hence
$p^{\prime}$ must receive one resource of value at least $1/\gamma$ for $p$ in
the original instance, or (b) the player $p^{\prime\prime}$ does not receive
the resource $r(p^{\prime\prime})$ hence must receive a bundle of resources
$S$ of total value at least $1/\gamma$ for player $p$ in the original
instance. In both cases, the original player $p$ is covered.

Hence, it suffices to devise an algorithm for the canonical instance.

###  3.2 From canonical instances to augmentation problem

Consider a partial assignment of resources $\sigma:R\rightarrow
P\cup\\{\bot\\}$, where symbol $\bot$ is used to describe that a resource is
not assigned to any player. From a canonical instance, partial assignment
$\sigma$, and a parameter $h\in\mathbb{N}$, we will construct an instance
$I(\sigma,h)$ of the augmentation problem that closely relates to potential
reassignments of resources. Parameter $h$, the number of levels in the
instance, will influence the approximation ratio and the running time. First,
we define

$\overline{\sigma}(r)=\begin{cases}\sigma(r)\mbox{ if }\sigma(r)\neq\bot\mbox{
and }f_{\sigma(r)}(\\{r\\})=1\ ,\\\ \bot\mbox{ otherwise.}\end{cases}$

Intuitively, the assignment $\overline{\sigma}$ is equal to the assignment
$\sigma$ except that all complex players release the small resources assigned
to them. Notice that in this new assignment $\overline{\sigma}$, a complex
player $p$ can only receives its unique big resource $r(p)$, if any. The
intuition here is that this greatly simplifies the structure of potential
reassignments, since every player can now only give up a single resource
(i.e., has an out-degree of at most $1$). Thus, reassignments can be thought
of as directed trees.

#### Construction of augmentation instance.

All our $h$ levels will feature the same graph, which is defined as follows.
Let $G=(V,E)$ where $V$ consists of all resources $R$, all basic players $B$,
two copies of the complex players, which we denote by $C^{S}$ and $C^{T}$, a
vertex $t$ and a vertex $s(r)$ for each currently unassigned resource $r$
(i.e., $\overline{\sigma}(r)=\bot$). For each resource $r$ and each $q\in
B\cup C^{T}$ for which $f_{q}(\\{r\\})>0$ there is an edge from each $r$ to
$q$ if $\overline{\sigma}(r)\neq q$. Further, for each $q\in B\cup C^{S}$ and
each resource $r$ which is currently assigned to $q$ (in the assignment
$\overline{\sigma}$) there is an edge from $q$ to $r$. Recall that by
definition of $\overline{\sigma}$ this implies that $f_{q}(\\{r\\})=1$.
Finally, there is an edge from $s(r)$ to $r$ for each unassigned resource $r$
and an edge from each basic player that is currently not assigned any resource
to $t$ (again referring to the assignment $\overline{\sigma}$).

The sinks are $t$ and the copies $C^{T}$, and the sources are $s(r)$ for
unassigned resources $r$ and the copies $C^{S}$. The incoming edges for some
$p\in C^{T}$ all come from resources and thus, a set $A\subseteq\delta(p)$
naturally corresponds to the set of resources incident to it. We define
$f_{p}(A)$ as the function value for these resources and complex player $p$ in
the canonical instance.

For vertex $t$ we define $f_{t}(A)=|A|/|\delta(t)|$ for each
$A\subseteq\delta(t)$. Notice that this function is linear, hence submodular.

In the reassignment of resources corresponding to the optimal solution, any
complex player $p$ whose private resource $r(p)$ is taken away would receive a
lot of other resources. The intuition for $C^{T}$ and $C^{S}$ is that we do
not strictly enforce this: from the copies in $C^{S}$ we potentially take away
the private resource and the copies in $C^{T}$ potentially receive a lot of
other resources, but consistency is not enforced. This relaxation is to make
it easier to find a good reassignment. However, we still have to strengthen
this relaxation to avoid that a reassignment simply takes away all private
resources from $C^{S}$ without being able to cover them with other resources.

Towards this, we build a multi-level instance of the augmentation problem by
stacking several copies of the graph defined as above on top of each other.
Then we connect these graphs together by some linking edges. Formally, for
each $1\leq i<h$ and every complex player $p$, we add a linking edge from the
vertex in $C^{T}$ corresponding to player $p$ in level $i+1$ to the vertex in
$C^{S}$ corresponding to the player $p$ in level $i$.

By construction, this enforces that if the unique resources of some complex
players $A\subseteq C^{S}$ of level $i$ are removed, then in the next level
there must be a solution that gives a lot of resources to the elements in
$C^{T}$ of level $i+1$ that correspond to $A$.

We denote by $I(\sigma,h)$ the multi-level augmentation instance obtained as
above.

#### Existence of an augmentation.

In the following lemma we prove that the instance $I(\sigma,h)$ as above is
feasible, assuming that the canonical instance is.

######  Lemma 5.

Consider the instance $I(\sigma,h)$ of the augmentation problem, where
$\sigma$ is an arbitrary assignment of resources. If there exists a solution
of value $1$ for the canonical instance, then there exists a solution with
coverage $\alpha=1$ and congestion $\beta=1$ for $I(\sigma,h)$ for any $h\geq
1$, which covers the sink $t$ in level $1$.

###### Proof.

As a solution, we define the same flow in each level. Let
$\sigma_{\mathrm{OPT}}$ be the optimal assignment in the canonical instance,
and $\overline{\sigma}$ the modified assignment derived from $\sigma$ as
before. We assume that there is no resource $r$ such that
$\sigma_{\mathrm{OPT}}=\bot$. This is without loss of generality, because we
can always assign this resource to an arbitrary player and modify
$\sigma_{\mathrm{OPT}}$ accordingly.

For simplicity of notation, we denote by $(p,r)$ the edge from the vertex
corresponding to player $p$ to the resource $r$. Notice that if $p$ is a
complex player, which means that there are two vertices corresponding to $p$,
this edge only exists from the copy of $p$ in $C^{S}$. Thus, the edge is
uniquely defined. Similarly, we denote by $(r,p)$ the edge from a resource $r$
to a player $p$. Again, if $p$ is a complex player, the edge must go to
$C^{T}$. We also have edges $(s(r),r)$ for unassigned resource $r$ and edges
$(p,t)$ for uncovered players to $t$.

The solution flow $g_{i}(e)$ for each level $i$ and some edge $e$ is defined
by

$g_{i}(e)=\begin{cases}1\quad\mbox{ if $e=(p,r)$ and
$\overline{\sigma}(r)\neq\sigma_{\mathrm{OPT}}(r)$},\\\ 1\quad\mbox{ if
$e=(r,p)$ and $\sigma_{\mathrm{OPT}}(r)=p$},\\\ 1\quad\mbox{ if
$e=(s(r),r)$},\\\ 1\quad\mbox{ if $e=(p,t)$},\\\ 0\quad\mbox{
otherwise.}\end{cases}$

It is easy to verify the validity of this solution since our flow solution
mimics the optimal assignment. One can verify that the sink $t$ in level $1$
is covered since all uncovered basic players send a flow of $1$ to $t$, and
the congestion is clearly at most $1$ on any edge.

Second, any player vertex $p$ which is not a source nor a sink must be a basic
player. Therefore, if the corresponding vertex is traversed by some flow,
there is one unit of outgoing flow since $p$ is assigned at most one big
resource in $\overline{\sigma}$, and exactly one unit of in-going flow since
$p$ receives only one big resource in $\sigma_{\mathrm{OPT}}$. Hence we have
the flow conservation at all player vertices. The case of resource vertices is
very similar, the resource is assigned to exactly one player in
$\sigma_{\mathrm{OPT}}$ and at most one in $\overline{\sigma}$, and it is easy
to verify that flow conservation holds at the corresponding vertex. Either the
resource is not traversed by any flow if both $\overline{\sigma}$ and
$\sigma_{\mathrm{OPT}}$ agree on that resource, or it is traversed by exactly
one flow unit.

Finally, in the flow solution $g_{i}$, the set of vertices in $C^{S}$ which
send some flow corresponds to a set of complex players which give up their big
resource in the reassignment. But since $\sigma_{\mathrm{OPT}}$ covers all
players, it must be that those players are covered by some small resources,
hence the corresponding sinks in $C^{T}$ will receive enough flow in the
assignment $g_{i+1}$, which satisfies the constraint related to the linking
edges between $C^{S}$ in one layer and $C^{T}$ in the next layer. ∎

#### Approximate solution with additional structure.

By Lemma 5 we know that $I(\sigma,h)$ will have a feasible solution, assuming
the canonical instance is feasible. We will show next that by a negligible
loss we can simplify any solution to obey a structure that will later help in
actually augmenting the assignment $\sigma$.

######  Lemma 6.

Let $\alpha,\beta\in\mathbb{N}$ and $h\geq 1+\log(\beta
n^{2})/\log(\gamma/(2\alpha))$ and consider the instance $I(\sigma,h)$
constructed from the assignment $\sigma$.

Any solution $g_{1},g_{2},\dotsc,g_{h}$ of coverage $\alpha$ and congestion
$\beta$ that covers $t$ in level $1$ can be turned in polynomial time into a
solution $g^{\prime}_{1},g^{\prime}_{2},\dotsc,g^{\prime}_{h}$ with coverage
$2h\alpha$ and congestion $\beta$ such that

  1. 1.

either (a) $g_{1}$ uses none of the source in $C^{S}$ (only the sources
$s(r)$) or (b) $g_{1}$ does not use sources $s(r)$ (and therefore only
$C^{S}$); and

  2. 2.

$g_{h}$ does not use any sources in $C^{S}$ (only potentially sources $s(r)$)
.

###### Proof.

Let $i$ be a level and consider a path decomposition of $g_{i}$ into paths
that each send unit flows. We define weights for each path corresponding to
the marginal values. Specifically, for a sink $v$ and an arbitrary ordering of
the paths $P_{1},P_{2},\dotsc$ that end in $v$, set

$\displaystyle w(i,P_{j})$ $\displaystyle:=f_{p}(\delta(v)\cap
P_{j}\mid\delta(v)\cap\\{P_{1},P_{2},\ldots,P_{j-1}\\})$
$\displaystyle=f_{p}(\delta(v)\cap\\{P_{1},P_{2},\ldots,P_{j}\\})-f_{p}(\delta(v)\cap\\{P_{1},P_{2},\ldots,P_{j-1}\\})\
.$

The total weight of paths ending in a covered sink is at least $1/\alpha$.

For the construction we need the notion of a subtree: with each path $P$ (in
some level $i$) we can associate the following subtree of paths: if $P$ starts
in some source $s(r)$, then the subtree only contains $P$. If it starts in
some vertex of $C^{S}$ corresponding to a complex player $p$, then we
associate with $P$ all paths in level $i+1$ that end in the corresponding
vertex of $C^{T}$ and their recursively defined subtrees.

Now, if the paths to sink $t$ in level $1$ that start in one of the sources
$s(r)$ have weight at least $|\delta(t_{1})|/(2\alpha)$, then we simply keep
these paths and delete all the others as well as all flows in later levels.
The obtained flow loses only a factor of $2$ in the coverage at $t$ in level
$1$ due to submodularity and satisfies the conditions of (1a) and (2).

Otherwise, it must be that paths of level $1$ that start in $C^{S}$ and end in
$t$ have a total weight of at least $|\delta(t_{1})|/(2\alpha)$. We drop all
other paths including their subtrees, thus satisfying (1b). Next, we proceed
to establish Property (2). We assume without loss of generality that the
solution is minimal in the sense that it contains exactly the subtree of $t$
in level $1$ and no other paths.

We mark the covered complex player vertices according to their “depth”. Every
vertex in $C^{T}$ of some level $i\geq 1$, which receives more than a $1/(2h)$
fraction of its weight through paths from a source $s(r)$ in the same level,
is marked as _depth-1_ vertex, and we delete all other paths that end in them
(along with their subtree). The corresponding vertices of $C^{S}$ in level
$i-1$ (linked to the marked one via linking edges) are considered to have the
same depth of $1$.

Then we proceed iteratively. Having marked all vertices up to depth $\ell$ for
some $\ell\geq 1$, we say that every unmarked vertex in $C^{T}$ of some level
$i\geq 1$, which receives more than a $1/(2h)$ fraction of its weight via
paths from depth-$\ell$ vertices in $C^{S}$ of the same level are marked as
depth-$(\ell+1)$ vertices (together the corresponding vertices in $C^{S}$ of
level $i-1$), and we delete all other paths that end in them along with the
corresponding subtree.

We claim that if we choose $h$ as in the lemma then all covered complex
players of level $2$ are marked by iteration $\ell=h-1$. Assume otherwise. Let
$p\in C^{T}$ be the complex player of level $2$, which is not marked. Since
this player is unmarked, it receives less than a $1/(2h)$ fraction of his flow
from the sources $s(r)$ or level-$\ell^{\prime}$ players, for any
$1\leq\ell^{\prime}<h$. Furthermore, there cannot be depth-$h$ players in
level $2$, since the remaining levels are only $h-1$. Hence, it must be that
at least a $1/2$ fraction of his weight comes from unmarked players. Applying
the same argument recursively, the player $p$ in level $2$ must be the root of
a tree of depth $h-1$ with minimum out-degree at least $\gamma/(2\alpha)$,
since by construction every resource has marginal value at most $1/\gamma$.

It follows that the number of paths in level $h$ is at least

$(\gamma/(2\alpha))^{h-1}>\beta n^{2}\ ,$

which is a contradiction since then some edge would have congestion more than
$\beta$.

Notice that at the end of this process, none of the sources in $C^{S}$ are
used, since the leafs of subtrees induced by players $C^{T}$ of level $2$
start in $s(r)$ of some level. In this process, we lost an approximation
factor of at most $2h$, which concludes the proof. ∎

###  3.3 From approximate augmentation to canonical instance solution

Our approach is to start with a solution that covers all complex players $p$
with their private resource $r(p)$ and we iteratively reduce the number of
basic players that are not covered while maintaining a good coverage of the
complex players. During this process, it will be helpful to maintain an
assignment $\sigma_{k}:R\rightarrow P$ of resources to players, for every
iteration $k=1,2,\dotsc$

######  Lemma 7 (Augmentation).

Let $\alpha,\beta,k\in\mathbb{N}$ and $h\geq 1+\log(\beta
n^{2})/\log(\gamma/(2\alpha))$. Assume that there exists a solution of value
$1$ for the canonical instance with parameter $\gamma$. Given an assignment
$\sigma_{k}$ for this canonical instance where each complex player gets a
value of at least $1/(8\alpha\beta h^{2}k)-4k/\gamma$, and a solution to the
augmentation problem $I(\sigma_{k},h)$ with coverage $\alpha$ and congestion
$\beta$, one can find in polynomial time an assignment $\sigma_{k+1}$ where
each complex player gets a value of at least $1/(8\alpha\beta
h^{2}(k+1))-4(k+1)/\gamma$ and the number of basic players not covered reduces
by a factor of $(1-1/(4h\alpha\beta))$.

###### Proof.

We first take away all resources $r\neq r(q)$ from each complex player $q$ to
obtain the assignment $\overline{\sigma}_{k}$, as in the construction of the
augmentation instance. With Lemma 6, we transform the solution to the
augmentation problem for the assignment $\overline{\sigma}_{k}$ into an
augmentation solution $g_{1},\dotsc,g_{h}$ covering $t$ in level $1$ that has
coverage $2h\alpha$, congestion $\beta$, and the structural assumptions
mentioned. In particular, the solution is of one of two types, for which we
derive the assertion separately.

#### Flow $g_{1}$ does not use $C^{S}$.

Assume that $g_{1}$ uses only sources $s(r)$. This means $g_{1}$ forms a flow
of at least $|\delta(t)|/(2h\alpha)$ from sources $s(r)$ to $t$ with
congestion $\beta$. Consider the fractional flow $g_{1}/\beta$. This flow has
congestion at most $1$ and flow value at least $|\delta(t)|/(2h\alpha\beta)$.
By standard flow arguments we can then also find an integral flow $g$ from
sources $s(r)$ to $t$ with congestion $1$ and flow value at least
$|\delta(t)|/(2h\alpha\beta)$. This flow can be interpreted as a reassignment
of resources. Let us denote by $\sigma_{k}^{\prime}$ the assignment obtained
from $\overline{\sigma}_{k}$ following the reassignment. $\sigma_{k}^{\prime}$
covers a $1/(2h\alpha\beta)$-fraction of previously uncovered basic players
and each basic player covered in $\overline{\sigma}_{k}$ remains covered.

However, it might be that some complex players covered in $\sigma_{k}$ by
small resources are not covered anymore in $\overline{\sigma}_{k}$, hence not
covered either in $\sigma_{k}^{\prime}$. Consider such a complex player $p$.
We have two cases.

If at least two of the small resources that are assigned to $p$ in
$\sigma_{k}$ are taken away by some other player in $\sigma_{k}^{\prime}$,
then we give $p$ back the private resource $r(p)$ and modify the assignment
$\sigma_{k}^{\prime}$ accordingly. If $r(p)$ is taken by some basic player in
$\sigma_{k}^{\prime}$, this results in the basic player being uncovered.

Otherwise, we modify $\sigma_{k}^{\prime}$ by giving to $p$ all the resources
it was assigned in $\sigma_{k}$, except for the one resource $r$ (if any) that
is already used in $\sigma_{k}^{\prime}$. Notice that in that case, $p$
receives value at least

$f_{p}(R^{\prime}\setminus\\{r\\})\geq
f_{p}(R^{\prime})-f_{p}(\\{r\\})\geq\frac{1}{8\alpha k\beta
h^{2}}-\frac{4k}{\gamma}-\frac{1}{\gamma}\geq\frac{1}{8\alpha(k+1)\beta
h^{2}}-\frac{4(k+1)}{\gamma}\ ,$

where $R^{\prime}$ are the resources that were assigned to $p$ in
$\sigma_{k}$. We let $\sigma_{k+1}$ be the assignment resulting from these
modifications.

To conclude the analysis of this case, let $N$ be the number of complex
players which take back their private resource in the first case above. For
each one of these players, we uncover one basic player, but each of these
players also sends $2$ flow units to $t$ via different paths. Hence, the
change in the number of covered basic players is at least

$\max\\{2N-N,\frac{|\delta(t)|}{2h\alpha\beta}-N\\}\geq\frac{|\delta(t)|}{4h\alpha\beta}\
,$

where $|\delta(t)|$ is the number of previously uncovered basic players.

#### Flow $g_{1}$ only uses $C^{S}$.

Define $g=g_{1}+g_{2}+\cdots+g_{h}$. Let $X\subseteq C$ be the complex players
for which the corresponding vertex in $C^{S}$ has any outgoing flow in $g$ and
let $Y\subseteq C\setminus X$ be the complex players $p$ that are not assigned
their private resource $r(p)$ in $\sigma_{k}$. By Lemma 6, the flow $g$ has
the following properties:

  1. 1.

$g(e)\leq\beta h$ for all $e\in E$,

  2. 2.

the incoming flow to $t$ is at least $|\delta(t)|/(2h\alpha)$,

  3. 3.

For each $p\in X$ the corresponding copy $p^{T}\in C^{T}$ satisfies
$f_{p^{T}}(\delta(p^{T})\cap g)\geq 1/(2h\alpha)$.

The last property holds because $C^{S}$ in the last level is not used. For
$p\in X$ and the corresponding copy $p^{T}\in C^{T}$ write
$E(p)=g\cap\delta(p^{T})$ and for $p\in Y$ we define $E(p)$ as the edges from
$s(r)$ to $r$ for resources $r$ assigned to $p$ in $\sigma_{k}$ (those that
were removed from $p$ in $\overline{\sigma}_{k}$).

For some $p\in X\cup Y$ let $\\{e_{1},e_{2},\dotsc,e_{\ell}\\}=E(p)$ be an
arbitrary but fixed order of the set $E(p)$. We define a partition
$E(p)=E_{1}(p)\cup E_{2}(p)\cup\dotsc$ by marginal value, with $E_{i}(p)$
consisting of all $e_{j}$ with

$2^{-(i-1)}>f_{p^{T}}(\\{e_{1},\dotsc,e_{j}\\})-f_{p^{T}}(\\{e_{1},\dotsc,e_{j-1}\\})\geq
2^{-i}\ .$

Notice that $E_{1}(p),E_{2}(p),\dotsc,E_{\lfloor\log\gamma\rfloor}(p)$ are
actually empty, since $f_{p}(\\{e\\})\leq\gamma$ for all $e\in E(p)$. We can
now find an integer flow $g^{\prime}$ with

  1. 1.

$g^{\prime}(e)\in\\{0,1\\}$ for all $e\in E$

  2. 2.

the incoming flow to $t$ is at least $\frac{|\delta(t)|}{4h\alpha\beta}$

  3. 3.

For each $p\in X\cup Y$ and $i=1,2,\dotsc$ we have

$\lfloor\frac{g(E_{i}(p))}{2(k+1)\beta h}\rfloor\leq
g^{\prime}(E_{i}(p))\leq\lceil\frac{g(E_{i}(p))}{2(k+1)\beta h}\rceil\ .$

This holds because the fractional flow $g_{1}/2+g/(2(k+1)\beta h)$ satisfies
Properties 2 and 3 and has congestion at most $1$: here notice that $g_{1}$
has no flow on any of the edge sets $E_{i}(p)$. Arguing with dummy vertices
for each set $E_{i}(p)$, it follows easily by standard flow arguments that
this fractional flow is a convex combination of flows that satisfy 1 and 3, at
least one out of which then also satisfies 2.

We use this flow $g^{\prime}$ to transform $\sigma_{k}$ into a new assignment
$\sigma_{k+1}$ in the natural way: From the flow $g^{\prime}$ we can transform
$\overline{\sigma}_{k}$ (itself obtained from $\sigma_{k}$) into a new
assignment $\sigma_{k}^{\prime}$. Then, we modify $\sigma_{k}^{\prime}$ by
giving to each player $p\in Y$ all the resources that $p$ was assigned in
$\sigma_{k}$ and that are not traversed by any flow in $g^{\prime}$. This
constitutes our final assignment $\sigma_{k+1}$. We will analyze that the new
assignment satisfies the properties in Lemma 7.

First, each basic player that loses its current resource gets a new resource,
because basic players are not sources. This means that all basic players that
had a resource in the current assignment, still have one in the new
assignment. Furthermore, for each unit of incoming flow to $t$, there must be
one basic player that previously did not have a resource and now gets one.
This means that the number of basic players that do not have a resource
decreases by a factor of $(1-1/(4h\alpha\beta))$.

Consider now a complex player $p\in X$, i.e., $p$ may lose its private
resource $r(p)$. Then the value of the resources assigned to $p$ through the
reassignment is

$\displaystyle f_{p}(E(p)\cap g^{\prime})$
$\displaystyle\geq\sum_{i=1}^{\infty}2^{-i}\cdot g^{\prime}(E_{i}(p))$
$\displaystyle\geq\sum_{i=1}^{\infty}2^{-i}\cdot\lfloor\frac{g(E_{i}(p))}{2(k+1)\beta
h}\rfloor$ $\displaystyle\geq\frac{1}{4(k+1)\beta
h}\sum_{i=1}^{\infty}2^{-(i-1)}\cdot
g(E_{i}(p))-\sum_{i=\lfloor\log_{2}(\gamma)\rfloor}^{\infty}2^{-i}$
$\displaystyle\geq\frac{1}{4(k+1)\beta h}f_{p}(E(p)\cap g)-\frac{4}{\gamma}$
$\displaystyle\geq\frac{1}{4(k+1)\beta
h}\cdot\frac{1}{2h\alpha}-\frac{4}{\gamma}$
$\displaystyle\geq\frac{1}{8\alpha\beta h^{2}(k+1)}-\frac{4(k+1)}{\gamma}\ .$

Finally, consider a complex player $p\in Y$, i.e., $p$ is not assigned $r(p)$
in the assignment $\sigma_{k}$. The reassignment may further take away
resources, but we will argue that $p$ retains a large value. More precisely,
the value of resources that $p$ still has after the reassignment is

$\displaystyle f_{p}(E(p)\setminus E(g^{\prime}))$ $\displaystyle\geq
f_{p}(E(p))-\sum_{i=1}^{\infty}2^{-(i-1)}\cdot g^{\prime}(E_{i}(p))$
$\displaystyle\geq
f_{p}(E(p))-\sum_{i=1}^{\infty}2^{-(i-1)}\cdot\lceil\frac{g(E_{i}(p))}{2(k+1)\beta
h}\rceil$ $\displaystyle\geq f_{p}(E(p))-\frac{1}{(k+1)\beta
h}\sum_{i=1}^{\infty}2^{-i}\cdot
g(E_{i}(p))-\sum_{i=\lceil\log_{2}(\gamma)\rceil}^{\infty}2^{-i}$
$\displaystyle\geq f_{p}(E(p))\left(1-\frac{1}{(k+1)\beta
h}\right)-\frac{4}{\gamma}$ $\displaystyle\geq\left(\frac{1}{8\alpha\beta
h^{2}k}-\frac{4k}{\gamma}\right)\left(1-\frac{1}{(k+1)}\right)-\frac{4}{\gamma}$
$\displaystyle\geq\frac{1}{8\alpha\beta h^{2}(k+1)}-\frac{4(k+1)}{\gamma}\ .$

We can conclude that the new assignment $\sigma_{k+1}$ satisfies our
desiderata in both cases. ∎

###### Proof of Theorem 2.

We repeatedly apply Lemma 7 with $h$ as specified in the lemma. After at most
$k=4h\alpha\beta\log(n)$ iterations all basic players are covered. According
to the lemma, in the resulting assignment each complex player receives a value
of at least

$\frac{1}{32\alpha^{2}\beta^{2}h^{3}\log(n)}-\frac{16h\alpha\beta\log(n)}{\gamma}\
.$

This is at least $1/\gamma$ provided that

$\gamma\geq 1000\alpha^{3}\beta^{3}h^{4}\log^{2}(n)\ .\qed$

##  4 Solving the linear programming relaxation

This section is devoted to proving the following theorem.

######  Theorem 8.

Let $\alpha=40$ and $\beta=10\log(n)$. There is a Las Vegas algorithm that
given some $b\in[0,\beta]^{E_{\geq i}}$ determines that $b\in\mathrm{B}_{\geq
i}(T^{*},\alpha,\beta)$ and finds corresponding variables for
$\mathrm{CLP}_{\geq i}(T^{*},\alpha,\beta)$ or finds a hyperplane that
separates $b$ from $\mathrm{B}_{\geq i}(T^{*},1,1)$. The algorithm makes
polynomially many recursive calls on $\mathrm{B}_{\geq i+1}$ and has otherwise
polynomial time overhead.

It follows immediately that one can find a solution to $\mathrm{CLP}_{\geq
1}(T^{*},\alpha,\beta)$ for a given $b\in[0,\beta]^{E}$ and $T^{*}\subseteq
T_{1}$ in time $n^{O(h)}$ with $\alpha,\beta$ as in the theorem.

###  4.1 Reduction to separation problem

In this subsection we reformulate the linear program using Dantzig-Wolfe
decomposition, which then can be solved using the Ellipsoid method. This will
reduce the proof of Theorem 8 to a certain separation problem, which we then
solve in the next subsection. Dantzig-Wolfe decomposition, see [12], is a
reformulation method of specific block structured linear programs. The
specific variant we are interested in is given in the following lemma.

######  Lemma 9.

Suppose we are given a linear program with $k$ sets of variables
$x^{(1)}\in\mathbb{R}^{n_{1}},x^{(2)}\in\mathbb{R}^{n_{2}},\dotsc,x^{(k)}\in\mathbb{R}^{n_{k}}$.
There are local constraints given by $B_{i}x^{(i)}\leq b^{(i)}$ for some
$B_{i}\in\mathbb{R}^{m_{i}\times n_{i}}$ and $b^{(i)}\in\mathbb{R}^{m_{i}}$ as
well as global constraints of the form $A_{1}x^{(1)}+\cdots+A_{k}x^{(k)}\leq
b^{(0)}$ for $A_{i}\in\mathbb{R}^{m_{0}\times n_{i}}$ and
$b^{(0)}\in\mathbb{R}^{m_{0}}$. We assume that each set
$Q_{i}=\\{x^{(i)}\in\mathbb{R}^{n_{i}}:B_{i}x^{(i)}\leq b^{(i)}\\}$ is a
polyhedral cone generated by a finite set of extreme rays $R_{i}$. Then this
linear program is feasible if and only if there is a solution to

$\displaystyle A_{1}\sum_{r\in R_{1}}\lambda^{(1)}_{r}r+\cdots+A_{1}\sum_{r\in
R_{k}}\lambda^{(k)}_{r}r$ $\displaystyle\leq b^{(0)}$
$\displaystyle\lambda^{(i)}$ $\displaystyle\in\mathbb{R}_{\geq 0}^{R_{i}}$
$\displaystyle\forall i=1,2,\dotsc,k$

###### Proof.

If there is a solution $x^{(1)},\dotsc,x^{(k)}$ to the original linear
program, then we can write each $x^{(i)}\in Q_{i}$ as a conic combination of
the extreme rays $R_{i}$. The corresponding weights $\lambda^{(i)}$ form a
solution to the reformulation.

Suppose on the other hand there exists a solution
$\lambda^{(1)},\dotsc,\lambda^{(k)}$ to the reformulation. Then
$x^{(i)}:=\sum_{r\in R_{i}}\lambda^{(i)}r\in Q_{i}$ is a solution to the
original linear program. ∎

This reformulation will be useful to us because it can greatly reduce the
number of constraints at the cost of increasing the number of variables. To
apply it, we first need to make some preparations. Let $\mathrm{X}_{\geq
i}(T^{*},\alpha,\beta)\subseteq\mathrm{B}_{\geq i}(T^{*},\alpha,\beta)$ be the
set of extreme points of the polytope, in particular,

$\mathrm{conv}(\mathrm{X}_{\geq i}(T^{*},\alpha,\beta))=\mathrm{B}_{\geq
i}(T^{*},\alpha,\beta)\ .$

Define further

$\displaystyle Q_{v,g}=\\{(x_{v,g},b_{v,g})\in\mathbb{R}_{\geq
0}\times\mathbb{R}_{\geq 0}^{E_{\geq i}}$ $\displaystyle:(b_{v,g}(e))_{e\in
E_{\geq i+1}}\in x_{v,g}\cdot\mathrm{B}_{\geq i+1}(L_{i}(g\cap
S_{i}),\alpha,\beta),$ $\displaystyle\quad g(e)\cdot x_{v,g}=b_{v,g}(e)\
\forall e\in E_{i}\\}\ .$

Then $Q_{v,g}$ is a polyhedral cone generated by the extreme rays
$(1,g,d)\in\mathbb{R}_{\geq 0}\times\mathbb{R}_{\geq
0}^{E_{i}}\times\mathbb{R}_{\geq 0}^{E_{\geq i+1}}$ for each
$d\in\mathrm{X}_{\geq i+1}(L_{i}(g\cap S_{i}),\alpha,\beta)$.

Given $b\in[0,\beta]^{E_{\geq i}}$ as fixed parameters, we apply Dantzig-Wolfe
decomposition (Lemma 9) to obtain the formulation
$\mathrm{CLP}^{\mathrm{DW}}$, which is equivalent to $\mathrm{CLP}$ in the
sense that one LP is feasible for $b$ if and only if the other is.

Dantzig-Wolfe decomposition of multi-level configuration LP,
$\mathrm{CLP}^{\mathrm{DW}}_{\geq i}(T^{*},\alpha,\beta)$
$\displaystyle\sum_{g\in\mathcal{C}(v,\alpha,\beta)}\sum_{d\in\mathrm{X}_{\geq
i+1}(L_{i}(g\cap S_{i}),\alpha,\beta)}y_{v,g,d}$ $\displaystyle\geq 1$
$\displaystyle\forall v\in T^{*}$ (7) $\displaystyle\sum_{v\in
T^{*}}\sum_{g\in\mathcal{C}(v,\alpha,\beta)}\sum_{d\in\mathrm{X}_{\geq
i+1}(L_{i}(g\cap S_{i}),\alpha,\beta)}g(e)\cdot y_{v,g,d}$ $\displaystyle\leq
b(e)$ $\displaystyle\forall e\in E_{i},$ (8) $\displaystyle\sum_{v\in
T^{*}}\sum_{g\in\mathcal{C}(v,\alpha,\beta)}\sum_{d\in\mathrm{X}_{\geq
i+1}(L_{i}(g\cap S_{i}),\alpha,\beta)}d(e)\cdot y_{v,g,d}$ $\displaystyle\leq
b(e)$ $\displaystyle\forall e\in E_{\geq i+1},$ (9) $\displaystyle y_{v,g,d}$
$\displaystyle\geq 0$ $\displaystyle\forall v\in
T^{*},g\in\mathcal{C}(v,\alpha,\beta),$ (10) $\displaystyle
d\in\mathrm{X}_{\geq i+1}(L_{i}(g\cap S_{i}),\alpha,\beta)$

It is now sufficient to either find a solution of $\mathrm{CLP}^{\mathrm{DW}}$
or a hyperplane that separates $b$ from all $b^{\prime}$ for which
$\mathrm{CLP}^{\mathrm{DW}}$ is feasible, i.e., from $\mathrm{B}_{\geq
i}(T^{*},\alpha,\beta)$. Since $\mathrm{CLP}^{\mathrm{DW}}$ has only
polynomially many constraints, it is useful to consider the dual, which has
polynomial dimension.

Dual of $\mathrm{CLP}^{\mathrm{DW}}_{\geq i}(T^{*},\alpha,\beta)$
$\displaystyle\min\sum_{e\in E_{\geq i}}b(e)\mu_{e}$ $\displaystyle-\sum_{v\in
T^{*}}\pi_{v}$ (11) $\displaystyle\sum_{e\in E_{i}}g(e)\mu_{e}+\sum_{e\in
E_{\geq i+1}}d(e)\mu_{e}$ $\displaystyle\geq\pi_{v}$ $\displaystyle\forall
v\in T^{*},g\in\mathcal{C}(v,\alpha,\beta),$ (12) $\displaystyle
d\in\mathrm{X}_{\geq i+1}(L_{i}(g\cap S_{i}),\alpha,\beta)$
$\displaystyle\pi_{v}$ $\displaystyle\geq 0$ $\displaystyle\forall v\in T^{*}$
(13) $\displaystyle\mu_{e}$ $\displaystyle\geq 0$ $\displaystyle\forall e\in
E_{\geq i}$ (14)

Our plan is to apply the Ellipsoid method to the dual using an approximate
separation problem, which we introduce below.

#### Separation problem.

Given dual variables $\pi_{v},\mu_{e}$ find $u^{*}\in T^{*}$,
$g^{*}\in\mathcal{C}(u^{*},\alpha,\beta)$, and $d^{*}\in\mathrm{B}_{\geq
i+1}(L_{i}(g\cap S_{i}),\alpha,\beta)$ such that

$\sum_{e\in E_{i}}g^{*}(e)\cdot\mu_{e}+\sum_{e\in E_{\geq
i+1}}d^{*}(e)\cdot\mu_{e}<\pi_{u^{*}}$

or determine that $\pi_{v},\mu_{e}$ satisfy all constraints (12) in the dual
of $\mathrm{CLP}^{\mathrm{DW}}_{\geq i+1}(T^{*},1,1)$.

######  Lemma 10.

Given an algorithm for the separation problem and some $b\in[0,\beta]^{E_{\geq
i}}$, we can find with polynomially many calls to the algorithm and polynomial
running time overhead a solution to $\mathrm{CLP}^{\mathrm{DW}}_{\geq
i}(T^{*},\alpha,\beta)$ or find a feasible solution $\pi,\mu$ to the dual of
$\mathrm{CLP}^{\mathrm{DW}}_{\geq i}(T^{*},1,1)$ with negative objective
(which proves that $\mathrm{CLP}^{\mathrm{DW}}_{\geq i}(T^{*},1,1)$ is
infeasible).

###### Proof.

We have $\mathcal{C}(v,1,1)\subseteq\mathcal{C}(v,\alpha,\beta)$, and we can
swap the requirement of $d\in\mathrm{X}_{\geq i+1}(L_{i}(g\cap
S_{i}),\alpha,\beta)$ for $d^{*}\in\mathrm{B}_{\geq i+1}(L_{i}(g\cap
S_{i}),\alpha,\beta)$, since these also form valid constraints for the dual.
Hence, the feasible region $P$ of the dual of
$\mathrm{CLP}^{\mathrm{DW}}_{\geq i}(T^{*},\alpha,\beta)$ is contained in the
feasible region $Q$ of the dual of $\mathrm{CLP}^{\mathrm{DW}}_{\geq
i+1}(T^{*},1,1)$. An algorithm for the separation problem can be seen as an
_approximate separation oracle_ in the sense that, given dual variables as
input, it either detects membership of the larger polyhedron $Q$ or outputs a
hyperplane separating the input from the smaller polyhedron $P$.

Notice that the all-zero-vector is feasible for the dual. Furthermore, if
$(\pi,\mu)$ is a feasible solution with objective $-1$, then
$(c\cdot\pi,c\cdot\mu)$ is also feasible for the dual and has an objective
value of $-c$ for any $c>0$, i.e., the dual is unbounded. It follows that
$\mathrm{CLP}_{\geq i+1}(L_{i}(g\cap S_{i}),\alpha,\beta)$ is feasible if and
only if its dual has no solution of value $-1$. Let

$P^{\prime}=\\{(\pi,\mu):(\pi,\mu)\in P,\ \sum_{e\in E_{\geq
i}}b(e)\mu_{e}-\sum_{v\in T^{*}}\pi_{v}=-1\\},$
$Q^{\prime}=\\{(\pi,\mu):(\pi,\mu)\in Q,\ \sum_{e\in E_{\geq
i}}b(e)\mu_{e}-\sum_{v\in T^{*}}\pi_{v}=-1\\}.$

We simulate the Ellipsoid method on $P^{\prime}$ with the given approximate
separation oracle (over $P^{\prime}$ and $Q^{\prime}$) in order to find a
feasible point in $Q^{\prime}$, if there exists one. Recall that in each
iteration the Ellipsoid method presents a point $(\pi,\mu)$ and it expects us
to either determine that $x\in P^{\prime}$ or a hyperplane separating $x$ from
$P^{\prime}$. In each iteration, we apply the approximate separation oracle
which either determines $(\pi,\mu)\in Q^{\prime}$ or finds a hyperplane
separating $(\pi,\mu)$ from $P^{\prime}$. In the latter case, we continue the
Ellipsoid method adhering to its requirements. In the former case we can stop
the algorithm, since we found the required solution. Note that we terminate
earlier than one would normally when running Ellipsoid on $P^{\prime}$, since
we cannot actually decide whether $(\pi,\mu)\in P^{\prime}$ or not.

As mentioned above, the existence of $(\pi,\mu)\in Q^{\prime}$ implies
infeasibility of $\mathrm{CLP}^{\mathrm{DW}}_{\geq i}(T^{*},1,1)$. If such a
point can not be found, it is enough to consider the primal variables that are
encountered as dual constraints when solving the dual. Since we only had
polynomially many calls to the approximate separation oracle, one can solve
the primal restricted to these variables. ∎

Assuming we can solve the separation problem efficiently, this implies Theorem
8. Indeed, if the algorithm from Lemma 10 is not successful, then we find a
feasible solution $\pi$, $\mu_{e}$ for the dual of
$\mathrm{CLP}^{\mathrm{DW}}_{\geq i}(T^{*},1,1)$ such that $\sum_{e\in E_{\geq
i}}b(e)\mu_{e}-\sum_{v\in T^{*}}\pi_{v}<0$. Notice that for any
$b^{\prime}\in\mathrm{B}_{\geq i}(T^{*},1,1)$ the dual has no negative
solutions, thus $\sum_{e\in E_{\geq i}}b^{\prime}(e)\mu_{e}-\sum_{v\in
T^{*}}\pi_{v}\geq 0$. Hence, this provides us with a hyperplane that separates
$b$ from $\mathrm{B}_{\geq i}(T^{*},1,1)$ as required in Theorem 8.

###  4.2 Separation via multilinear extension

Our goal is now to devise an algorithm that solves the separation problem
stated above. We will formulate a continuous relaxation of the separation
problem, solve and round it, but in order to do so we need to first introduce
the concept of _multilinear extension_. Let
$f:\\{0,1\\}^{n}\rightarrow\mathbb{R}_{\geq 0}$ be a submodular function. We
want to extend $f:\\{0,1\\}^{n}\rightarrow\mathbb{R}$ to the domain
$[0,1]^{n}$, since we will be working with continuous relaxations. There are
several natural extensions, one of which is known as the _multilinear
extension_. The multilinear extension $F:[0,1]^{n}\rightarrow\mathbb{R}$ is
defined by

$F(x)=\sum_{S\subseteq[n]}f(S)\prod_{i\in S}x_{i}\prod_{j\notin S}(1-x_{j})\
.$

It is equivalent to set $F(x)=\mathbb{E}[f(X)]$ where $X$ is a random set with
elements appearing independently with probabilities $x_{i}$. Notice that the
definition of $F$ involves summing over all subsets of $[n]$, but a good
approximation can be computed by sampling from the said distribution. Although
$F$ is not convex, there are strong results for approximately maximizing it
over polytopes, most notable the continuous Greedy algorithm [24]. We will
need a non-standard variant that is summarized in the lemma below.

######  Lemma 11.

Let $P\subseteq Q\subseteq[0,1]^{n}$ be downward-closed polytopes444A polyope
is downward-closed if for any $x$ in the polytope and any $y$ with $0\leq
y_{i}\leq x_{i}$ for each component $i$, $y$ is also in the polytope. and
suppose that we can approximately optimize over $Q$ in the following way:
given some $c\in\mathbb{R}^{n}$ we can find some $x\in Q$ such that
$c^{T}x\geq c^{T}y$ for all $y\in P$ or determine that $P$ is empty. Let $F$
be the multilinear extension of a monotone submodular function $f$ and let
$x^{*}=\mathrm{argmax}_{x\in P}F(x)$. Assume furthermore that $f(\\{i\\})\leq
F(x^{*})$ for any element $i\in[n]$. Then, there is a polynomial time Las
Vegas algorithm that finds some $x\in Q$ such that
$F(x)\geq(1-1/e-\varepsilon)F(x^{*})$.

The proof of the lemma is almost identical to the classical analysis of the
continuous Greedy algorithm [24], see Appendix A.

We will now reformulate the separation problem as maximizing a submodular
function over a polytope. Assume that $\pi_{v},\mu_{e}$ do not satisfy all
constraints (12) for the dual of $\mathrm{CLP}^{\mathrm{DW}}_{\geq
i+1}(T^{*},1,1)$, i.e., there exists some $u^{*}\in T^{*}$,
$g^{*}\in\mathcal{C}(u^{*},1,1)$, and $d^{*}\in\mathrm{B}_{\geq
i+1}(L_{i}(g\cap S_{i}),1,1)$ with

$\sum_{e\in E_{i}}g^{*}(e)\mu_{e}+\sum_{e\in E_{\geq
i+1}}d^{*}(e)\mu_{e}<\pi_{u^{*}}\ .$

We can assume that we know $u^{*}$ through guessing. Our goal is to
approximately find $g^{*}$ and $d^{*}$. Using the definition of a
configuration, the values $g^{*}$ and $d^{*}$ are feasible for the following
system and have a value of at least $1$.

$\displaystyle\max\ $ $\displaystyle f_{u^{*}}(g\cap\delta(u^{*}))$ (15)
$\displaystyle\sum_{e\in E_{i}}g(e)\mu_{e}+\sum_{e\in E_{\geq
i+1}}d(e)\mu_{e}$ $\displaystyle\leq\pi_{u^{*}}$ (16) $\displaystyle
g(\delta^{-}(v))$ $\displaystyle=g(\delta^{+}(v))$ $\displaystyle\forall v\in
V_{i}\setminus(S_{i}\cup T_{i})$ (17) $\displaystyle d$
$\displaystyle\in\mathrm{B}_{\geq i+1}(L_{i}(g\cap S_{i}),1,1)$ (18)
$\displaystyle g(e)$ $\displaystyle\in\\{0,1\\}$ $\displaystyle\forall e\in
E_{i}$ (19)

We need to find a solution of value at least $1/\alpha$ and we can make use of
congestion $\beta$. For technical reasons we will assume without loss of
generality that $f_{u^{*}}$ is upper bounded by $1$, which is possible by
replacing $f_{u^{*}}$ with $f_{u^{*}}^{\prime}(S)=\min\\{1,f_{u^{*}}(S)\\}$,
since this preserves monotonicity, submodularity and the existence of a
solution of value $1$. We further assume that each individual element has a
small value, more precisely, $f_{u^{*}}(\\{e\\})\leq 1/20$ for each
$e\in\delta(u^{*})$. The careful reader will have noticed that the reduction
in Section 3 anyway guarantees this property. However, it is also easy to
establish this assumption without adding more technical restrictions to the
definition of the augmentation problem555 If $g^{*}(e)=1$ for some
$e\in\delta(u^{*})$ with $f_{u^{*}}(\\{e\\})>1/40$ we guess $e$ as well as the
source $s\in S_{i}$, from which the flow on $e$ comes (in an arbitrary path
decomposition of $g^{*}$. We compute a shortest path from $s$ to $e$ with
weights $\mu_{e}$ and we compute some $d\in B_{\geq
i+1}(L_{i}(\\{s\\}),\alpha,\beta)$ minimizing $\sum_{e\in E_{\geq
i+1}}d(e)\mu_{e}$ using Ellipsoid method. This yields a solution of the
separation problem for $\alpha\geq 1/40$. In the other case we can remove all
$e\in\delta(u^{*})$ with $f_{u^{*}}(\\{e\\})>1/40$, since they are not used. .

By Lemma 4 we can replace Constraint (18) with the following equivalent
constraints and additional variables. The main idea is that we introduce a
binary variable $y_{s}\in\\{0,1\\}$ for each $s\in S_{i}$, which describes
whether $s\in g\cap S_{i}$.

$\displaystyle d_{s}$ $\displaystyle\in y_{s}\cdot\mathrm{B}_{\geq
i+1}(L_{i}(\\{s\\}),1,1)$ $\displaystyle\forall s\in S_{i}$ $\displaystyle
y_{s}$ $\displaystyle=g(\delta^{+}(s))$ $\displaystyle\forall s\in S_{i}$
$\displaystyle y_{s}$ $\displaystyle\in\\{0,1\\}$ $\displaystyle\forall s\in
S_{i}$ $\displaystyle d(e)$ $\displaystyle=\sum_{s\in S_{i}}d_{s}(e)$
$\displaystyle\forall e\in E_{\geq i+1}$ $\displaystyle d(e)$
$\displaystyle\in[0,1]$ $\displaystyle\forall e\in E_{\geq i+1}$
$\displaystyle d_{s}(e)$ $\displaystyle\in[0,1]$ $\displaystyle\forall s\in
S_{i},e\in E_{\geq i+1}$

In order to find an approximate solution we consider the continuous relaxation
using the multi-linear extension as described below.

Relaxed separation problem $\mathrm{SEP}(u^{*},\alpha,\beta)$ with multilinear
extension $\displaystyle\max\ $ $\displaystyle F_{u^{*}}(\
(g(e))_{e\in\delta(u^{*})}\ )$ (20) $\displaystyle\sum_{e\in
E_{i}}g(e)\mu_{e}+\sum_{e\in E_{\geq i+1}}\sum_{s\in S_{i}}d_{s}(e)\mu_{e}$
$\displaystyle\leq\pi_{u^{*}}$ (21) $\displaystyle g(\delta^{-}(v))$
$\displaystyle=g(\delta^{+}(v))$ $\displaystyle\forall v\in
V_{i}\setminus(S_{i}\cup T_{i})$ (22) $\displaystyle d_{s}$ $\displaystyle\in
y_{s}\cdot\mathrm{B}_{\geq i+1}(L_{i}(\\{s\\}),\alpha,\beta)$
$\displaystyle\forall s\in S_{i}$ (23) $\displaystyle y_{s}$
$\displaystyle=g(\delta^{+}(s))$ $\displaystyle\forall s\in S_{i}$ (24)
$\displaystyle\sum_{s\in S_{i}}d_{s}(e)$ $\displaystyle\leq 1$
$\displaystyle\forall e\in E_{\geq i+1}$ (25) $\displaystyle g(e)$
$\displaystyle\in[0,1]$ $\displaystyle\forall e\in E_{i}$ (26) $\displaystyle
y_{s}$ $\displaystyle\in[0,1]$ $\displaystyle\forall s\in S_{i}$ (27)
$\displaystyle d_{s}(e)$ $\displaystyle\in[0,1]$ $\displaystyle\forall s\in
S_{i},e\in E_{\geq i+1}$ (28)

Here $F_{u^{*}}$ is the multilinear extension of $f_{u^{*}}$. If $F_{u^{*}}$
is replaced by a linear objective, then we can solve $\mathrm{SEP}$
approximately in the following sense.

######  Lemma 12.

Consider the system $\mathrm{LINSEP}(u^{*},\alpha,\beta,c)$, where (20) in
$\mathrm{SEP}(u^{*},\alpha,\beta)$ is replaced by a linear objective
$\max\sum_{e\in\delta(u^{*})}c_{e}g(e)$ for $c\in\mathbb{R}^{\delta(u^{*})}$.

Let $\alpha,\beta\in\mathbb{N}$. We can find a solution for
$\mathrm{LINSEP}(u^{*},\alpha,\beta,c)$ with value at least the optimum of
$\mathrm{LINSEP}(u^{*},1,1,c)$ using polynomial running time overhead and a
polynomial number of queries that for a given $s\in S_{i}$ and
$d_{s}\in[0,\beta]^{E_{\geq i+1}}$ determine either $d_{s}\in\mathrm{B}_{\geq
i+1}(L_{i}(\\{s\\}),\alpha,\beta)$ or return a hyperplane separating $d_{s}$
from $\mathrm{B}_{\geq i+1}(L_{i}(\\{s\\}),1,1)$.

###### Proof.

We will run the Ellipsoid method to optimize over $\mathrm{LINSEP}$: similar
to the proof of Lemma 10 we simulate Ellipsoid on
$\mathrm{LINSEP}(u^{*},1,1,c)$ and terminate once the given solution is
feasible for $\mathrm{LINSEP}(u^{*},\alpha,\beta,c)$. Optimization is reduced
to feasibility testing by performing a binary search over the optimum.

It remains to separate (approximately) over Constraint (23). The query access
from the premise can be lifted to this task: Fix some $s\in S_{i}$ and
$d_{s},y_{s}$. If $d_{s},y_{s}$ are all zero, then $d_{s}\in
y_{s}\cdot\mathrm{B}_{\geq i+1}(L_{i}(\\{s\\},\alpha,\beta)$. If $y_{s}=0$ and
$d_{s}(e)>0$ for some $e$, we have that

$d_{s}(e)>y_{s}\text{ and }d^{\prime}_{s}(e)\leq y^{\prime}_{s}\text{ for all
}d^{\prime}_{s}\in y^{\prime}_{s}\cdot\mathrm{B}_{\geq
i+1}(L_{i}(\\{s\\},1,1)\ ,$

which serves as a separating hyperplane. Assume now that $y_{s}>0$. Apply the
query from the premise on $d_{s}/y_{s}$. Either
$d_{s}/y_{s}\in\mathrm{B}_{\geq i+1}(L_{i}(\\{s\\}),\alpha,\beta)$, which
implies that $d_{s}\in y_{s}\cdot\mathrm{B}_{\geq
i+1}(L_{i}(\\{s\\}),\alpha,\beta)$ or we find a separating hyperplane
$w\in\mathbb{R}^{E_{\geq i+1}}$, $W\in\mathbb{R}$ with $w^{T}(d_{s}/y_{s})<W$
and $w^{T}d^{\prime}\geq W$ for all $d^{\prime}\in\mathrm{B}_{\geq
i+1}(L_{i}(\\{s\\}),1,1)$. It follows that

$w^{T}d_{s}-Wy_{s}<0\text{ and }w^{T}d^{\prime}_{s}-Wy^{\prime}_{s}\geq
0\text{ for all }d^{\prime}_{s}\in y^{\prime}_{s}\cdot\mathrm{B}_{\geq
i+1}(L_{i}(\\{s\\}),\alpha,\beta)\ ,$

which again serves as a separating hyperplane. ∎

In order to employ the continuous Greedy algorithm (Lemma 11), the feasible
region needs to be downward closed, which is not necessarily true here. If,
however, we project to the variables $g(e)$, $e\in\delta(u^{*})$, then the
feasible region becomes downward closed. This is easy to see by considering
the path decomposition of the flow $g$, and the fact that the $\mu_{e}$
variables are non-negative. Maximizing $F_{u^{*}}$ over the projection is
equivalent to maximizing it over the original feasible set. Hence, we can use
the lemma to find such a solution with value at least $1-1/e-\varepsilon$
(assuming that the optimum is $1$).

As a final step, we need to round this continuous solution to an integral one.

######  Lemma 13.

Let $\alpha\geq 40$ and $\beta\geq 10\log(n)$. Given a solution of value
$1-1/e-\varepsilon$ for $\mathrm{SEP}(u^{*},\alpha,\beta)$ with
$\varepsilon>0$ being a sufficiently small constant, there is a Las Vegas
algorithm to find a solution for the separation problem in polynomial time.

###### Proof.

Let $g,y_{s},d_{s}$ be the continuous solution of
$\mathrm{SEP}(u^{*},\alpha,\beta)$. We compute a path decomposition of $g$
into paths $\mathcal{P}$ from $S_{i}$ to $u^{*}$ and weights
$\lambda_{P},P\in\mathcal{P}$, that satisfy
$g=\sum_{P\in\mathcal{P}}\lambda_{P}\cdot\chi(P)$, where
$\chi(P)\in\\{0,1\\}^{E_{i}}$ is the characteristic vector of path $P$. We
partition $\mathcal{P}$ into sets $\mathcal{P}(e),e\in\delta(u^{*})$, which
are the paths with last edge being $e$.

Independently for each $e\in\delta(u^{*})$ we sample at most one path from
$\mathcal{P}(e)$ such that the probability of sampling $P$ is exactly
$\lambda_{P}$. Let $\mathcal{P}^{\prime}$ be the resulting paths. For
simplicity of notation, we write

$f_{u^{*}}(\mathcal{Q})=f_{u^{*}}(\bigcup_{P\in\mathcal{Q}}P\cap\delta(u^{*}))\
,$

for the submodular function value of some set of paths $\mathcal{Q}$.
Furthermore, for each $P\in\mathcal{P}^{\prime}$ define

$\Phi(P)=\sum_{e\in P}\mu_{e}+\sum_{e\in E_{\geq
i+1}}d_{s}(e)/y_{s}\cdot\mu_{e}\ ,$

where $s$ is the source that $P$ originates from. Then we have that

$\mathbb{E}[\sum_{P\in\mathcal{P}^{\prime}}\Phi(P)]=\sum_{e\in
E_{i}}g(e)\mu_{e}+\sum_{e\in E_{\geq i+1}}\sum_{s\in S_{i}}y_{s}\cdot
d_{s}(e)/y_{s}\cdot\mu_{e}\leq\pi_{u^{*}}\ .$

Thus, by Markov’s inequality we get

$\mathbb{P}[\sum_{P\in\mathcal{P}^{\prime}}\Phi(P)>10\pi_{u^{*}}]\leq 1/10\ .$

Further, let $p=\mathbb{P}[f_{u^{*}}(\mathcal{P}^{\prime})<1/2]$. Since $f$ is
bounded by $1$ due to an earlier assumption, we have

$1-1/e-\varepsilon\leq
F_{u^{*}}((g(e))_{e\in\delta(u^{*})})=\mathbb{E}[f_{u^{*}}(\mathcal{P}^{\prime})]\leq
p/2+(1-p)\ .$

This implies

$p\leq 2/e+2\varepsilon\leq 0.75\ ,$

assuming $\varepsilon$ (from the continuous Greedy algorithm) is choosen
sufficiently small. Define
$k=\lceil\sum_{P\in\mathcal{P}^{\prime}}\Phi(P)/\pi_{u^{*}}\rceil$. With
probability at least $0.15$ we have that

$k\leq 10\quad\text{ and }\quad f_{u^{*}}(\mathcal{P}^{\prime})\geq 1/2\ .$
(29)

We will show that if (29) holds, then we can recover a set of paths
$\mathcal{P}^{\prime\prime}\subseteq\mathcal{P}^{\prime}$ with
$\sum_{P\in\mathcal{P}^{\prime\prime}}\Phi(P)<\pi_{u^{*}}$ and
$f_{u^{*}}(\mathcal{P}^{\prime\prime})\geq 1/\alpha$.

Partition $\mathcal{P}^{\prime}$ into $k+1$ many sets
$\mathcal{P}^{\prime}_{0},\dotsc,\mathcal{P}^{\prime}_{k}$ where
$|\mathcal{P}^{\prime}_{0}|\leq k$ and $\Phi(P^{\prime}_{i})<1$ for all
$i=1,2,\dotsc,k$: for this, we greedily add paths to
$\mathcal{P}^{\prime}_{1}$ until $\Phi(P^{\prime}_{1})<1$ would be violated
with the next path. This path is added to $P^{\prime}_{0}$. Then we repeat the
same with $\mathcal{P}^{\prime}_{2},\mathcal{P}^{\prime}_{3},\dotsc$ until all
paths are placed in one set. Since each iteration packs $\Phi(P)$ values of
sum at least $1$, the process must terminate after at most $k$ iterations.

Since $f$ is monotone submodular and in particular subadditive and since
$f_{u^{*}}(\\{e\\})\leq 1/40$ by an earlier assumption, we have that

$f_{u^{*}}(\mathcal{P}^{\prime}_{1})+\cdots+f_{u^{*}}(\mathcal{P}^{\prime}_{k})\geq
f_{u^{*}}(\mathcal{P}^{\prime})-f_{u^{*}}(\mathcal{P}^{\prime}_{0})\geq
1/2-k\cdot 1/40\geq 1/4\ .$

Thus, $f_{u^{*}}(\mathcal{P}^{\prime}_{i})\geq 1/(4k)\geq 1/40=1/\alpha$ for
some $i\in\\{1,2,\dotsc,k\\}$. Let $i$ be the index above and define
$g^{\prime}=\sum_{P\in\mathcal{P}^{\prime}_{i}}\chi(P)$, where $\chi(P)$ is
the characteristic vector of path $P$. In other words, $g^{\prime}$ is the
flow corresponding to $\mathcal{P}^{\prime}_{i}$. We further define
$d^{\prime}=\sum_{s\in L_{i}(g^{\prime}\cap S_{i})}d_{s}/y_{s}$.

By the previous arguments we have that with probability at least $0.15$, the
function value $f_{u^{*}}(g^{\prime}\cap S_{i})\geq 1/40$. It remains to show
that with a high probability $g^{\prime}$ has congestion at most $\beta$ and
that $d^{\prime}\in\mathrm{B}_{\geq i+1}(L_{i}(g^{\prime}\cap
S_{i}),\alpha,\beta)$. For the former, we analyze the flow value on each edge
$e\in E_{i}$ separately. Note that

$\mathbb{E}[g^{\prime}(e)]\leq\mathbb{E}[\ |\\{P\in\mathcal{P}^{\prime}:e\in
P\\}|\ ]=g(e)\leq 1\ .$

Further, $X=|\\{P\in\mathcal{P}^{\prime}:e\in P\\}|$ can be seen as a sum of
independent $0/1$ random variables, one for each set
$\mathcal{P}(e^{\prime})$, $e^{\prime}\in\delta(u^{*})$. Thus, we can apply a
Chernoff bound on $X$, which implies that

$\mathbb{P}[g^{\prime}(e)>10\log(n)]\leq\mathbb{P}[X>10\log(n)]\leq 1/n^{3}\
.$

Now consider $d^{\prime}$. Since $d_{s}/y_{s}\in\mathrm{CLP}_{\geq
i+1}(L_{i}(\\{s\\}),\alpha,\beta)$ for all $s\in g^{\prime}\cap S_{i}$ and
$d^{\prime}$ is their sum, due to Lemma 4 it suffices to show that
$d^{\prime}\in[0,\beta]^{E_{\geq i+1}}$. This we can argue in a similar way
with a Chernoff bound: let $e\in E_{\geq i+1}$. Then

$\mathbb{E}[d^{\prime}(e)]=\sum_{s\in S_{i}}\mathbb{P}[s\in g^{\prime}\cap
S_{i}]\cdot d_{s}(e)/y_{s}\leq\sum_{s\in S_{i}}d_{s}(e)\leq 1\ .$

Each term $d_{s}(e)/y_{s}$ can be seen as an independent random variable,
which is bounded by $1$ since $d_{s}\in y_{s}\cdot\mathrm{CLP}_{\geq
i+1}(\\{s\\},1,1)$. Thus

$\mathbb{P}[d^{\prime}(e)>10\log(n)]\leq 1/n^{3}\ .$

To summarize, we have with probability $0.15-|E_{\geq i}|/n^{3}$ that the
solution we output is a correct solution to the separation problem. This can
be boosted to high probability by repeating the random experiment. ∎

##  5 Rounding the linear programming relaxation

In this section we will perform randomized rounding on a solution to the
multi-level configuration LP, $\mathrm{CLP}_{\geq 1}(T^{*},\alpha,\beta)$, in
order to arrive at a solution for the augmentation problem. For convenience,
we restate here the LP. We recall that $\mathrm{B}_{\geq
i}(T^{*},\alpha,\beta)$ is the set of feasible values $b\in[0,\beta]^{E_{\geq
i}}$ for $\mathrm{CLP}_{\geq i}(T^{*},\alpha,\beta)$.

Multi-level configuration LP, $\mathrm{CLP}_{\geq i}(T^{*},\alpha,\beta)$
$\displaystyle\sum_{g\in\mathcal{C}(v,\alpha,\beta)}x_{v,g}$
$\displaystyle\geq 1$ $\displaystyle\forall v\in T^{*}$ (30)
$\displaystyle\sum_{v\in
T^{*}}\sum_{g\in\mathcal{C}(v,\alpha,\beta)}b_{v,g}(e)$ $\displaystyle\leq
b(e)$ $\displaystyle\forall e\in E_{\geq i}$ (31) $\displaystyle g(e)\cdot
x_{v,g}$ $\displaystyle=b_{v,g}(e)$ $\displaystyle\forall v\in
T^{*},g\in\mathcal{C}(v,\alpha,\beta),$ (32) $\displaystyle e\in E_{i},$
$\displaystyle(b_{v,g}(e))_{e\in E_{\geq i+1}}$ $\displaystyle\in
x_{v,g}\cdot\mathrm{B}_{\geq i+1}(L_{i}(g\cap S_{i}),\alpha,\beta)$
$\displaystyle\forall v\in T^{*},g\in\mathcal{C}(v,\alpha,\beta)$ (33)
$\displaystyle x_{v,g}$ $\displaystyle\geq 0$ $\displaystyle\forall v\in
T^{*},g\in\mathcal{C}(v,\alpha,\beta)$ (34) $\displaystyle b_{v,g}(e)$
$\displaystyle\geq 0$ $\displaystyle\forall v\in
T^{*},g\in\mathcal{C}(v,\alpha,\beta),$ (35) $\displaystyle e\in E_{\geq i}$

The rounding procedure will be defined recursively and its properties are
summarized in the following lemma.

######  Lemma 14.

Assume we are given a set of sinks $T^{*}\subseteq T_{i}$, and
$b=(\gamma,\dotsc,\gamma)\in\mathrm{B}_{\geq i}(T^{*},\alpha,\beta)$ with
$\gamma\geq 6\beta\cdot\log^{3}n$. Then, we can in polynomial time find an
integral flow $\bar{g}$ in $G_{i}$ such that with high probability

  1. 1.

flow $\bar{g}$ $\alpha$-covers every sink in $T^{*}$ with congestion
$O(\gamma)$, and

  2. 2.

$(\bar{\gamma},\bar{\gamma},\dotsc,\bar{\gamma})\in\mathrm{B}_{\geq
i+1}(L_{i}(\bar{g}\cap S_{i})),\alpha,\beta)$ for
$\bar{\gamma}=\gamma\cdot\left(1+\frac{1}{\log n}\right)$.

###### Proof.

We proceed as follows. We let $x_{v,g}$ and $b_{v,g}(e)$ be the variables that
attest $(\gamma,\gamma,\dotsc,\gamma)\in\mathrm{B}_{\geq
i}(T^{*},\alpha,\beta)$. We assume without loss of generality that (30) holds
with equality. Each sink $v\in T^{*}$ picks independently a flow
(configuration) $g_{v}$ with probability $x_{v,g_{v}}$, which by the previous
assumption is a valid probability distribution. By Constraints (33), we have
that $b_{v,g_{v}}/x_{v,g_{v}}\in\mathrm{B}_{\geq i+1}(L_{i}(g_{v}\cap
S_{i}),\alpha,\beta)$ attested by some variables
$x^{(v)}_{u,g_{u}},b^{(v)}_{u,g_{u}}$ (corresponding to the conditions of
$\mathrm{CLP}_{\geq i+1}$). We then define

$\bar{g}=\sum_{v\in T^{*}}g_{v}\ ,\quad\bar{x}_{u,g_{u}}=\sum_{v\in
T^{*}}x^{(v)}_{u,g_{u}}\ ,\quad\text{ and }\quad\bar{b}_{u,g_{u}}=\sum_{v\in
T^{*}}b^{(v)}_{u,g_{u}}\ .$

We will show that with high probability $\bar{g}$ satisfies the properties of
the lemma and $\bar{x}_{u,g_{u}},\bar{b}_{u,g_{u}}$ attest that
$(\bar{\gamma},\dotsc,\bar{\gamma})\in\mathrm{B}_{\geq
i+1}(\bar{T}^{*},\alpha,\beta)$, where $\bar{T}^{*}=L_{i}(\bar{g}\cap S_{i})$.

For the first property, we need to analyze the congestion of $\bar{g}$. By
Constraints (32) and (31) we obtain that the expected congestion on any edge
$e$ is equal to

$\mathbb{E}[\bar{g}(e)]=\mathbb{E}[\sum_{v\in T^{*}}g_{v}(e)]=\sum_{v\in
T^{*}}\sum_{g\in\mathcal{C}(v,\alpha,\beta)}g(e)\cdot x_{v,g}\leq\sum_{v\in
T^{*}}\sum_{g\in\mathcal{C}(v,\alpha,\beta)}b_{v,g}\leq\gamma\ .$

Further, the congestion is the sum of independent random variables, one for
each $v\in T^{*}$, that are each bounded by $\beta$. Therefore, using a
Chernoff bound, the probability that the congestion is more than $2\gamma$ is
at most

$\exp\left(-\frac{\gamma}{3\beta}\right)\leq\exp\left(-2\log^{3}n)\right)\ .$

Hence, with high probability, the congestion in $E_{i}$ at most $2\gamma$. For
the second property, we verify Constraints (30), (32), (31), and (33) one by
one, the last two being trivial to verify.

#### Constraint (30).

Let $u\in\bar{T}^{*}$ be one of our new sources. Let
$g_{w}\in\mathcal{C}(w,\alpha,\beta)$ be a configuration that was selected for
some $w\in T^{*}$ such that $u\in V(g_{w})$ (it must exists by definition of
$\bar{T}^{*}$). Then, by Constraint (33), we have that that
$b_{w,g_{w}}/x_{w,g_{w}}\in\mathrm{B}_{\geq i+1}(L_{i}(g_{w}\cap
S_{i}),\alpha,\beta)$ attested by $x^{(w)}_{v,g}$, $b^{(w)}_{v,g}$. Due to
Constraint (30) in $\mathrm{CLP}_{\geq i+1}$ we have

$\sum_{g\in\mathcal{C}(u,\alpha,\beta)}\bar{x}_{u,g}\geq\sum_{g\in\mathcal{C}(u,\alpha,\beta)}x^{(w)}_{u,g}\geq
1\ .$

#### Constraints (32) and (33).

Notice that $\bar{x}_{u,g}$, $\bar{b}_{u,g}$ are the sum of variables that
each satisfy (32) and (33). It is easy to see that these constraints remain
satisfied under taking the sum of feasible solutions (since those constraints
define polyhedral cones).

#### Constraint (31).

Notice that

$\displaystyle\mathbb{E}[\sum_{u\in\bar{T}^{*}}\sum_{g\in\mathcal{C}(u,\alpha,\beta)}\bar{b}_{u,g}(e)]$
$\displaystyle\leq\sum_{v\in
T^{*}}\sum_{\begin{subarray}{c}g\in\mathcal{C}(v,\alpha,\beta)\\\
x_{v,g}>0\end{subarray}}x_{v,g}\cdot\frac{b_{v,g}(e)}{x_{v,g}}$
$\displaystyle\leq\sum_{v\in
T^{*}}\sum_{g\in\mathcal{C}(v,\alpha,\beta)}b_{v,g}(e)$
$\displaystyle\leq\gamma\ ,$

where the first inequality is obtained by definition of our sampling procedure
and the last inequality by Constraint (31) in $\mathrm{CLP}_{\geq i}$. Second,
we notice that the random variable
$\sum_{u\in\bar{T}^{*}}\sum_{g\in\mathcal{C}(u,\alpha,\beta)}\bar{b}_{u,g}(e)$
is a sum of independent random variables, one for each $u\in T^{*}$ that take
a value $b_{u,g}(e)/x_{u,g}$ for some configuration $g$. By definition of
$\mathrm{B}_{\geq i+1}$, we also have the constraint that
$b_{u,g}(e)/x_{u,g}\leq\beta$ for all $u$ and $g$. Hence the random variable
$\sum_{u\in\bar{T}^{*}}\sum_{g\in\mathcal{C}(u,\alpha,\beta)}\bar{b}_{u,g}(e)$
is a sum of independent random variables, all bounded in absolute value by
$\beta$, and of total expectation at most $\gamma$. By a standard Chernoff
bound, we have

$\mathbb{P}\left[\sum_{u\in\bar{T}^{*}}\sum_{g\in\mathcal{C}(u,\alpha,\beta)}\bar{b}_{u,g}(e)\geq\gamma\cdot\left(1+1/\log
n\right)\right]\leq\exp\left(-\frac{\gamma}{2\beta\log^{2}n}\right)\leq\exp(-3\log
n)\ .$

Hence, with high probability, Constraint (31) is satisfied as well. ∎

Now we can solve the augmentation problem by applying Lemma 14 iteratively. If
we have an LP solution with coverage $\alpha$ and congestion $\beta$ for an
$h$-level instance, this yields an $(\alpha,O(\beta\log^{3}(n)\cdot(1+1/\log
n)^{h})$-approximate solution. For any $h=O(\log n)$, this is a
$(\alpha,O(\beta\log^{3}n))$-approximate solution. Hence, Theorem 8 and Lemma
14 imply Theorem 3.

## References

  * [1] Noga Alon and Joel H Spencer.  The probabilistic method.  John Wiley & Sons, 2016.
  * [2] Chidambaram Annamalai, Christos Kalaitzis, and Ola Svensson.  Combinatorial algorithm for restricted max-min fair allocation.  ACM Transactions on Algorithms, 13(3):1–28, 2017.
  * [3] Arash Asadpour, Uriel Feige, and Amin Saberi.  Santa claus meets hypergraph matchings.  ACM Transactions on Algorithms, 8(3):24:1–24:9, 2012.
  * [4] Étienne Bamas, Paritosh Garg, and Lars Rohwedder.  The submodular santa claus problem in the restricted assignment case.  In Proceedings of ICALP, pages 22:1–22:18, 2021.
  * [5] Étienne Bamas, Alexander Lindermayr, Nicole Megow, Lars Rohwedder, and Jens Schlöter.  Santa claus meets makespan and matroids: Algorithms and reductions.  In Proceedings of SODA, pages 2829–2860, 2024.
  * [6] Étienne Bamas and Lars Rohwedder.  Better trees for santa claus.  In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 1862–1875, 2023.
  * [7] Nikhil Bansal and Maxim Sviridenko.  The santa claus problem.  In Proceedings of STOC, pages 31–40, 2006.
  * [8] Siddharth Barman, Umang Bhaskar, Anand Krishna, and Ranjani G. Sundaram.  Tight Approximation Algorithms for p-Mean Welfare Under Subadditive Valuations.  In Proceedings of ESA, pages 11:1–11:17, 2020.
  * [9] Mohammad Hossein Bateni, Moses Charikar, and Venkatesan Guruswami.  Maxmin allocation via degree lower-bounded arborescences.  In Proceedings of STOC, pages 543–552, 2009.
  * [10] Gruia Calinescu, Chandra Chekuri, Martin Pal, and Jan Vondrák.  Maximizing a monotone submodular function subject to a matroid constraint.  SIAM Journal on Computing, 40(6):1740–1766, 2011.
  * [11] Deeparnab Chakrabarty, Julia Chuzhoy, and Sanjeev Khanna.  On allocating goods to maximize fairness.  In Proceedings of FOCS, pages 107–116, 2009.
  * [12] George B Dantzig and Philip Wolfe.  Decomposition principle for linear programs.  Operations research, 8(1):101–111, 1960.
  * [13] Sami Davies, Thomas Rothvoss, and Yihao Zhang.  A tale of santa claus, hypergraphs and matroids.  In Proceedings of SODA, pages 2748–2757, 2020.
  * [14] Leah Epstein and Jiří Sgall.  Approximation schemes for scheduling on uniformly related and identical parallel machines.  In Proceedings of ESA, pages 151–162, 1999.
  * [15] Uriel Feige.  On allocations that maximize fairness.  In Proceedings of SODA, pages 287–293, 2008.
  * [16] Uriel Feige.  On maximizing welfare when utility functions are subadditive.  SIAM Journal on Computing, 39(1):122–142, 2009.
  * [17] Michel X Goemans, Nicholas JA Harvey, Satoru Iwata, and Vahab Mirrokni.  Approximating submodular functions everywhere.  In Proceedings of SODA, pages 535–544, 2009.
  * [18] Sungjin Im, Benjamin Moseley, Hung Q. Ngo, Kirk Pruhs, and Alireza Samadian.  Optimizing polymatroid functions.  CoRR, abs/2211.08381, 2022.
  * [19] Andreas Krause, Ram Rajagopal, Anupam Gupta, and Carlos Guestrin.  Simultaneous placement and scheduling of sensors.  In Proceedings of IPSN, pages 181–192, 2009.
  * [20] Jan Karel Lenstra, David B. Shmoys, and Éva Tardos.  Approximation algorithms for scheduling unrelated parallel machines.  Mathematical Programming, 46:259–271, 1990.
  * [21] Wenzheng Li and Jan Vondrák.  A constant-factor approximation algorithm for nash social welfare with submodular valuations.  In Proceedings of FOCS, pages 25–36, 2022.
  * [22] Lukáš Poláček and Ola Svensson.  Quasi-polynomial local search for restricted max-min fair allocation.  ACM Transactions on Algorithms, 12(2):1–13, 2015.
  * [23] Zoya Svitkina and Lisa Fleischer.  Submodular approximation: Sampling-based algorithms and lower bounds.  SIAM Journal on Computing, 40(6):1715–1737, 2011.
  * [24] Jan Vondrák.  Optimal approximation for the submodular welfare problem in the value oracle model.  In Proceedings of STOC, pages 67–74, 2008.
  * [25] Gerhard J Woeginger.  A polynomial-time approximation scheme for maximizing the minimum machine completion time.  Operations Research Letters, 20(4):149–154, 1997.

##  Appendix A Continuous greedy with approximate separation

In this section, we prove Lemma 11. Let $P\subseteq
Q\subseteq\mathbb{[}0,1]^{n}$ be two polyhedra which are downward-closed.

Let $F$ be the multilinear relaxation of a monotone submodular function $f$.
We also assume that for any element $i$ in the ground set, we have that
$f(\\{i\\})\leq F(x^{*})$, where $x^{*}$ is the point in $P$ maximizing
$F(x^{*})$.

We show that we can obtain with high probability, in polynomial time for any
fixed $\varepsilon>0$, a point $y\in Q$ such that
$F(y)\geq(1-1/e-\varepsilon)\cdot F(x^{*})$.

The proof is an easy modification of [10], which we repeat here for
completeness. The algorithm is as follows.

  1. 1.

Let $\delta=1/(10n^{2})$, and let $t=0$, $y(0)=0$.

  2. 2.

Let $R(t)$ contain each $j\in[n]$ independently with probability $y_{j}(t)$.
For all $j\in[n]$, we let $w_{j}(t)$ be an estimate of

$\mathbb{E}[f(j\mid R(t))]$

by taking the average over $\frac{10}{\delta^{2}}(1+\ln n)$ independent
samples of $R(t)$. We denote by $\textbf{E}_{t}$ the vector whose $j$-th
coordinate is equal to $\mathbb{E}[f(j\mid R(t))]$. We also aggregate the
$w_{j}(t)$ into a single vector $w(t)$.

  3. 3.

Find $y\in Q$ such that $w(t)^{T}y\geq w(t)^{T}x$ for all $x\in P$. We can
find such a point by the assumption in Lemma 11. Set

$y(t+\delta)=y(t)+\delta\cdot y\ .$

  4. 4.

If $t<1$, return to step 2, otherwise output $y(1)$.

Note that the output $y(1)$ is a convex combination of points in $Q$ (recall
that $y(0)=0\in Q$ since $Q$ is downward-closed). Hence, we have $y(1)\in Q$.

We use essentially the same arguments as in [10]. We start by the first key
lemma.

######  Lemma 15.

Let $y\in[0,1]^{n}$ and let $R$ be a random set containing each $j$
independently with probability $y_{j}$. Then

$F(x^{*})\leq F(y)+\max_{y^{\prime}\in
P}\sum_{j\in[n]}y^{\prime}_{j}\cdot\mathbb{E}[f(j\mid R(t))]\ .$

###### Proof.

We can write by submodularity, for any set $R$, and any set $O$,

$f(O)\leq f(R)+\sum_{j\in O}f(j\mid R)\ .$

By taking the expectation over the set $R$ containing each $j$ independently
with probability $y_{j}$ and over the set $O$ containing each element $j$
independently with probability $x_{j}^{*}$, we obtain

$\displaystyle F(x^{*})\leq
F(y)+\sum_{j\in[n]}x_{j}^{*}\cdot\mathbb{E}[f(j\mid R)]\leq
F(y)+\max_{y^{\prime}\in P}\sum_{j\in[n]}y^{\prime}_{j}\cdot\mathbb{E}[f(j\mid
R)]\ ,$

where the inequality holds since $x^{*}\in P$. This concludes the proof. ∎

The second lemma essentially states that estimating the expectations with
sampling does not loose much. Before proving this result, we state here an
inequality that will be useful in the proof.

######  Theorem 16 (Theorem A.1.16 in [1]).

Let $X_{i}$, $1\leq i\leq k$ be independent random variable with
$\mathbb{E}[X_{i}]=0$ and $|X_{i}|\leq 1$ for all $i$, then

$\mathbb{P}[|\sum_{i=1}^{k}X_{i}|>a]\leq 2\exp(-a^{2}/(2k))\ .$

######  Lemma 17.

With probability at least $1-1/\mathrm{poly}(n)$, for every $t$ the algorithm
finds some $y\in Q$ such that

$(\textbf{E}_{t})^{T}y\geq(1-2n\delta)\cdot F(x^{*})-F(y(t))\ .$

###### Proof.

Recall that $y$ is selected to (approximately) maximize $w(t)^{T}y$ among
feasible points in $Q$, where $w_{j}(t)$ is our estimate of
$(\textbf{E}_{t})_{j}=\mathbb{E}[f(j\mid R(t))]$. We say that an estimate
$w_{j}(t)$ is bad if $|w_{j}(t)-\mathbb{E}[f(j\mid R(t))]|>\delta\cdot
F(x^{*})$. As in [10], one can argue that with high probability there is no
bad estimate during the whole run of the algorithm.

Let $R_{1},R_{2},\ldots,R_{k}$ be the $k=\frac{10}{\delta^{2}}(1+\ln n)$
samples used for the estimates $w_{j}(t)$, and let us denote by $X_{i}$ the
random variable $X_{i}=(f(j\mid R_{i})-\mathbb{E}[f(j\mid R(t))])/F(x^{*})$.
First, by submodularity and our assumption in the beginning of this section,
we always have

$\displaystyle|X_{i}|\leq\frac{\max(f(j\mid R_{i}),\mathbb{E}[f(j\mid
R(t))])}{F(x^{*})}\leq\frac{f(j)}{F(x^{*})}\leq 1\ .$

Next, note that the estimate is bad exactly if

$\left|\sum_{i=1}^{k}X_{i}\right|>\frac{10}{\delta^{2}}(1+\ln n)\cdot\delta\
.$

By applying Theorem 16, the probability of this happening is at most

$2\exp\left(-\frac{5}{\delta^{2}}(1+\ln
n)\cdot\delta\right)=2\exp\left(-5\ln(n)\right)\leq n^{-4}\ .$

By union bound over all $10n^{2}$ timesteps and all coordinates $j\in[n]$,
with high probability all estimates are good.

Now, let $y^{\prime}\in P$ defined as

$y^{\prime}=\text{argmax}_{y^{\prime\prime}\in
P}(\textbf{E}_{t})^{T}y^{\prime\prime}\ ,$

and let $M$ be this value. By Lemma 15, we have that

$M\geq F(x^{*})-F(y(t))\ .$

Since all estimates are good, we also have that

$\sum_{j\in[n]}y_{j}\cdot w_{j}(t)\geq\sum_{j\in[n]}y^{\prime}_{j}\cdot
w_{j}(t)\geq M-\sum_{j\in[n]}y^{\prime}_{j}|w_{j}(t)-\mathbb{E}[f(j\mid
R(t))]|\geq M-n\delta F(x^{*})\ ,$

where $y\in Q$ is the point chosen by the algorithm such that
$(w(t))^{T}y\geq(w(t))^{T}y^{\prime\prime}$ for all $y^{\prime\prime}\in P$.
Therefore, we obtain that

$\displaystyle\sum_{j\in[n]}y_{j}\cdot\mathbb{E}[f(j\mid R(t))]$
$\displaystyle\geq\sum_{j\in[n]}y_{j}\cdot w_{j}(t)-\sum_{j\in
n}y_{j}|w_{j}(t)-\mathbb{E}[f(j\mid R(t))]|$
$\displaystyle\geq\sum_{j\in[n]}y^{\prime}_{j}\cdot w_{j}(t)-n\delta F(x^{*})$
$\displaystyle\geq M-2n\delta F(x^{*})$
$\displaystyle\geq(1-2n\delta)F(x^{*})-F(y(t))\ ,$

as desired. ∎

We can conclude with the main result we need.

######  Lemma 18.

With high probability, if $f$ is a monotone submodular function such that
$F(x^{*})\geq f(i)$ for all $i\in[n]$, the fractional solution $y$ found by
the continuous greedy algorithm satisfies

$F(y)\geq\left(1-1/e-1/(2n)\right)\cdot F(x^{*})\ .$

###### Proof.

Assume without loss of generality that $F(y(t))\leq F(x^{*})$ for all $t$,
since otherwise the assertion follows immediately from the fact that $F(y)\geq
F(y(t))$. The assumption is not trivial, since $x^{*}$ is in the set $P$,
while $y(t)$ is allowed to be inside the bigger polytope $Q$.

The algorithm starts with $F(y(0))=0$. We lower bound the increase in value at
each step of the algorithm. The proof is the same as in [10]. Let $R(t)$ be
the random set containing each element $j$ independently with probability
$y_{j}(t)$, and $D(t)$ the set containing each element independently with
probability $\Delta_{j}(t)=y_{j}(t+\delta)-y_{j}(t)$. We can easily see that

$F(y(t+\delta))=\mathbb{E}[R(t+\delta)]\geq\mathbb{E}[f(R(t)\cup D(t))]\ .$

This is because $R(t+\delta)$ contains $j$ with probability
$y_{j}(t)+\Delta_{j}(t)$, while $R(t)\cup D(t)$ contains $j$ with smaller
probability $1-(1-y_{j}(t))(1-\Delta_{j}(t))$. The two distributions can be
coupled so that $R(t)\cup D(t)$ is a subset of $R(t+\delta)$, and we can
conclude by the monotonicity of $f$. By denoting $y^{*}\in Q$ the direction in
which we move $y(t)$, we can write

$\displaystyle F(y(t+\delta))-F(y(t))$ $\displaystyle\geq\mathbb{E}[f(R(t)\cup
D(t))-f(R(t))]$
$\displaystyle\geq\sum_{j\in[n]}\mathbb{P}[D(t)=\\{j\\}]\cdot\mathbb{E}[f(j\mid
R(t))]$ $\displaystyle=\sum_{j\in[n]}(\delta y_{j}^{*})\prod_{j^{\prime}\neq
j}(1-\delta y_{j^{\prime}}^{*})\cdot\mathbb{E}[f(j\mid R(t))]$
$\displaystyle\geq\sum_{j\in[n]}(\delta
y_{j}^{*})(1-n\delta)\cdot\mathbb{E}[f(j\mid R(t))]\ .$

Using Lemma 17 and $F(y(t))\leq F(x^{*})$, we obtain

$\displaystyle F(y(t+\delta))-F(y(t))$ $\displaystyle\geq\sum_{j\in[n]}(\delta
y_{j}^{*})(1-n\delta)\cdot\mathbb{E}[f(j\mid R(t))]$
$\displaystyle\geq\delta(1-n\delta)((1-2n\delta)\cdot
F(x^{*})-F(y(t)))\geq\delta((1-3n\delta)\cdot F(x^{*})-F(y(t))\ .$

Writing $\tilde{F}(x^{*})=(1-3n\delta)\cdot F(x^{*})$, we rearrange to get

$\displaystyle\tilde{F}(x^{*})-F(y(t+\delta))\leq(1-\delta)(\tilde{F}(x^{*})-F(y(t)))\
.$

It follows now by induction that for any $k\geq 0$ (recall that $F(y(0))=0$),

$\tilde{F}(x^{*})-F(y(k\delta))\leq(1-\delta)^{k}\tilde{F}(x^{*})\ .$

Hence,

$\displaystyle F(y(1))$
$\displaystyle\geq\tilde{F}(x^{*})(1-(1-\delta)^{1/\delta})$
$\displaystyle\geq\tilde{F}(x^{*})(1-1/e)$ $\displaystyle=(1-3n\delta)\cdot
F(x^{*})\cdot(1-1/e)$ $\displaystyle\geq(1-1/e-1/(2n))\cdot F(x^{*})\ ,$

which concludes the proof. ∎

##  Appendix B Proof of Lemma 4

For convenience, we restate the assertion here: Let $T^{*},T^{**}$ be disjoint
sets of sinks and let $b\in[0,\beta]^{E_{\geq i}}$. Then $b\in\mathrm{B}_{\geq
i}(T^{*}\cup T^{**},\alpha,\beta)$ if and only if there exist
$b^{\prime}+b^{\prime\prime}=b$ with $b^{\prime}\in\mathrm{B}_{\geq
i}(T^{*},\alpha,\beta)$ and $b^{\prime\prime}\in\mathrm{B}_{\geq
i}(T^{**},\alpha,\beta)$.

###### Proof.

Let $(b,b_{v,g},x_{b,g})\in\mathrm{CLP}_{\geq i}(T^{*}\cup
T^{**},\alpha,\beta)$ and assume without loss of generality that each
constraint (2) is tight. Let

$x^{\prime}_{v,g}:=\begin{cases}x_{v,g}&\text{ if }v\in T^{*}\\\ 0&\text{
otherwise. }\end{cases}\text{ and
}b^{\prime}_{v,g}:=\begin{cases}b_{v,g}&\text{ if }v\in T^{*}\\\ 0&\text{
otherwise. }\end{cases}$

Similarly, let

$x^{\prime\prime}_{v,g}:=\begin{cases}x_{v,g}&\text{ if }v\in T^{**}\\\
0&\text{ otherwise. }\end{cases}\text{ and
}b^{\prime\prime}_{v,g}:=\begin{cases}b_{v,g}&\text{ if }v\in T^{**}\\\
0&\text{ otherwise. }\end{cases}$

Define $b^{\prime}(e)=\sum_{v\in
T^{*}}\sum_{g\in\mathcal{C}(v,\alpha,\beta)}b^{\prime}_{v,g}(e)$ and
$b^{\prime\prime}(e)=\sum_{v\in
T^{**}}\sum_{g\in\mathcal{C}(v,\alpha,\beta)}b^{\prime\prime}_{v,g}(e)$. Then
$(b^{\prime},b^{\prime}_{v,g},x^{\prime}_{v,g})\in\mathrm{CLP}_{\geq
i}(T^{*},\alpha,\beta)$,
$(b^{\prime\prime},b^{\prime\prime}_{v,g},x^{\prime\prime}_{v,g})\in\mathrm{CLP}_{\geq
i}(T^{**},\alpha,\beta)$, and $b=b^{\prime}+b^{\prime\prime}$.

For the other direction, let
$(b^{\prime},b^{\prime}_{v,g},x^{\prime}_{v,g})\in\mathrm{CLP}_{\geq
i}(T^{*},\alpha,\beta)$ and
$(b^{\prime\prime},b^{\prime\prime}_{v,g},x^{\prime\prime}_{v,g})\in\mathrm{CLP}_{\geq
i}(T^{**},\alpha,\beta)$. Then
$(b^{\prime}+b^{\prime\prime},b^{\prime}_{v,g}+b^{\prime\prime}_{v,g},x^{\prime}_{v,g}+x^{\prime\prime}_{v,g})\in\mathrm{CLP}_{\geq
i}(T^{*}\cup T^{**},\alpha,\beta)$. ∎