# Submodular Maximization Under A Matroid Constraint: Asking more from an old
friend, the Greedy Algorithm

Nived Rajaraman  Indian Institute of Technology, Madras,
Department of Electrical Engineering,
Indian Institute of Technology, Madras, Chennai, India
<EMAIL_ADDRESS>Rahul Vaze  Tata Institute of Fundamental Research,
Mumbai,
School of Technology and Computer Science,
Tata Institute of Fundamental Research Mumbai, India<EMAIL_ADDRESS>
###### Abstract

The classical problem of maximizing a submodular function under a matroid
constraint is considered. Defining a new measure for the increments made by
the greedy algorithm at each step, called the discriminant, improved
approximation ratio guarantees are derived for the greedy algorithm. At each
step, discriminant measures the multiplicative gap in the incremental
valuation between the item chosen by the greedy algorithm and the largest
potential incremental valuation for eligible items not selected by it. The new
guarantee subsumes all the previous known results for the greedy algorithm,
including the curvature based ones, and the derived guarantees are shown to be
tight via constructing specific instances. More refined approximation
guarantee is derived for a special case called the submodular welfare
maximization/partition problem that is also tight, for both the offline and
the online case.

###### keywords:

Submodular maximization, Partition Problem, Greedy Algorithms

##  1 Introduction

We consider the problem of maximizing a submodular function under a matroid
constraint. This is a classical problem (Edmonds (1971)), with many important
special cases, e.g., uniform matroid (the subset selection problem), partition
matroid (submodular welfare/partition problem). The problem is known to be NP-
hard even for special cases, and the earliest theoretical results on this
problem date back to the seminal work of Edmonds (1971); Nemhauser and Wolsey
(1978); Fisher et al. (1978), that derived tight approximation guarantees. In
particular, for the general problem, the greedy algorithm is known to achieve
a $1/2$-approximation (Fisher et al. (1978)), while for the uniform matroid
(subset selection problem), where the objective is to select the optimal
subset under a cardinality constraint, the greedy algorithm is known to be
$(1-1/e)$-approximate (Edmonds (1971); Nemhauser and Wolsey (1978)). Moreover,
these guarantees are tight and instance independent.

Even though the theoretical work limits the instance independent guarantees
for the greedy algorithm to be $1/2$ or $1-1/e$, in practice, the performance
of the greedy algorithm is far better, sometimes even close to the optimal. To
explain this phenomenon, work on instance dependent guarantees started with
(Conforti and Cornuéjols (1984)), which showed that using the concept of
curvature, the approximation guarantee of the greedy algorithm can be improved
from $1/2$ to $\frac{1}{1+c}$, where $c$ is the curvature that captures the
distance of the function from being linear. Lower curvature is better, with
zero-curvature (modular) giving the optimal solution. For the special case of
subset selection problem, the guarantee can be improved from $(1-1/e)$ to
$(1-e^{-c})/c$ ($\rightarrow 1$ as $c\rightarrow 0$) (Conforti and Cornuéjols
(1984)). In more recent work, (Soma and Yoshida (2017)) has improved the
guarantee to $(1-\gamma_{h}/e-\epsilon)$, where $\gamma_{h}$ is the
$h$-curvature and for any $\epsilon>0$. Most of the theoretical work on the
greedy algorithm assumes the value oracle model, where a polynomial algorithm
is assumed to exist that can compute the optimal increment in each iteration.
To obviate this possibly restrictive assumption, approximate greedy algorithms
were considered by Goundan and Schulz (2007), where the increment is only
available up to a certain approximation guarantee. There is also work on
finding guarantees for non-monotone submodular maximization problems (see,
e.g., Feige et al. (2011)).

Compared to deterministic algorithms, randomized algorithms (Calinescu et al.
(2011)) can improve the instance dependent guarantee to $(1-e^{-c})/c$ (with
the continuous greedy algorithm) for the general problem, which can be further
refined for the subset selection problem to $(1-c/e)$ (Sviridenko and Ward
(2013)) using a non-oblivious local search algorithm.

In addition to the subset selection problem, another important special case of
the general problem is the submodular welfare maximization/partition problem,
where there is a set of items/resources $\mathcal{R}$ that has to be
partitioned among the set of $n$ agents, each agent has a submodular valuation
function $f_{i}$ over the subsets of $\mathcal{R}$, and the problem is to find
the partition of $\mathcal{R}$ that maximizes the sum of the agents’
valuations after partition. This problem was addressed in (Fisher et al.
(1978)) itself that gave a $1/2$-approximate guarantee for the greedy
algorithm, which surprisingly holds even in the online setting (the elements
of the resource set $\mathcal{R}$ are revealed sequentially, and on arrival of
each new element it has to be assigned irrevocably to one of the agents).
Randomized algorithm with $(1-1/e)$-approximation guarantee was proposed in
(Vondrák (2008)) for this problem. Instance dependent guarantees as a function
of the curvature $c$ for the general problem of course carry over to this
problem as well.

For deriving instance dependent guarantees, the motivation to consider the
curvature of the submodular function was that if the curvature is small, then
the greedy algorithm remains ‘close’ to the optimal solution. In a similar
spirit, in this paper, we consider a new measure of the problem instance and
the greedy algorithm, called the discriminant, where larger discriminant helps
the greedy algorithm to stay ‘close’ to the optimal. We exploit the
discriminant for finding improved instance dependent guarantees for the greedy
algorithm when used to solve the general problem, the partition problem, and
the online partition problem under the value oracle model.

We begin the discussion on discriminant using the partition problem and then
describe the corresponding definition of the discriminant for the general
problem. For the partition problem, the greedy algorithm at each iteration
choses the item-agent pair that maximizes the incremental valuation, and
assigns the chosen item to the chosen agent. We define the discriminant
$d_{s}$ at iteration $s$ of the greedy algorithm, as the ratio of the
incremental increase in valuation made by the greedy algorithm (because of the
item-agent pair chosen by greedy) and the best incremental increase (possible)
in valuation among all other agents (not chosen by greedy) for the item chosen
by the greedy algorithm in iteration $s$, given the past choices of the greedy
algorithm until iteration $s-1$. Formal definition of $d_{s}$ is given in
Definition 3.2. It is easy to see that uniformly (over all iterations) large
discriminant should help the greedy algorithm in staying ‘close’ to the
optimal solution.

The intuition behind considering the discriminant becomes clear especially for
the following asymmetric partition problem, where among the $n$-agents, one of
them (say $i$) has a valuation such that $f_{i}(S)>>f_{j}(S)$ $\forall\ j\neq
i,\forall\ S\subset\mathcal{R}$. Clearly, the greedy algorithm (assign all
resources to agent $i$) is optimal, while the best known bound for it over
this instance is $(1-e^{-c})/c$, where $c=\max_{i}c_{i}$ ($c_{i}$ is the
curvature for user $i$) can be large, resulting in a poor guarantee.
Incidentally though, the discriminant remains uniformly large throughout the
execution of the greedy algorithm for this example, indicating that
discriminant may be related with the performance of the greedy algorithm and
can imply better guarantees.

So the first question we ask: can we generalize this intuition and derive a
theoretical guarantee on the approximation ratio of the greedy algorithm for
the partition problem as a function of the discriminant without losing out on
the dependence of the curvature. The answer turns out to be positive: we show
that the greedy algorithm (with a slight modification for tie-breaking) can
achieve an approximation ratio of

$\min\left\\{1,\frac{1}{\max_{s}\\{\frac{1}{d_{s}}+c_{s}\\}}\right\\},$ (1)

where $c_{s}$ is the curvature of the user chosen at iteration $s$ of the
greedy algorithm. This result nicely explains the optimal performance of the
greedy algorithm for the asymmetric partition problem, since for that $d_{s}$
is very large for all $s$, and our approximation guarantee approaches $1$ as
$d_{s}\rightarrow\infty,\ \forall\ s$ and since $c_{s}\leq 1$. By definition
$d_{s}\geq 1$, thus, compared to the previous best known approximation
guarantee of $\frac{1}{1+c}$ ($c=\max_{u\in\text{user set}}c_{u}$) for the
greedy algorithm (Conforti and Cornuéjols (1984)), our result is stronger
unless $d_{s}=1$ for some iteration $s$ and the curvature of the user chosen
in iteration $s$ is the largest among all the users, in which case it equals
$\frac{1}{1+c}$. So our result provides a newer and stronger guarantee for
asymmetric problems, when $d_{s}$ remains large, and exploits a new dimension
(discriminant) of the submodular partition problem that is tied to the greedy
algorithm. Similar to the earlier approximation guaratees for the greedy
algorithm (Fisher et al. (1978)), we show that the derived approximation
guarantee (1) holds for even the online partition problem, and the bound is
tight. We refer the reader to (Korula et al. (2015)) for more details and
review of the recent progress on the online problem under
stochastic/secretarial settings). We also provide some intuition on the
specific form of dependence of the discriminant on the approximation guarantee
(1) in Remark 3.6.

Next, the natural question is: can we derive discriminant dependent guarantees
for the greedy algorithm for the general submodular maximization problem under
a matroid constraint. The answer to this question is also yes, however, the
guarantee is little different and is given by

$\min\left\\{1,\frac{1}{\\{\frac{1}{d_{\min}}+c\\}}\right\\},$ (2)

where $d_{\min}=\min_{s}d_{s}$, and the discriminant at iteration $s$ $d_{s}$
for this case is defined as: given the past choices of the greedy algorithm
until iteration $s-1$, $d_{s}$ is the ratio of the incremental increase in
valuation (item chosen by greedy) and the best incremental increase (possible)
in valuation among all other items (other than the one chosen by the greedy
that are still available for selection) in iteration $s$ (formal definition is
provided in Definition 2.9). Once again as $d_{\min}\geq 1$, our guarantee
subsumes the previous known result of $1/(1+c)$, and matches that only if
$d_{s}=1$ is some iteration $s$.

The intuition for the approximation guarantee (2) can be developed by
considering the special case of the uniform matroid (subset selection
problem), where the greedy algorithm selects a new element that has the
largest incremental increase in function valuation at each iteration. If in
each iteration $s\geq 1$, $d_{s}$ is large, the greedy algorithm is making
rapid progress towards the optimal valuation, by selecting ‘near-optimal’
elements, since the elements it rejects have comparatively low incremental
valuation. We also show that this guarantee is tight for the general problem.

Our work exploits an unexplored parameter of the greedy algorithm,
discriminant, and provides a new guarantee that subsumes all previous
guarantees. The utility of discriminant based guarantee is easily manifested
for the submodular partitioning problems, where the valuation functions for
different users have inherent asymmetry, such that the discriminants are
uniformly large, e.g. in subcarrier and power allocation in wireless systems
(Thekumparampil et al. (2016)). As far as we know, this is the first time an
algorithm dependent (greedy algorithm) and instance dependent approximation
guarantee has been derived for submodular maximization problem. Even though
the guarantee (discriminant) is algorithm dependent, however, since the greedy
algorithm is deterministic, the discriminants can be computed once the problem
instance is specified, and computational complexity of finding the
discriminant is same as the complexity of the greedy algorithm.

In this paper, we have discovered a new connection between the multiplicative
gap (which we call the discriminant) between the locally best increment made
by the greedy algorithm and the next best increment possible, and its
performance guarantee for the submodular maximization problem that has wide
applications. The discriminant appears to be a fundamental quantity in
studying greedy algorithms, and we believe that such an approach can also lead
to improved guarantees for similar combinatorial problems, e.g., the
generalized assignment (GAP) problem (Fleischer et al. (2006)), where the
greedy algorithm is known/observed to perform well.

##  2 Monotone Submodular Maximization over a Matroid

######  Definition 2.1.

(Matroid) A matroid over a finite ground set $N$ is a pair $(N,\mathcal{M})$,
where $\mathcal{M}\subseteq 2^{N}$ (power set of $N$) that satisfies the
following properties:

  1. 1.

$\phi\in\mathcal{M}$,

  2. 2.

If $T\in\mathcal{M}\text{ and }S\subset T\Rightarrow S\in\mathcal{M}$
[independence system property],

  3. 3.

If $S,T\in\mathcal{M}:|T|>|S|\Rightarrow\exists\ x\in T\setminus
S:S\cup\\{x\\}\in\mathcal{M}$ [augmentation property]. $\mathcal{M}$ is called
the family of independent sets.

######  Definition 2.2.

(Rank of a matroid) For $S\subseteq N$, the rank function of a matroid
$(N,\mathcal{M})$ is defined as $r(S)=\max\\{|M|:M\subseteq
S,M\in\mathcal{M}\\}$, and rank of the matroid is $r(N)$, the cardinality of
the largest independent set. For a matroid to have rank $K$, there must exist
no independent sets of cardinality $K+1$.

For many applications, two special cases of matroids are of interest, namely
the uniform and the partition matroid that are defined as follows.

######  Definition 2.3.

(Uniform Matroid) For some $K>0$, the uniform matroid over a ground set $N$ is
defined as $(N,\mathcal{M}^{u})$, where $\mathcal{M}^{u}=\\{S:S\subseteq
N,|S|\leq K\\}$. The uniform matroid has rank $K$.

######  Definition 2.4.

(Partition Matroid) A ground set $N$, and its partition
$\\{P_{i}:i=1,2,\dots,p\\}$, $\cup_{i}P_{i}=N$, and $\ P_{i}\cap
P_{j}=\phi,i\neq j$ are given. Given integers $k_{i}:1\leq k_{i}\leq|P_{i}|$,
the partition matroid over $N$ is defined as $(N,\mathcal{M}^{p})$, where
$\mathcal{M}^{p}=\\{S:S\subseteq N\text{ and }|S\cap P_{i}|\leq k_{i}\text{
for }i=1,2,\dots,p\\}$. This partition matroid has rank $\sum_{i=1}^{p}k_{i}$.

######  Definition 2.5.

(Monotone and Submodular Function) A set function
$Z:2^{N}\rightarrow\mathbb{R}$ is defined to be monotone if for $S\subset
T\subseteq N$, $Z(S)\leq Z(T)$, and submodular if for all $T\subseteq
N\setminus\phi,S\subset T\text{ and }x\notin T$, $\ Z(T\cup\\{x\\})-Z(T)\leq
Z(S\cup\\{x\\})-Z(S)\text{ [Diminishing Returns]}$. Without loss of
generality, we assume $Z(\phi)=0$ $(\Rightarrow Z(S)\geq 0,\forall\ S\subset
N)$.

######  Problem 2.6.

Given a matroid $(N,\mathcal{M})$ of rank $K$, and a monotone and submodular
function $Z:2^{N}\rightarrow{\mathbb{R}}$, the problem is to find $\text{max
}\\{Z(S):S\in\mathcal{M}\\}$.

Since $Z(S)$ is non-decreasing, we only consider feasible solutions to Problem
2.6 that have cardinality $K$ even if there exists a smaller solution with the
same valuation. For the rest of the paper we use the following notation. Given
a set $S$ associated with an ordering $(s_{1},s_{2},\dots,s_{|S|})$, $S^{i}$
denotes the partial ordering $(s_{1},s_{2},\dots,s_{i})$. The increment in
valuation of set $S$ upon addition of element $q$ to $S$ is defined as

$\rho_{q}(S)=Z(S\cup\\{q\\})-Z(S).$

The most natural algorithm to solve Problem 2.6 is a greedy algorithm
(Algorithm 1) that incrementally adds an element to the existing set that
provides the largest increase in the set valuation as described next.

Algorithm 1 Greedy Algorithm for monotone submodular maximization over a
rank-$K$ matroid $(N,\mathcal{M})$

procedure $\mathsf{GREEDY}$

Initialize: $G^{0}=\phi,i=1$

while $i\leq K$ do

$q_{i}\leftarrow\underset{q}{\text{ argmax}}\left\\{\rho_{q}(G^{i-1}):\ q\cup
G^{i-1}\in\mathcal{M}\right\\}$ $\triangleright$ Pick arbitrarily in case of
ties

$G^{i}\leftarrow G^{i-1}\cup\\{q_{i}\\}$

$i\leftarrow i+1$

end while

Return $G=G^{K}$

end procedure

We let $\Omega$ denote the global optimal solution and $G$ the solution
generated by the $\mathsf{GREEDY}$ algorithm for the problem in context,
respectively. Then the following guarantees are known for Problem 2.6.

######  Theorem 2.7.

Fisher et al. (1978) For Problem 2.6, $\frac{Z(G)}{Z(\Omega)}\geq\frac{1}{2}$.

The above $\frac{1}{2}$-approximation bound is a global lower bound on the
performance of the greedy algorithm for Problem 2.6, which can be further
improved with the knowledge of the curvature parameter, $c$ of the monotone
and submodular valuation function, that is defined as

$c=1-\underset{S,j\in S^{*}}{\text{min
}}\frac{\rho_{j}(S)}{\rho_{j}(\phi)},\quad\text{where }\ S^{*}=\\{j:j\in
N\setminus S,\ \rho_{j}(\phi)>0\\}.$ (3)

By submodularity, we have $c\leq 1$. The case $c=0$ implies that the function
valuations are linear.

######  Theorem 2.8 (Conforti and Cornuéjols (1984) Theorem 2.3).

For Problem 2.6, $\frac{Z(G)}{Z(\Omega)}\geq\frac{1}{1+c}$.

The first main result of this paper is presented in the Theorem 2.10, where we
derive stronger approximation guarantees for the $\mathsf{GREEDY}$ algorithm
as a function of ‘discriminant’ (as defined next) in addition to the curvature
as done in Theorem 2.8.

######  Definition 2.9.

Let $S_{\bot}:=\\{j:j\in N\setminus S,\ j\cup S\in\mathcal{M}\\}$. Then, given
the selected set $G^{i-1}$ by the $\mathsf{GREEDY}$ algorithm at the end of
iteration $i-1$, the discriminant $d_{i}$ at iteration $i$ is defined as:

$d_{i}=\frac{\rho_{g_{i}}(G^{i-1})}{\underset{g^{\prime}_{i}\neq
g_{i}}{\text{max }}\rho_{g_{i}^{\prime}}(G^{i-1})},$

where $g_{i}=\underset{g}{\text{argmax }}\rho_{g}(G^{i-1}),\text{ and
}g^{\prime}_{i}\in G^{i-1}_{\bot}.$ Define $d_{i}:=\infty\ \text{ if }\forall
g^{\prime}_{i}\in G^{i-1}_{\bot}:g^{\prime}_{i}\neq g_{i},\
\rho_{g_{i}^{\prime}}(G^{i-1})=0$. Moreover, the minimum discriminant is
defined as $d_{\text{min}}=\underset{i<i_{0}}{\text{min }}d_{i}$, where
$i_{0}=\text{min }\\{i:|G^{i-1}_{\bot}|=K-i+1\\}$, where $K$ is the rank of
the matroid.

Consider the element $g_{i}$ selected by the $\mathsf{GREEDY}$ algorithm in
iteration $i$ and consider the incremental gain $\rho_{g_{i}}(G^{i-1})$. Find
the best element $g_{i}^{\prime}$ other than $g_{i}$ such that $G^{i-1}\cup
g_{i}^{\prime}\in\mathcal{M}$, and compute the incremental increment
$\rho_{g_{i}^{\prime}}(G^{i-1})$. The ratio of the two is defined as the
discriminant in iteration $i$. Moreover, index $i_{0}$ is the earliest
iteration $i$ in the execution of the $\mathsf{GREEDY}$ algorithm where the
number of items that are not part of the $\mathsf{GREEDY}$ algorithm’s chosen
set equals $K-i+1$. This is useful, since after iteration $i_{0}$ we show that
the items chosen by the $\mathsf{GREEDY}$ algorithm belong to the optimal set
as well. Thus, to compute $d_{\text{min}}$, minimization needs to be carried
out over a smaller set.

######  Theorem 2.10.

Using the $\mathsf{GREEDY}$ algorithm (Algorithm 1) for Problem 2.6
guarantees:

$\frac{Z(G)}{Z(\Omega)}\geq\text{min}\left(1,\frac{1}{\left(c+\underset{i<i_{0}}{\text{max
}}\frac{1}{d_{i}}\right)}\right)=\text{min}\left(1,\frac{1}{c+\frac{1}{d_{\text{min}}}}\right).$

Discussion: Since $d_{\text{min}}\geq 1$, the approximation guarantee provided
by Theorem 2.10 subsumes the best known guarantee for the greedy algorithm
(Theorem 2.8), and matches that only when there is a tie in some iteration
before $i_{0}$, in which case it matches the result of Theorem 2.8
($\frac{1}{1+c}$). Theorem 2.10 shows that if the problem instance has large
discriminants, the greedy algorithm is theoretically far better than what was
previously known. The proof of Theorem 2.10 is rather technical and does not
allow simple intuitive explanation. We provide intuition for the specific form
of the guarantee as the function of the discriminant ($1/d$) for the special
case of the submodular partition problem in the next section in Remark 3.6.

All proofs are provided in the appendices. Here we give a brief proof sketch
for Theorem 2.10.

Proof Sketch: The key step in proving Theorem 2.10 is to show that

$Z(\Omega)\leq c\sum_{i:g_{i}\in
G\setminus\Omega}\rho_{g_{i}}(G^{i-1})+\sum_{i:g_{i}\in
G\cap\Omega}\rho_{g_{i}}(G^{i-1})+\sum_{i:\omega_{i}\in\Omega\setminus
G}\rho_{\omega_{i}}(G),$ (4)

via Lemma 5.13, and using a particular ordering for $\Omega$ that is a
function of the ordering of $G$ (defined in Lemma 5.2). We then show in Lemma
5.18 that for each $i$, $\rho_{\omega_{i}}(G^{i-1})$ (which upper bounds
$\rho_{\omega_{i}}(G)$) cannot be larger than
$\frac{\rho_{g_{i}}(G^{i-1})}{d_{i}}$, and substitute this back into the upper
bound (4) for $Z(\Omega)$. Subsequently, as shown in Section 2.1 B, the set
$\\{i:i\geq i_{0}\\}$ is a subset of $\\{i:g_{i}\in G\cap\Omega\\}$, which
implies that $\\{i:i<i_{0}\\}$ is a superset of $\\{i:g_{i}\in
G\backslash\Omega\\}$ as well as $\\{i:g_{i}\in\Omega\backslash G\\}$, and we
replace the summation index set for the first and the third term in (4) with
$\\{i:i<i_{0}\\}$ to further upper bound $Z(\Omega)$. The statement of Theorem
2.10 then follows by rearranging terms and simplifying. $\Box$

###  2.1 Discussion on the definition of discriminant for Problem 2.6

Essentially, the discriminant in each iteration (Definition 2.9) is the ratio
of the locally best increment made by the $\mathsf{GREEDY}$ algorithm and the
next best possible increment at any iteration in its execution. However, there
is a little subtlety which is explained as follows. Note the following cases:

  1. A

If $\underset{g^{\prime}_{i}\neq g_{i}}{\text{max
}}\rho_{g_{i}^{\prime}}(G^{i-1})=0$, $d_{i}$ is defined as $\infty$ for the
sake of continuity and can be removed from the minimization over $i$ in the
definition of $d_{\min}$. If $i_{0}=1$, the problem is trivial (there exists
only $1$ feasible solution).

  2. B

In the following argument, we show that in every iteration after $i_{0}$, the
element chosen by the $\mathsf{GREEDY}$ algorithm belongs to the optimal
solution, i.e., $\\{i:i\geq i_{0}\\}\subseteq\\{i:g_{i}\in G\cap\Omega\\}$.
Let at a iteration $i$, $|G^{i-1}_{\bot}|=K-i+1$, that is, there exist exactly
$K-i+1$ valid choices of elements that can be added to $G^{i-1}$ to generate
$G^{i}$.

    1. (a)

For such $i$, Lemma 5.11 states that $S=G^{i-1}_{\bot}$ is a unique set that
satisfies $|S|=K-i+1$ and $G\cup G^{i-1}_{\bot}\in\mathcal{M}$. Thus it
follows from Corollary 5.9, that $G^{i-1}_{\bot}\subseteq\Omega$, where
$\Omega$ is the optimal solution.

    2. (b)

From the uniqueness of $S$, it follows that $G=G^{i-1}\cup G^{i-1}_{\bot}$.
Thus, $G^{i-1}_{\bot}\subseteq G$.

    3. (c)

From (a) and (b), it follows that for iteration $i$, $|G^{i-1}_{\bot}|=K-i+1$,
then $G^{i-1}_{\bot}\in G\cap\Omega$.

    4. (d)

If in iteration $i$, $|G^{i-1}_{\bot}|=K-i+1$, then for all $j>i$,
$|G^{j-1}_{\bot}|=K-j+1$.

Recalling the definition of $i_{0}=\text{min }\\{i:|G^{i-1}_{\bot}|=K-i+1\\}$,
from (c) and (d) we conclude that for every iteration $i\geq i_{0}$, we have
$G^{i-1}_{\bot}\in G\cap\Omega$.

######  Lemma 2.11.

The approximation guarantee obtained in Theorem 2.10 is tight.

The result of Theorem 2.10 is derived by upper bounding (22). To prove Lemma
2.11, in Appendix 5.6, we provide a problem instance for which the
approximation guarantee matches the bound derived in (22).

Next, we consider the special case of Problem 2.6, the submodular partition
problem, and provide better guarantees than the general problem as a function
of the discriminants.

##  3 Submodular Partition Problem

######  Problem 3.1.

Given a set of allocable resources $\mathcal{R}$ with $|\mathcal{R}|=n$, and a
set of users denoted by $\mathcal{U}$ with $|\mathcal{U}|=m$. Each user $u$
has a monotone and submodular valuation function
$Z_{u}(S):2^{\mathcal{R}}\rightarrow\mathbb{R}$, where without loss of
generality, $Z_{u}(\phi)=0,\forall u\in\mathcal{U}$. The submodular partition
problem is to find a partition of the set of resources $\mathcal{R}$, among
the set of users $\mathcal{U}$ such that the sum of the valuations of
individual users is maximized. That is:

$\text{max }\sum_{u\in\mathcal{U}}Z_{u}(S_{u}),\text{subject to:}\
S_{u}\subseteq\mathcal{R}\quad\forall u,\ S_{u_{i}}\cap
S_{u_{j}}=\phi,\text{for }u_{i}\neq u_{j}.$

The submodular partition problem is a special case of Problem 2.6, where the
matroid is the partition matroid $(\mathcal{R},\mathcal{M}^{p})$,

$\mathcal{M}^{p}=\\{S:S\subseteq\mathcal{V},\ |S\cap\mathcal{V}_{r}|\leq
1\quad\forall r\in\mathcal{R}\\},$

where
$\mathcal{V}=\mathcal{U}\times\mathcal{R}=\\{(u,r):u\in\mathcal{U},r\in\mathcal{R}\\}$,
and $\mathcal{V}_{r}=\\{(u,r):u\in\mathcal{U}\\}$ and
$Z(S)=\sum_{u\in\mathcal{U}}Z_{u}(S_{u})$ is submodular, since the sum of
submodular functions is submodular. For this special case, we denote the
increment in valuation by allocating resource $r$ to user $u$ given the
existing set $S$ as:

$\rho_{r}^{u}(S):=Z(S\cup\\{(u,r)\\})-Z(S)=Z_{u}(S_{u}\cup\\{r\\})-Z_{u}(S_{u}).$
(5)

Since Problem 3.1 is a special case of Problem 2.6, Theorem 2.8 implies an
approximation guarantee of $\frac{1}{1+c}$, where $c$ is the curvature of
$\sum_{u\in\mathcal{U}}Z_{u}(S_{u})$. It is known that
$c=\underset{u\in\mathcal{U}}{\text{max }}c_{u}$.

Next, we describe a modified greedy algorithm, called $\mathsf{GREEDY-M}$,
where the modification is in the tie-breaking rule compared to
$\mathsf{GREEDY}$, that uses curvature and incremental gain ratios, and derive
improved approximation guarantee in Theorem 2.10 for it compared to Theorem
2.8. To define the modified greedy algorithm, we need the following
definition. Let for $S\in\mathcal{M}^{p}$, the set of unallocated resources in
$S$ be defined as

$\mathcal{R}(S_{\bot}):=\\{r:\forall u\in\mathcal{U},(u,r)\not\in S\\},$

i.e., the resources that do not appear in the set of user-resource pairs that
are part of $S$.

Algorithm 2 Modified Greedy Algorithm for the Submodular Partition problem

1:procedure $\mathsf{GREEDY-M}$

2: Initialize: $G^{0}=\phi,i=1$

3: while $i\leq|\mathcal{R}|=n$ do

4: $(u^{*},r^{*})\leftarrow\underset{u,r}{\text{
argmax}}\left\\{\rho_{r}^{u}(G^{i-1}):\
r\in\mathcal{R}(G^{i-1}_{\bot})\right\\}$

5:$\triangleright$ Tie Breaking Rule: In case there is more than one optimal
pair, choose the user-resource pair $(u,r)$ that minimizes
$c_{u}+\frac{1}{d_{i}(u,r)}$, where
$d_{i}(u,r):=\frac{\rho_{r}^{u}(G^{i-1})}{\max_{u^{\prime}\neq
u}\rho_{r}^{u^{\prime}}(G^{i-1})}$

6: $G^{i}\leftarrow G^{i-1}\cup\\{(u^{*},r^{*})\\}$

7: $i\leftarrow i+1$

8: end while

9: Return $G=G^{n}$

10:end procedure

######  Definition 3.2.

Let the set chosen by the $\mathsf{GREEDY-M}$ algorithm at the end of
iteration $i-1$ be $G^{i-1}$. Consider the user-resource pair $(u^{*},r^{*})$
selected by the greedy algorithm in iteration $i$ and consider its incremental
gain $\rho_{r^{*}}^{u^{*}}(G^{i-1})$. For the resource $r^{*}$ chosen by the
$\mathsf{GREEDY-M}$, find the best user $u^{\prime}$ other than $u^{*}$ with
the highest incremental valuation for $r^{*}$ and compute the incremental gain
$\rho_{r^{*}}^{u^{\prime}}(G^{i-1})$. The ratio of the two incremental gains
is defined as the discriminant $d_{i}^{p}$ ($p$ stands for the partition
problem) in iteration $i$, as

$d_{i}^{p}=\frac{\rho_{r^{*}}^{u^{*}}(G^{i-1})}{\underset{u^{\prime}\neq
u^{*}}{\text{max }}\rho_{r^{*}}^{u^{\prime}}(G^{i-1})},\quad\text{where
}(u^{*},r^{*})=\underset{u,r\in\mathcal{R}(G^{i-1}_{\bot})}{\text{argmax
}}\rho_{r}^{u}(G^{i-1}).$

With respect to the $\mathsf{GREEDY-M}$ algorithm,
$d_{i}^{p}=d_{i}(u^{*},r^{*})$.

At iteration $i$, discriminant $d_{i}^{p}$ is the ratio of the increment due
to the best local user-resource pair chosen by the $\mathsf{GREEDY-M}$
algorithm and the increment possible if the resource chosen by the
$\mathsf{GREEDY-M}$ algorithm is allocated to the user who values it second
most.

######  Remark 3.3.

For $\mathsf{GREEDY-M}$ algorithm, if the tie-breaking rule also fails to
produce a unique pair, in which case a particular indexing of user resource
pairs that is fixed at the beginning is used, and the user resource pair with
the highest index is declared the chosen pair in that iteration. Thus, the
value of discriminant $d_{i}^{p}$ in iteration $i$ is uniquely defined once
the problem is specified.

Next, we present the second main result of this paper, that gives an
approximation guarantee for the $\mathsf{GREEDY-M}$ algorithm as a function of
the discriminant and the curvature.

######  Theorem 3.4.

Using the $\mathsf{GREEDY-M}$ algorithm for Problem 3.1 guarantees:

$\frac{Z(G)}{Z(\Omega)}\geq\text{min}\left(1,\frac{1}{\underset{i}{\text{max}}\left\\{c_{u_{i}}+\frac{1}{d_{i}^{p}}\right\\}}\right),$

where $d_{i}^{p}$ is the discriminant and $c_{u_{i}}$ is the curvature of the
user chosen, in iteration $i$, respectively, for
$i=\\{1,2,\dots,|\mathcal{R}|\\}$.

Discussion: Compared to Theorem 2.8, $1/d_{i}^{p}$ replaces the $1$ in the
denominator, and thus larger the discriminant better is the approximation
guarantee, and which approaches $1$ as $d_{i}^{p}\rightarrow\infty$ for all
$i$. The guarantee obtained by Theorem 3.4 is strictly better than the bound
in Theorem 2.8 except for the following corner case: $(i)$ $d_{i}^{p}=1$ i.e.,
there is a tie in some iteration $i$ between multiple users for the best
resource, AND $(ii)$ every user who is part of the tie set has curvature equal
to $\underset{u\in\mathcal{U}}{\text{max }}c_{u}$ , in which case the bound
matches with the bound of Theorem 2.8,
$\frac{1}{1+\underset{u\in\mathcal{U}}{\text{max }}c_{u}}$.

######  Lemma 3.5.

The approximation guarantee obtained in Theorem 3.4 is tight.

######  Remark 3.6.

One question that is important to understand is the exact form of dependence
of the discriminant on the approximation guarantee for the greedy algorithm
that emerges from Theorem 3.4. Some intuition towards this end can be derived
as follows. Recall that the total number of resources $|\mathcal{R}|=n$.
Consider the instance where in the first $n-1$ iterations of the
$\mathsf{GREEDY-M}$ algorithm, resources $r_{1},\dots,r_{n-1}$ (indexed by
choices of $\mathsf{GREEDY-M}$ algorithm) have been allocated to users
$\hat{u}_{1},\dots,\hat{u}_{n-1}$ that matches the allocation for the same
resources by the optimal algorithm, i.e., $G^{n-1}=\Omega^{n-1}$ ($\Omega^{i}$
is the restriction of the optimal solution $\Omega$ to the items chosen in
$G^{i}$). Then we claim that the one remaining resource is also allocated to
the same user as done by the optimal algorithm, i.e., $G=\Omega$. The reason
is that the $\mathsf{GREEDY-M}$ algorithm in the last iteration allocates
$r_{n}$ to the user $u_{n}$ that maximizes
$Z(G^{n-1}\cup\\{(u_{n},r_{n})\\})-Z(G^{n-1})$. Since the optimal allocation
$\Omega$ maximizes $Z$, and $G^{n-1}=\Omega^{n-1}$, the $\mathsf{GREEDY-M}$
algorithm allocates $r_{n}$ to $\hat{u}_{n}$ (same as in the optimal
solution).

Extending this scenario backwards, let $G^{n-2}=\Omega^{n-2}$, then $G=G^{n}$
may not be equal to $\Omega$, since the $\mathsf{GREEDY-M}$ algorithm in the
final two iterations may make different choices compared to the optimal
algorithm. In particular, let the $\mathsf{GREEDY-M}$ algorithm allocate
resource $r_{n-1}$ to user $u_{n-1}$, while in the optimal algorithm $r_{n-1}$
is allocated to user ${\hat{u}}_{n-1}$, where $u_{n-1}\neq{\hat{u}}_{n-1}$.
Let the increment made by the $\mathsf{GREEDY-M}$ algorithm at iteration $n-1$
be $\rho_{n-1}$, while the increment made by the optimal algorithm in choosing
user ${\hat{u}}_{n-1}$ to allocate resource $r_{n-1}$ given its choices for
the $n-2$ resources be
$\rho^{o}_{n-1}=Z(\Omega^{n-2}\cup\\{({\hat{u}}_{n-1},r_{n-1})\\})-Z(\Omega^{n-2})$,
where $\Omega^{n-2}=G^{n-2}$. By definition of the $\mathsf{GREEDY-M}$
algorithm, $\rho^{o}_{n-1}\leq\frac{\rho_{n-1}}{d_{n-1}^{p}}$. Moving on to
the final iteration, let the $\mathsf{GREEDY-M}$ algorithm accrue zero
incremental valuation on allocating the last item (worst case) while the
incremental valuation for the optimal algorithm on allocation of item $r_{n}$
to user ${\hat{u}}_{n}$ be
$\rho^{o}_{n}=Z(\Omega^{n-1}\cup\\{({\hat{u}}_{n},r_{n})\\})-Z(\Omega^{n-1})$.
Note that $\rho^{o}_{n}\leq\rho_{n-1}$, since otherwise the
$\mathsf{GREEDY-M}$ algorithm would have allocated resource $r_{n}$ to user
${\hat{u}}_{n}$ in iteration $n-1$ itself.

Thus, the ratio of the $\mathsf{GREEDY-M}$ valuation to the optimal valuation
is:

$\displaystyle\frac{Z(G)}{Z(\Omega)}$
$\displaystyle=\frac{Z(G^{n-2})+\rho_{n-1}+0}{Z(\Omega^{n-2})+\rho^{o}_{n-1}+\rho^{o}_{n}}\geq\frac{Z(\Omega^{n-2})+\rho_{n-1}+0}{Z(\Omega^{n-2})+\frac{\rho_{n-1}}{d_{n-1}^{p}}+\rho_{n-1}}\geq\frac{1}{\frac{1}{d_{n-1}^{p}}+1}.$

Similar argument can be extended to earlier iterations of the
$\mathsf{GREEDY-M}$ algorithm, to conclude that its approximation guarantee
should depend on the discriminant $d_{i}^{p}$ as $1/d_{i}^{p}$.

In the next section, we consider the online version of the submodular
partition problem, and show that the same approximation guarantee as derived
in Theorem 3.4 (which now will be called competitive ratio) can be achieved by
a natural online version of the $\mathsf{GREEDY-M}$ algorithm.

##  4 Online Monotone Submodular Partition Problem

######  Problem 4.1.

This problem is identical to Problem 3.1, except that now, at each time index
$t=1,2,\dots,|\mathcal{R}|$, one resource
$j_{t}\in\mathcal{R},|\mathcal{R}|=n$ arrives, which must immediately be
allocated to exactly one of the users and the decision is irrevocable.

For an online problem, given the arrival sequence of resources $\sigma$ that
is a permutation over the order of arrival of $|\mathcal{R}|=n$ resources, the
competitive ratio of any online $A$ algorithm is defined as
${\mathsf{r}}_{A}=\min_{\sigma}\frac{Z(A(\sigma))}{Z(\Omega(\sigma))}$ and the
objective is to find an optimal online algorithm $A^{*}$ such that
${\mathsf{r}}_{A^{*}}=\max_{A}{\mathsf{r}}_{A}$. We propose a simple
modification of the $\mathsf{GREEDY-M}$ algorithm to make it online and then
bound its competitive ratio.

Algorithm 3 Modified Greedy Algorithm for the Online Monotone Submodular
Partition problem

1:procedure $\mathsf{GREEDY-ON}$

2: Initialize: $G^{0}=\phi,t=1$

3: while $t\leq|\mathcal{R}|=n$, on arrival of resource $j_{t}$ at time $t$ do

4: Allocate $j_{t}$ to user $u_{t}$ if

5: $u_{t}=\underset{u}{\text{
argmax}}\left\\{\rho_{j_{t}}^{u}(G^{t-1})\right\\}$

6: Tie: Allocate resource $j_{t}$ to user $u$ with least $c_{u}$

7: $G^{t}\leftarrow G^{t-1}\cup\\{(u_{t},j_{t})\\}$

8: $t\leftarrow t+1$

9: end while

10: Return $G=G^{n}$

11:end procedure

######  Remark 4.2.

$\mathsf{GREEDY-ON}$ is simpler than $\mathsf{GREEDY-M}$ since at each
iteration, the resource to be allocated is fixed, and the tie breaking rule
does not require the discriminant information.

To derive a lower bound on the competitive ratio of the $\mathsf{GREEDY-ON}$
algorithm, we need the following definition of the discriminant.

######  Definition 4.3.

For iteration $t$ of $\mathsf{GREEDY-ON}$, where resource $j_{t}$ arrives and
the current allocated set is $G^{t-1}$, the discriminant at iteration $t$,
$d^{o}_{t}$ (where o stands for online) is defined as:

$d^{o}_{t}=\frac{\rho_{j_{t}}^{u^{*}}(G^{t-1})}{\underset{u^{\prime}\neq
u^{*}}{\text{max }}\rho_{j_{t}}^{u^{\prime}}(G^{t-1})},\qquad\text{where,
}u^{*}=\underset{u}{\text{argmax}}\rho_{j_{t}}^{u}(G^{t-1}).$

The definition for discriminant in the online case only slightly differs from
the offline case, in that the resource being allocated at time $t$ is fixed as
$j_{t}$. Next, we present the final main result of the paper that provides a
guarantee on the competitive ratio of the $\mathsf{GREEDY-ON}$ algorithm.

######  Theorem 4.4.

For any arrival sequence $\sigma$ over the $|\mathcal{R}|=n$ resources, the
competitive ratio of the $\mathsf{GREEDY-ON}$ algorithm on Problem 4.1 is
bounded by

${\mathsf{r}}_{\mathsf{GREEDY-
ON}}\geq\text{min}\left(1,\frac{1}{\left(\underset{t}{\text{max
}}\left\\{\frac{1}{d^{o}_{t}}+c_{u_{t}}\right\\}\right)}\right),$

where $d^{o}_{t}$ is the discriminant and $c_{u_{t}}$ is the curvature of the
user chosen, in iteration $t$, respectively, for
$t\in\\{1,2,\dots,|\mathcal{R}|\\}$.

The natural online variant of the greedy algorithm $\mathsf{GREEDY}$ is known
to have a competitive ratio of at least $1/2$ (Fisher et al. (1978)), which
can be improved to $1/(1+c)$ using the curvature information (Conforti and
Cornuéjols (1984)). Theorem 4.4 shows that the competitive ratio can be
further improved if the discriminant values for the problem instance are
large.

##  5 Appendix

Recall that given a set $S$ associated with an ordering
$(s_{1},s_{2},\dots,s_{|S|})$, $S^{i}$ denotes the partial ordering
$(s_{1},s_{2},\dots,s_{i})$.

###  5.1 Intermediate Lemmas

######  Lemma 5.1 (Conforti and Cornuéjols (1984), Equation 2.1).

Given an instance of Problem 2.6, for all $A,B\in\mathcal{M}$, the following
is true:

$Z(A\cup B)\leq Z(A)+\sum_{i:b_{i}\in B\setminus A}\rho_{b_{i}}(A).$

######  Lemma 5.2 (Conforti and Cornuéjols (1984), Lemma 2.2).

Given feasible solutions $A,B$ to Problem 2.6, and an ordering
$A=(a_{1},a_{2},\dots,a_{K})$, an ordering for $B$ can be constructed as
$(b_{1},b_{2},\dots,b_{K})$ such that:

$A^{i-1}\cup\\{b_{i}\\}\in\mathcal{M},\quad\text{for }i=1,2,\dots,K.$

Furthermore, if for any $i$, $b_{i}\in A\cap B$, then $b_{i}=a_{i}$.

######  Remark 5.3.

The ordering for $B$ in Lemma 5.2 need not be unique. In a particular
iteration of the construction, there may exist more than one $b_{t}:b_{t}\cup
A^{t-1}\in\mathcal{M}$. The ordering exists irrespective of which $b_{t}$ is
chosen.

######  Corollary 5.4.

Given a feasible solution $A$ to Problem 2.6 with ordering
$A=(a_{1},a_{2},\dots,a_{K})$, if for some $i$, there exists a unique $a$ :
$A^{i-1}\cup\\{a\\}\in\mathcal{M}$ then, $a$ belongs to every feasible
solution to Problem 2.6.

######  Proof 5.5.

Order any feasible solution $B$ to Problem 2.6 as per Lemma 5.2. $A^{i-1}\cup
b_{i}\in\mathcal{M}\Rightarrow b_{i}=a$, and hence $a\in B$.

######  Lemma 5.6 (Conforti and Cornuéjols (1984), Lemma 2.2).

Given feasible solutions $A,B$ to Problem 2.6, and an ordering
$A=(a_{1},a_{2}\dots,a_{K})$, ordering $B$ as per Lemma 5.2 guarantees that:

$\displaystyle a_{i}\in A\setminus B$ $\displaystyle\Leftrightarrow b_{i}\in
B\setminus A.$

We introduce Lemma 5.7 below as an aid for the proof in Section 2.1 B.

######  Lemma 5.7.

Given feasible solutions $A,B$ to Problem 2.6, and an ordering
$A=(a_{1},a_{2}\dots,a_{K})$, ordering $B$ as per Lemma 5.2 also guarantees
for all $i$ that:

$\displaystyle\exists A_{c}\subset A\setminus A^{i-1},\ |A_{c}|=K-i,\text{
such that: }A^{i-1}\cup\\{b_{i}\\}\cup A_{c}\in\mathcal{M}.$

######  Proof 5.8.

The statement is trivially true for $b_{i}\in A$ ($\Rightarrow b_{i}=a_{i}$),
as we can choose $A_{c}=A\setminus(A^{i-1}\cup\\{b_{i}\\})$. For $b_{i}\not\in
A$, the claim is proved as follows by showing that we can find a sequence of
sets $\\{A^{t}_{c}\\}$ such that:

$\displaystyle A_{c}^{t}\subset A\setminus A^{i-1},\ |A_{c}|=t,\text{ such
that: }A^{i-1}\cup\\{b_{i}\\}\cup A^{t}_{c}\in\mathcal{M}.$ (6)

From the ordering of $B$ as per Lemma 5.2, (6) is trivial for $t=0$. For
$t>0$, we prove (6) by induction:

  1. 1.

Assume that (6) is true for some $t$:

$\Rightarrow\exists A_{c}^{t}\subset A\setminus A^{i-1},\ |A_{c}^{t}|=t,\text{
such that: }A^{i-1}\cup\\{b_{i}\\}\cup A_{c}^{t}\in\mathcal{M}.$

  2. 2.

Consider the sets $A^{i-1}\cup\\{b_{i}\\}\cup A_{c}^{t}$ and $A$. By the
augmentation property of matroids,

$\exists a\in A\setminus A^{i-1}\setminus A_{c}^{t}:A^{i-1}\cup\\{b_{i}\\}\cup
A_{c}^{t}\cup\\{a\\}\in\mathcal{M}.$ (7)

  3. 3.

We set $A^{t+1}_{c}\leftarrow A^{t}_{c}\cup\\{a\\}\ [\subset A\setminus
A^{i-1}]$. From (7), we have $A^{i-1}\cup b_{i}\cup
A^{t+1}_{c}\in\mathcal{M}$. Thus we have found an $A^{t+1}_{c}$, with
$|A^{t+1}_{c}|=t+1$ that satisfies (6). Plugging $t=K-i$ into (6):

$\displaystyle\Rightarrow\ \exists A_{c}\subset A\setminus A^{i-1},\
|A_{c}|=K-i,\text{ such that: }A^{i-1}\cup\\{b_{i}\\}\cup
A_{c}\in\mathcal{M}.$

######  Corollary 5.9.

(An extension to Corollary 5.4) For some feasible solution $A$ to Problem 2.6,
if there exists a unique $S:S\subseteq N\setminus A^{i-1},\ |S|=K-i+1$ such
that $A^{i-1}\cup S\in\mathcal{M}$, then $S$ is a part of every feasible
solution to Problem 2.6.

######  Proof 5.10.

The set $A\setminus A^{i-1}$ is a valid candidate for $S$, since it has
cardinality $K-i+1$ and $A^{i-1}\cup(A\setminus A^{i-1})=A\in\mathcal{M}$. By
the uniqueness of $S$, we conclude that $S=A\setminus
A^{i-1}=(a_{i},a_{i+1},\dots,a_{K})$. Consider any feasible solution $B$ to
Problem 2.6. Order $B$ as per Lemma 5.2. From Lemma 5.6, we have that:

$\displaystyle\exists A_{c}\subset A\setminus A^{i-1},\ |A_{c}|=K-i,\text{
such that:}A^{i-1}\cup\\{b_{i}\\}\cup A_{c}\in\mathcal{M}.$ (8)

Observe that: (a) $A_{c}\subset A\setminus A^{i-1}$, (b) $|A\setminus
A^{i-1}|=K-i+1$, and (c) $|A_{c}|=K-i$. Therefore $(A\setminus
A^{i-1})\setminus A_{c}$ is a singleton set containing some $a_{i_{1}}$, i.e.
$A\setminus A^{i-1}=A_{c}\cup\\{a_{i_{1}}\\}$. Also note that:

$\displaystyle A=A_{i-1}\cup(A\setminus A^{i-1})\in\mathcal{M},\ \Rightarrow\
A_{i-1}\cup(A_{c}\cup\\{a_{i_{1}}\\})\in\mathcal{M}.$ (9)

Because of the uniqueness of $S:|S|=K-i+1$ and $S\cup A^{i-1}\in\mathcal{M}$,
from (8) and (9), we have:

$a_{i_{1}}\in S\quad\text{ and }\quad b_{i}=a_{i_{1}}\Rightarrow b_{i}\in A.$
(10)

By the ordering of $B$ as per Lemma 5.2, $b_{i}\in A\Rightarrow b_{i}=a_{i}$.
Thus, from (10), we have $b_{i}=a_{i}$. We also have $b_{i}=a_{i_{1}}$, which
gives $a_{i}=a_{i_{1}}$.
We can also argue that since $S=A\setminus A^{i-1}$ is the only set with
$|S|=K-i+1$ such that $S\cup A^{i-1}\in\mathcal{M}$, $\forall t>i,\
S^{\prime}=A\setminus A^{t-1}$ is the only set with $|S^{\prime}|=K-t+1$ such
that $S^{\prime}\cup A^{t-1}\in\mathcal{M}$. Therefore, we can extend the
arguments made in (8), (9) and (10) to the set $A^{t-1}$ and conclude that
$b_{t}=a_{i_{t}}=a_{t}$. Thus,
$\\{b_{i},b_{i+1},\dots,b_{K}\\}=\\{a_{i},a_{i+1},\dots,a_{K}\\}=S\Rightarrow
S\subseteq B$.

######  Lemma 5.11.

There exists a unique $S:|S|=K-i+1$ such that $A^{i-1}\cup S\in\mathcal{M}$
iff there exist exactly $K-i+1$ choices for $a$ such that
$A^{i-1}\cup\\{a\\}\in\mathcal{M}$.

######  Proof 5.12.

The forward implication can be shown because there cannot be less than $K-i+1$
choices to add to $A^{i-1}$ (contradicts that $|S|=K-i+1$ as each element of
$S$ is a valid choice) and there cannot be more than $K-i+1$ choices, because
this contradicts the uniqueness of $S$ (using the augmentation property of
matroids).
The reverse implication also directly follows from the augmentation property
of matroids and from the rank of the matroid being equal to $K$.

######  Lemma 5.13 (Conforti and Cornuéjols (1984) Lemma 2.1).

Given an instance of Problem 2.6, for all $A,B\in\mathcal{M}$, with $A$
ordered as $(a_{1},a_{2},\dots,a_{|A|})$ and
$A^{t}=(a_{1},a_{2},\dots,a_{t})$, we have:

$Z(B)\leq\sum_{i:a_{i}\in A\cap B}\rho_{a_{i}}(A^{i-1})+c\sum_{i:a_{i}\in
A\setminus B}\rho_{a_{i}}(A^{i-1})+\sum_{b\in B\setminus A}\rho_{b}(A).$

######  Lemma 5.14.

Given an instance of Problem 3.1, for all $A,B\in\mathcal{M}^{p}$, with $A$
ordered as $(a_{1},a_{2},\dots,a_{|A|})$ and $A^{t}=(a_{1},a_{2},\dots,a_{t})$
we have:

$Z(B)\leq\sum_{\begin{subarray}{c}i:a_{i}\in A\setminus B\\\
a_{i}=(u_{i},r_{i})\end{subarray}}c_{u_{i}}\rho_{a_{i}}(A^{i-1})+\sum_{i:a_{i}\in
A\cap B}\rho_{a_{i}}(A^{i-1})+\sum_{b\in B\setminus A}\rho_{b}(A),$

where the curvature of $Z_{u_{i}}(S)$ is denoted by $c_{u_{i}}$.

######  Proof 5.15.

Following the proof of Lemma 5.13 [Conforti and Cornuéjols (1984) Lemma 2.1] ,
we can write:

$Z(B)\leq\sum_{i:a_{i}\in
A}\rho_{a_{i}}(A^{i-1})-\sum_{\begin{subarray}{c}i:a_{i}\in A\setminus B\\\
a_{i}=(u_{i},r_{i})\end{subarray}}\rho_{a_{i}}(B\cup A^{i-1})+\sum_{b\in
B\setminus A}\rho_{b}(A).$ (11)

From the definition of curvature of $Z_{u}(S)$ in (3), $\rho^{u}_{r}(B\cup
A^{i-1})\geq(1-c_{u})\rho_{r}^{u}(A^{i-1})$. Thus, (11) gives:

$\displaystyle Z(B)\leq\sum_{i:a_{i}\in
A}\rho_{a_{i}}(A^{i-1})-\sum_{\begin{subarray}{c}i:a_{i}\in A\setminus B\\\
a_{i}=(u_{i},r_{i})\end{subarray}}(1-c_{u_{i}})\rho_{a_{i}}(A^{i-1})+\sum_{b\in
B\setminus A}\rho_{b}(A).$ (12)

Rearranging terms in (12) and using $\underset{i:a_{i}\in
A}{\sum}\rho_{a_{i}}(A^{i-1})-\underset{i:a_{i}\in A\setminus
B}{\sum}\rho_{a_{i}}(A^{i-1})=\underset{i:a_{i}\in A\cap
B}{\sum}\rho_{a_{i}}(A^{i-1})$ gives:

$\displaystyle Z(B)\leq\sum_{i:a_{i}\in A\cap
B}\rho_{a_{i}}(A^{i-1})+\sum_{\begin{subarray}{c}i:a_{i}\in A\setminus B\\\
a_{i}=(u_{i},r_{i})\end{subarray}}c_{u_{i}}\rho_{a_{i}}(A^{i-1})+\sum_{b\in
B\setminus A}\rho_{b}(A).$

###  5.2 Proof of Theorem 2.10

For proving Theorem 2.10, we restate the following definitions.

  1. 1.

The solution output by the $\mathsf{GREEDY}$ algorithm is denoted by
$G=(g_{1},g_{2}\dots,\dots,g_{K})$ ordered in the sequence of elements chosen
by the $\mathsf{GREEDY}$ algorithm, where $K$ is the rank of the matroid.

  2. 2.

Partial solutions output by $\mathsf{GREEDY}$: $G^{t}$ as
$(g_{1},g_{2}\dots,g_{t})$.

  3. 3.

$\rho_{i}:=\underset{g_{i}}{\text{max }}\rho_{g_{i}}(G^{i-1}):g_{i}\cup
G^{i-1}\in\mathcal{M}\quad$ [$\mathsf{GREEDY}$ increment at iteration $i$].

  4. 4.

Recalling $N$ as the ground set in Problem 2.6, for any set $S\subseteq N$,

$S_{\bot}:=\\{j:j\in N\setminus S,\ j\cup S\in\mathcal{M}\\}.$

######  Lemma 5.16.

For any $g^{\prime}\in G^{i-1}_{\bot}\setminus G$, where $G$ is the output of
the $\mathsf{GREEDY}$ algorithm,

$\rho_{g^{\prime}}(G^{i-1})\leq\frac{\rho_{g_{i}}(G^{i-1})}{d_{i}}=\frac{\rho_{i}}{d_{i}}.$

######  Proof 5.17.

Since $g^{\prime}\in G^{i-1}_{\bot}\setminus G$, we can write:

$\rho_{g^{\prime}}(G^{i-1})\leq\text{max}\left\\{\rho_{j^{\prime}}(G^{i-1}):j^{\prime}\in
G^{i-1}_{\bot}\setminus G\right\\}.$ (13)

Observe that $G_{\bot}^{i-1}\setminus G\subseteq
G_{\bot}^{i-1}\setminus\\{g_{i}\\}$. Therefore, (13) gives:

$\rho_{g^{\prime}}(G^{i-1})\leq\text{max}\left\\{\rho_{j^{\prime}}(G^{i-1}):j^{\prime}\in
G^{i-1}_{\bot},\ j^{\prime}\neq g_{i}\right\\}.$ (14)

From the definition of $d_{i}$ in iteration $i$ (Definition 2.9), we have:

$\displaystyle
d_{i}=\frac{\rho_{g_{i}}(G^{i-1})}{\text{max}\left\\{\rho_{j^{\prime}}(G^{i-1}):j^{\prime}\in
G^{i-1}_{\bot},\ j^{\prime}\neq g_{i}\right\\}},$ which implies that
$\displaystyle\text{max}\left\\{\rho_{j^{\prime}}(G^{i-1}):j^{\prime}\in
G^{i-1}_{\bot},\ j^{\prime}\neq
g_{i}\right\\}=\frac{\rho_{g_{i}}(G^{i-1})}{d_{i}}.$

Together with (14), this completes the proof.

######  Lemma 5.18.

Given that $G$ is ordered as $(g_{1},g_{2},\dots,g_{K})$, ordering $\Omega$ as
$(\omega_{1},\omega_{2}\dots,\omega_{K})$ as per Lemma 5.2 guarantees for any
$1\leq t\leq K$:

$\rho_{\omega_{i}}(G^{t-1})\leq\begin{cases}\rho_{t}&\quad\forall i:i>t,\\\
\frac{\rho_{i}}{d_{i}}&\quad\forall i:1\leq i\leq t,\\\ \end{cases}\quad
i:\omega_{i}\in\Omega\setminus G.$

######  Proof 5.19.

Recall that $i_{0}$ is defined as $\min\\{i:|G_{\bot}^{i-1}|=K-i+1\\}$. Recall
from the discussion in Section 2.1 B, for $i\geq i_{0},\ g_{i}\in
G\cap\Omega$. Therefore the set $\\{i:\omega_{i}\in\Omega\setminus G\\}$ must
be a subset of $\\{i:i<i_{0}\\}$. As long as $i<i_{0}$, $d_{i}$ is always
defined (even if it is defined as $\infty$). Given that $G$ is ordered as
$(g_{1},g_{2},\dots,g_{K})$, order $\Omega$ as
$(\omega_{1},\omega_{2}\dots,\omega_{K})$ as in Lemma 5.2. Consider
$\rho_{\omega_{i}}(G^{t-1})$ for the $2$ cases:

  1. 1.

If $i>t$, by the ordering of $\Omega$, $G^{i-1}\cup\omega_{i}\in\mathcal{M}$.
Since, $G^{t-1}\cup\\{\omega_{i}\\}\subseteq G^{i-1}\cup\\{\omega_{i}\\}$, by
the independence system property of matroids
$G^{t-1}\cup\\{\omega_{i}\\}\in\mathcal{M}$. Thus, from the solution of
$\mathsf{GREEDY}$, $G$, we have:
$\rho_{\omega_{i}}(G^{t-1})\leq\rho_{g_{t}}(G^{t-1})=\rho_{t}$ for $i>t$.

  2. 2.

If $1\leq i\leq t$, by submodularity,
$\rho_{\omega_{i}}(G^{t-1})\leq\rho_{\omega_{i}}(G^{i-1})\quad-(a)$.
Some facts about $\omega_{i}$:

    1. $(b)$

$G^{i-1}\cup\\{\omega_{i}\\}\in\mathcal{M}\Rightarrow\omega_{i}\in
G^{i-1}_{\bot}$ [due to the ordering of $\Omega$],

    2. $(c)$

$\omega_{i}\in\Omega\setminus G\Rightarrow\omega_{i}\not\in G$.

    3. $(d)$

From $(b)$ and $(c)$, we have $\omega_{i}\in G^{i-1}_{\bot}\setminus G$. From
Lemma 5.16, we have $\rho_{\omega_{i}}(G^{i-1})\leq\frac{\rho_{i}}{d_{i}}$.

Together with $(a)$, for $1\leq i\leq t$, this gives:
$\rho_{\omega_{i}}(G^{t-1})\leq\frac{\rho_{i}}{d_{i}}.$

Now we are ready to prove Theorem 2.10.

######  Proof 5.20 (Proof of Theorem 2.10).

From Lemma 5.13 for $\Omega$ and $G$, we have:

$Z(\Omega)\leq c\sum_{i:g_{i}\in
G\setminus\Omega}\rho_{g_{i}}(G^{i-1})+\sum_{i:g_{i}\in
G\cap\Omega}\rho_{g_{i}}(G^{i-1})+\sum_{\omega\in\Omega\setminus
G}\rho_{\omega}(G).$

Following the ordering for $\Omega$ in Lemma 5.2, it follows that:

$Z(\Omega)\leq c\sum_{i:g_{i}\in G\setminus\Omega}\rho_{i}+\sum_{i:g_{i}\in
G\cap\Omega}\rho_{i}+\sum_{i:\omega_{i}\in\Omega\setminus
G}\rho_{i}\frac{\rho_{\omega_{i}}(G^{i-1})}{\rho_{i}}.$ (15)

From Lemma 5.6, under the ordering of $\Omega$ from Lemma 5.2,

$\displaystyle g_{i}\in
G\setminus\Omega\Leftrightarrow\omega_{i}\in\Omega\setminus G.$ (16)

We define

$d_{i}^{\prime}:=\frac{\rho_{i}}{\rho_{\omega_{i}}(G^{i-1})}.$ (17)

For $i:\omega_{i}\in\Omega\setminus G$, we can lower bound $d_{i}^{\prime}$ by
$d_{i}$. This is a consequence of Lemma 5.18, with $t=i$:

$\displaystyle\rho_{\omega_{i}}(G^{i-1})$
$\displaystyle\leq\frac{\rho_{i}}{d_{i}}$ $\displaystyle\Rightarrow\ d_{i}$
$\displaystyle\leq d_{i}^{\prime}$ (18)

Consider the last term in the RHS of (15):

$\displaystyle\sum_{i:\omega_{i}\in\Omega\setminus
G}\rho_{i}\frac{\rho_{\omega_{i}}(G^{i-1})}{\rho_{i}}$
$\displaystyle\overset{(i)}{=}\sum_{i:\omega_{i}\in\Omega\setminus
G}\frac{\rho_{i}}{d_{i}^{\prime}}\overset{(ii)}{=}\sum_{i:g_{i}\in
G\setminus\Omega}\frac{\rho_{i}}{d_{i}^{\prime}},$ (19)

where $(i)$ follows from the definition of $d_{i}^{\prime}$ in (17) and $(ii)$
follows from the assertion in (16). Substituting (19) back in (15), we have:

$\displaystyle Z(\Omega)$ $\displaystyle\leq c\sum_{i:g_{i}\in
G\setminus\Omega}\rho_{i}+\sum_{i:g_{i}\in
G\cap\Omega}\rho_{i}+\sum_{i:g_{i}\in
G\setminus\Omega}\frac{\rho_{i}}{d_{i}^{\prime}},$
$\displaystyle=\sum_{i:g_{i}\in
G\setminus\Omega}\left(c+\frac{1}{d_{i}^{\prime}}\right)\rho_{i}+\sum_{i:g_{i}\in
G\cap\Omega}\rho_{i},$ $\displaystyle\leq\left(c+\underset{i:g_{i}\in
G\setminus\Omega}{\text{max }}\
\frac{1}{d_{i}^{\prime}}\right)\sum_{i:g_{i}\in
G\setminus\Omega}\rho_{i}+\sum_{i:g_{i}\in G\cap\Omega}\rho_{i}.$ (20)

We reduce (5.20) as below:

$\displaystyle Z(\Omega)\leq\text{max}\left(1,\ c+\underset{i:g_{i}\in
G\setminus\Omega}{\text{max }}\
\frac{1}{d_{i}^{\prime}}\right)\sum_{i:g_{i}\in G}\rho_{i}=\text{max}\left(1,\
c+\underset{i:g_{i}\in G\setminus\Omega}{\text{max }}\
\frac{1}{d_{i}^{\prime}}\right)Z(G).$ (21)

Since we cannot compute $G\setminus\Omega$ in polynomial time, we relax the
domain over which $\frac{1}{d_{i}^{\prime}}$ is maximized. Recall from the
discussion in Section 2.1 B: $\forall i\geq i_{0},\ g_{i}\in G\cap\Omega$.
Therefore $\\{i:i\geq i_{0}\\}\subseteq\\{i:g_{i}\in G\cap\Omega\\}$, which
means that $\\{i:i<i_{0}\\}\supseteq\\{i:g_{i}\in G\setminus\Omega\\}$.
Therefore, in the term involving maximization of $\frac{1}{d_{i}^{\prime}}$
over $G\setminus\Omega$ in (5.20), we replace $G\setminus\Omega$ by the larger
set $\\{i:i<i_{0}\\}$ and perform the maximization over this set. This gives:

$\displaystyle Z(\Omega)\leq\text{max}\left(1,\ c+\underset{i<i_{0}}{\text{max
}}\ \frac{1}{d_{i}^{\prime}}\right)Z(G).$ (22)

From (18), lower bounding $d_{i}^{\prime}$ by $d_{i}$ in (22) gives:

$\displaystyle Z(\Omega)\leq\text{max}\left(1,\ c+\underset{i<i_{0}}{\text{max
}}\ \frac{1}{d_{i}}\right)Z(G)$ $\displaystyle\leq\text{max}\left(1,\ c+\
\frac{1}{\underset{i<i_{0}}{\text{min }}d_{i}}\right)Z(G),$
$\displaystyle\overset{(i)}{=}\text{max}\left(1,c+\frac{1}{d_{\min}}\right)Z(G),$

where $(i)$ follows from the definition of $d_{\min}$ (Definition 2.9). Hence
we get,

$\frac{Z(G)}{Z(\Omega)}\geq\frac{1}{\text{max}\left(1,\frac{1}{d_{\min}}+c\right)}=\text{min}\left(1,\frac{1}{c+\frac{1}{d_{\min}}}\right)=\text{min}\left(1,\frac{1}{\left(c+\underset{i<i_{0}}{\text{max
}}\ \frac{1}{d_{i}}\right)}\right).$

###  5.3 Proof of Theorem 3.4

Before proving Theorem 3.4, we restate the following definitions. In the
following, we denote the increment made by the $\mathsf{GREEDY-M}$ algorithm
in iteration $i$ by choosing the user-resource pair $g_{i}=(u_{i},r_{i})$, as
$\rho_{i}=\rho^{u_{i}}_{r_{i}}(G^{i-1}):=\rho_{g_{i}}(G^{i-1})$ and the set
chosen by the $\mathsf{GREEDY-M}$ algorithm as $G$.

######  Lemma 5.21.

With $|\mathcal{R}|=n$, let the solution generated by the $\mathsf{GREEDY-M}$
algorithm $G$ be ordered as $(g_{1},g_{2},\dots,g_{n})$ (in order of resources
allocated by the $\mathsf{GREEDY-M}$ algorithm), where $g_{i}=(u_{i},r_{i})$
and the partial greedy solutions $G^{t}=(g_{1},g_{2},\dots,g_{t})$ [with
$G^{0}=\phi$]. Ordering $\Omega$ as
$(\omega_{1},\omega_{2},\dots,\omega_{n})$, where
$\omega_{i}=(\hat{u}_{i},r_{i})$ [arranged in the same order of resources
$r_{i}^{{\text{'}s}}$ allocated by the $\mathsf{GREEDY-M}$ algorithm] gives:

$\rho^{\hat{u}_{i}}_{r_{i}}(G^{t})\leq\begin{cases}\rho_{t+1}&\forall
i:i>t,\\\ \frac{\rho_{i}}{d_{i}^{p}}\quad&\forall i:i\leq t,\end{cases}\qquad
i:(\hat{u}_{i},r_{i})\in\Omega\setminus G,$

where $\rho_{r_{i}}^{\hat{u}_{i}}(G^{t})$ follows the same notation as in (5)
and is equal to $Z(G^{t}\cup\\{(\hat{u}_{i},r_{i})\\})-Z(G^{t})$.

######  Proof 5.22.

Consider an index $i:(\hat{u}_{i},r_{i})\in\Omega\setminus
G\subseteq\Omega\setminus G^{t}$. If no such $i$ exists, we are guaranteed
that $\Omega\setminus G=\phi\Rightarrow\Omega=G$. Otherwise, for such $i$,
consider $\rho_{r_{i}}^{\hat{u}_{i}}(G^{t})$:

  1. 1.

For $i>t$, $G^{t}\cup(\hat{u}_{i},r_{i})\in\mathcal{M}^{p}$, since the
resource $r_{i}$ has not yet been allocated in $G^{t}$. Thus for $i>t$,
$\rho_{t+1}\geq\rho_{r_{i}}^{\hat{u}_{i}}(G^{t})$.

  2. 2.

$\mathsf{GREEDY-M}$ has allocated the resources
$\\{r_{1},r_{2},\dots,r_{t}\\}$ to $G^{t}$ until iteration $t$, implying that
$(u_{i},r_{i})\in G^{t}$ for any $i\leq t$. Therefore, defining
$S_{t,i}=G^{t}\cup\\{(\hat{u}_{i},r_{i})\\}$, we have that for $i\leq t$,
$S_{t,i}\not\in\mathcal{M}^{p}$. This is because
$\\{(u_{i},r_{i}),(\hat{u}_{i},r_{i})\\}\subset S_{t,i}$, and hence it fails
to satisfy $|S_{t,i}\cap\mathcal{V}_{r_{i}}|\leq 1$ \- a condition every set
in $\mathcal{M}^{p}$ must satisfy as defined in Problem 3.1. However,

    1. (a)

$G^{i-1}\cup\\{(\hat{u}_{i},r_{i})\\}\in\mathcal{M}^{p}$ (since $r_{i}$ has
not yet been allocated in $G^{i-1}$), and

    2. (b)

$\hat{u}_{i}\neq u_{i}$. This is because:

$\displaystyle(\hat{u}_{i},r_{i})$ $\displaystyle\in\Omega\setminus G,$
$\displaystyle\Rightarrow(\hat{u}_{i},r_{i})$ $\displaystyle\not\in
G=\\{(u_{1},r_{1}),(u_{2},r_{2}),\dots,(u_{n},r_{n})\\},$
$\displaystyle\Rightarrow(\hat{u}_{i},r_{i})$
$\displaystyle\neq(u_{i},r_{i}).\qquad[\text{Since }(u_{i},r_{i})\text{ is an
element of }G]$

Thus, from (a) and (b) we have that $(\hat{u}_{i},r_{i})$ is a valid choice
for $\mathsf{GREEDY-M}$ in the $i^{th}$ iteration, but it involves allocating
$r_{i}$ to a user different from the greedy choice in that iteration.
Therefore, we conclude that $\hat{u}_{i}$ is at most the second best user
choice for $r_{i}$ in iteration $i$ and we get the inequality $(i)$ that for
$i\leq t$

$\displaystyle\rho_{r_{i}}^{\hat{u}_{i}}(G^{i-1})\overset{(i)}{\leq}\underset{u\neq
u_{i}}{\text{max
}}\rho^{u}_{r_{i}}(G^{i-1})\overset{(ii)}{\leq}\frac{1}{d_{i}^{p}}\rho_{r_{i}}^{u_{i}}(G^{i-1})=\frac{\rho_{i}}{d_{i}^{p}}.$
(23)

where $(ii)$ follows from the definition of the discriminant at iteration $i$.
It is important to note that $(i)$ is conditionally true only if
$(\hat{u}_{i},r_{i})\in\Omega\setminus G$. Since $r_{i}$ has not yet been
allocated in $G^{i-1}$, we are assured that
$G^{i-1}\cup\\{(\hat{u}_{i},r_{i})\\}\in\mathcal{M}^{p}$. Thus, from (23) we
have:

$\text{for }i\leq t,\ \
\rho^{\hat{u}_{i}}_{r_{i}}(G^{t})\overset{(iii)}{\leq}\rho_{r_{i}}^{\hat{u}_{i}}(G^{i-1})\leq\frac{\rho_{i}}{d_{i}^{p}}$

where $(iii)$ follows from submodularity.

####  5.3.1 Proof of Theorem 3.4

######  Proof 5.23.

From Lemma 5.14, we have:

$Z(\Omega)\leq\sum_{\begin{subarray}{c}i:g_{i}\in G\setminus\Omega\\\
g_{i}=(u_{i},r_{i})\end{subarray}}c_{u_{i}}\rho_{g_{i}}(G^{i-1})+\sum_{i:g_{i}\in
G\cap\Omega}\rho_{g_{i}}(G^{i-1})+\sum_{\omega\in\Omega\setminus
G}\rho_{\omega}(G).$ (24)

Let $G$ be ordered as $(g_{1},g_{2},\dots,g_{n})$, where
$g_{i}=(u_{i},r_{i})$. Recall that,

$g_{i}=\underset{u,r}{\text{ argmax}}\left\\{\rho_{r}^{u}(G^{i-1}):\
r\in\mathcal{R}(G^{i-1}_{\bot})\right\\}.$

We order $\Omega$ as $(\omega_{1},\omega_{2},\dots,\omega_{n})$, where
$\omega_{i}=(\hat{u}_{i},r_{i})$ [in the same order of resources
$r_{i}^{{\text{'}s}}$ allocated by $\mathsf{GREEDY-M}$]. Consider the last
summation in the RHS of (24):

$\displaystyle\sum_{\omega\in\Omega\setminus G}\rho_{\omega}(G)=$
$\displaystyle\sum_{i:\omega_{i}\in\Omega\setminus
G}\rho_{\omega_{i}}(G)\overset{(i)}{\leq}\sum_{i:\omega_{i}\in\Omega\setminus
G}\rho_{\omega_{i}}(G^{i-1})\overset{(ii)}{\leq}\sum_{i:\omega_{i}\in\Omega\setminus
G}\frac{\rho_{i}}{d_{i}^{p}},$ (25)

where $(i)$ follows from submodularity of $Z(S)$ and $(ii)$ follows from Lemma
5.21. Putting together (24) and (25), we have:

$\displaystyle Z(\Omega)$
$\displaystyle\leq\sum_{\begin{subarray}{c}i:g_{i}\in G\setminus\Omega\\\
g_{i}=(u_{i},r_{i})\end{subarray}}c_{u_{i}}\rho_{i}+\sum_{i:g_{i}\in
G\cap\Omega}\rho_{i}+\sum_{i:\omega_{i}\in\Omega\setminus
G}\frac{\rho_{i}}{d_{i}^{p}}.$ (26)

In order to combine terms in the first and the third summations of (26), we
give an argument to show that if
$\omega_{i}=(\hat{u}_{i},r_{i})\in\Omega\setminus G$ then
$g_{i}=(u_{i},r_{i})\in G\setminus\Omega$ for the same index $i$. Consider $i$
such that $\omega_{i}=(\hat{u}_{i},r_{i})\in\Omega\setminus G$. If no such $i$
exists, $\Omega\setminus G=\phi\Rightarrow\Omega=G$, and hence the statement
of Theorem 3.4 holds true trivially. Otherwise, it follows that:

  1. (a)

$\omega_{i}\not\in G$.

  2. (b)

Since $g_{i}=(u_{i},r_{i})\in G$, for such $i$, it follows from (a) that
$\omega_{i}\neq g_{i}$. This means that $\hat{u}_{i}\neq u_{i}$.

  3. (c)

From (b) it follows that if $\hat{u}_{i}\neq u_{i}$, then
$(u_{i},r_{i})\not\in\Omega$ (since $\Omega\in\mathcal{M}^{p}$, it cannot
contain both $(\hat{u}_{i},r_{i})$ and $(u_{i},r_{i})$). Hence $g_{i}\in
G\setminus\Omega$.

Since $|G\setminus\Omega|=|\Omega\setminus G|$ (which is a consequence of
$|G|=|\Omega|=n$), we combine the first and the third summations in (26) to
give:

$\displaystyle Z(\Omega)\leq\sum_{\begin{subarray}{c}i:g_{i}\in
G\setminus\Omega\\\
g_{i}=(u_{i},r_{i})\end{subarray}}\left(c_{u_{i}}+\frac{1}{d_{i}^{p}}\right)\rho_{i}+\sum_{i:g_{i}\in
G\cap\Omega}\rho_{i}.$ (27)

Since, $1\leq\text{max}\left(1,\frac{1}{d_{i}^{p}}+c_{u_{i}}\right),\text{ and
}\left(c_{u_{i}}+\frac{1}{d_{i}^{p}}\right)\leq\text{max}\left(1,\frac{1}{d_{i}^{p}}+c_{u_{i}}\right)$
from (27), we have:

$\displaystyle Z(\Omega)$
$\displaystyle\leq\sum_{i=1}^{n}\text{max}\left(1,\frac{1}{d_{i}^{p}}+c_{u_{i}}\right)\rho_{i}\leq\underset{i}{\text{max}}\left(\text{max}\left(1,\frac{1}{d_{i}^{p}}+c_{u_{i}}\right)\right)Z(G).$

Thus,
$\frac{Z(\Omega)}{Z(G)}\leq\frac{1}{\underset{i}{\text{max}}\left(\text{max}\left(1,\frac{1}{d_{i}^{p}}+c_{u_{i}}\right)\right)}=\text{min}\left(1,\frac{1}{\underset{i}{\text{max}}\left(c_{u_{i}}+\frac{1}{d_{i}^{p}}\right)}\right)$.

###  5.4 Proof of Theorem 4.4 \- Online Partition Problem

Before proceeding ahead, we restate the following notation:

  1. 1.

User chosen by the $\mathsf{GREEDY-ON}$ algorithm at time $t$: $u_{t}$.

  2. 2.

The $\mathsf{GREEDY-ON}$ solution,
$G=\\{(u_{1},j_{1}),(u_{2},j_{2}),\dots,(u_{n},j_{n})\\}=\\{g_{1},g_{2},\dots,g_{n}\\}$
and optimal solution,
$\Omega=\\{(\hat{u}_{1},j_{1}),(\hat{u}_{2},j_{2}),\dots,(\hat{u}_{n},j_{n})\\}=\\{\omega_{1},\omega_{2},\dots,\omega_{n}\\}$.

  3. 3.

Partition matroid $\mathcal{M}^{p}$ as defined in Problem $2$. Then,
$\sum_{u\in\mathcal{U}}Z_{u}(S_{u})\ \equiv\ Z(S):S\in\mathcal{M}^{p}$.

  4. 4.

The set of all user-resource pairs involving the resource $j_{t}$:
$U^{t}=\\{(u,j_{t}):\forall u\in\mathcal{U}\\}$

  5. 5.

$\Psi^{t}=\Omega\cap U^{t}$ and $\xi^{t}=G\cap U^{t}$.

######  Remark 5.24.

$|\Psi^{t}\cap\xi^{t}|\leq 1$. This is because at every time $t$ only a single
resource is allocated ($|\Psi^{t}|=|\xi^{t}|=1$).

######  Lemma 5.25.

For $t_{1}\neq t_{2}$,
$\Psi^{t_{1}}\cap\Psi^{t_{2}}=\xi^{t_{1}}\cap\xi^{t_{2}}=\Psi^{t_{1}}\cap\xi^{t_{2}}=\phi$.

######  Proof 5.26.

It follows from definition that $\Psi^{t}\subseteq U^{t}$ and
$\xi^{t}\subseteq U^{t}$. Since, $U^{t_{1}}\cap U^{t_{2}}=\phi$, the result
follows.

######  Lemma 5.27.

$G\setminus\Omega$ and $\Omega\setminus G$ can be decomposed as:

$\displaystyle G\setminus\Omega=\bigcup_{t=1}^{n}\xi^{t}\setminus\Psi^{t},\
\text{ and }\ \Omega\setminus G=\bigcup_{t=1}^{n}\Psi^{t}\setminus\xi^{t}.$

######  Proof 5.28.

From the definition of $\Psi^{t}$ and $\xi^{t}$, it follows that:
$G=\bigcup_{t=1}^{n}\xi^{t},\ \text{ and }\ \Omega=\bigcup_{t=1}^{n}\Psi^{t}.$
The proof concludes using Lemma 5.25.

####  5.4.1 Proof of Theorem 4.4

######  Proof 5.29.

From Lemma 5.1, we have:

$\displaystyle Z(\Omega\cup G)$ $\displaystyle\leq
Z(G)+\sum_{q\in\Omega\setminus G}\rho_{q}(G),$
$\displaystyle\overset{(i)}{=}Z(G)+\sum_{t=1}^{n}\sum_{q\in\Psi^{t}\setminus\xi^{t}}\rho_{q}(G),$
$\displaystyle\overset{(ii)}{\leq}Z(G)+\sum_{t=1}^{n}\sum_{q\in\Psi^{t}\setminus\xi^{t}}\rho_{q}(G^{t-1}),$
(28)

where $(i)$ follows from Lemma 5.27 and Remark 5.25, and $(ii)$ follows from
submodularity. Expanding the LHS of (5.29), and again applying Lemma 5.27 and
Remark 5.25 gives:

$\displaystyle Z(\Omega\cup
G)=Z(\Omega)+\sum_{t=1}^{n}\sum_{q\in\xi^{t}\setminus\Psi^{t}}\rho_{q}(\Omega\cup
G^{t-1}).$ (29)

Combining (5.29) and (29):

$\displaystyle Z(\Omega)$ $\displaystyle\leq
Z(G)+\sum_{t=1}^{n}\sum_{q\in\Psi^{t}\setminus\xi^{t}}\rho_{q}(G^{t-1})-\sum_{t=1}^{n}\sum_{q\in\xi^{t}\setminus\Psi^{t}}\rho_{q}(\Omega\cap
G^{t-1}).$ (30)

From the definition of curvature, for any $q=(u_{t},j_{t})$:

$\rho_{q}(\Omega\cap G^{t-1})\geq(1-c_{u_{t}})\rho_{q}(G^{t-1}).$ (31)

Expanding $Z(G)$ in (30) and combining it together with (31), we have:

$\displaystyle Z(\Omega)$
$\displaystyle\leq\sum_{t=1}^{n}\sum_{q\in\xi^{t}}\rho_{q}(G^{t-1})+\sum_{t=1}^{n}\sum_{q\in\Psi^{t}\setminus\xi^{t}}\rho_{q}(G^{t-1})-\sum_{t=1}^{n}\sum_{\begin{subarray}{c}q\in\xi^{t}\setminus\Psi^{t}\\\
q=(u_{t},j_{t})\end{subarray}}(1-c_{u_{t}})\rho_{q}(G^{t-1}).$ (32)

Cancelling identical terms in the first and last summations in (32), we get:

$\displaystyle Z(\Omega)$
$\displaystyle\leq\sum_{t=1}^{n}\sum_{q\in\xi^{t}\cap\Psi^{t}}\rho_{q}(G^{t-1})+\sum_{t=1}^{n}\sum_{q\in\Psi^{t}\setminus\xi^{t}}\rho_{q}(G^{t-1})+\sum_{t=1}^{n}\sum_{\begin{subarray}{c}q\in\xi^{t}\setminus\Psi^{t}\\\
q=(u_{t},j_{t})\end{subarray}}c_{u_{t}}.\rho_{q}(G^{t-1}).$ (33)

Consider the middle summation of (33). Recall that $\hat{u}_{t}$ is the user
that the resource $j_{t}$ is allocated to in the optimal solution $\Omega$.
For $q=(\hat{u}_{t},j_{t})\in\Psi^{t}\setminus\xi^{t}$:

  1. 1.

$(\hat{u}_{t},j_{t})\not\in\xi^{t}$. But, $\xi_{t}$ contains $(u_{t},j_{t})$
(since it is equal to $G\cap U^{t}$), and hence we conclude that
$\hat{u}_{t}\neq u_{t}$.

  2. 2.

We also note that $G^{t-1}\cup(\gamma_{n-1},j_{t})\in\mathcal{M}^{p}$,
$\forall\gamma_{n-1}\in\mathcal{U}$ (since $j_{t}$ has not been allocated in
$G^{t-1}$), and hence $G^{t-1}\cup(\hat{u}_{t},j_{t})\in\mathcal{M}^{p}$.

Therefore, from the definition of discriminant (Definition 4.3) for the online
case, we can write for $q\in\Psi^{t}\setminus\xi^{t}$:

$\rho_{q}(G^{t-1})\leq\frac{\rho_{j_{t}}^{u_{t}}(G^{t-1})}{d_{t}^{o}}.$ (34)

Recalling, $\rho_{t}:=\rho_{j_{t}}^{u_{t}}(G^{t-1})$ and putting together (33)
with (34), we have:

$\displaystyle Z(\Omega)$
$\displaystyle\leq\sum_{t=1}^{n}\left(\sum_{q\in\xi^{t}\cap\Psi^{t}}\rho_{t}+\sum_{q\in\Psi^{t}\setminus\xi^{t}}\frac{\rho_{t}}{d_{t}^{o}}+\sum_{\begin{subarray}{c}q\in\xi^{t}\setminus\Psi^{t}\\\
q=(u_{t},j_{t})\end{subarray}}c_{u_{t}}.\rho_{t}\right).$ (35)

Recalling that $\Psi^{t}=\\{(\hat{u}_{t},j_{t})\\}$ and
$\xi^{t}=\\{(u_{t},j_{t})\\}$. If $\xi^{t}\setminus\Psi^{t}\neq\phi$, then it
is clear that $\Psi^{t}\setminus\xi^{t}\neq\phi$. Thus, we combine together
the last two summations in (35) to get

$\displaystyle Z(\Omega)$
$\displaystyle\leq\sum_{t=1}^{n}\sum_{q\in\xi^{t}\cap\Psi^{t}}\rho_{t}+\sum_{t=1}^{n}\sum_{\begin{subarray}{c}q\in\xi^{t}\setminus\Psi^{t}\\\
q=(u_{t},j_{t})\end{subarray}}\left(c_{u_{t}}+\frac{1}{d_{t}^{o}}\right)\rho_{t}.$

Bringing $c_{u_{t}}+\frac{1}{d_{t}^{o}}$ out of the summation by defining
$\Lambda=\underset{t}{\text{max}}\left(c_{u_{t}}+\frac{1}{d_{t}^{o}}\right)$,
we get

$\displaystyle
Z(\Omega)\leq\sum_{t=1}^{n}\sum_{q\in\xi^{t}\cap\Psi^{t}}\rho_{t}+\Lambda\sum_{t=1}^{n}\sum_{\begin{subarray}{c}q\in\xi^{t}\setminus\Psi^{t}\\\
q=(u_{t},j_{t})\end{subarray}}\rho_{t}.$ (36)

We can further reduce the RHS of (36) to:

$\displaystyle Z(\Omega)$
$\displaystyle\leq\text{max}\left(1,\Lambda\right)\sum_{t=1}^{n}\sum_{q\in\xi^{t}\cap\Psi^{t}}\rho_{t}+\text{max}\left(1,\Lambda\right)\sum_{t=1}^{n}\sum_{\begin{subarray}{c}q\in\xi^{t}\setminus\Psi^{t}\\\
q=(u_{t},j_{t})\end{subarray}}\rho_{t},$
$\displaystyle=\text{max}\left(1,\Lambda\right)\sum_{t=1}^{n}\sum_{q\in\xi^{t}}\rho_{t}\
=\ \text{max}\left(1,\Lambda\right)Z(G).$

This gives the required bound:

$\displaystyle\frac{Z(G)}{Z(\Omega)}\geq\text{min}\left(1,\frac{1}{\Lambda}\right)=\text{min}\left(1,\frac{1}{\underset{t}{\text{max}}\left(c_{u_{t}}+\frac{1}{d_{t}^{o}}\right)}\right).$

###  5.5 Proof of Lemma 3.5 \- Tight example for the bound in Theorem 3.4:

  1. 1.

Set of users, $\mathcal{U}=\\{u_{1},u_{2}\\}$, and set of resources,
$\mathcal{R}=\\{r_{1},r_{2},\dots,r_{n}\\}$.

  2. 2.

For some $0\leq c\leq 1$, $1\leq d\leq\frac{1}{1-c}$, and some small
$\epsilon>0$, let $d_{-}=d-\epsilon$.

  3. 3.

Define the monotone submodular valuation functions, $Z_{u_{1}}(S)$ and
$Z_{u_{2}}(S)$:
$r_{1}$ $r_{2}$ $r_{3}$ $r_{4}$ $\cdots$ $u_{1}$ $d$ $r_{1}\not\in S_{u_{1}}$
$r_{1}\in S_{u_{1}}$ $d_{-}$ $d_{-}(1-c)$ $d^{3}(1-c)^{2}$ $r_{3}\not\in
S_{u_{1}}$ $r_{3}\in S_{u_{1}}$ $d_{-}^{3}(1-c)^{2}$ $d_{-}^{3}(1-c)^{3}$
$\cdots$ $u_{2}$ $1$ $d^{2}(1-c)$ $r_{2}\not\in S_{u_{2}}$ $r_{2}\in
S_{u_{2}}$ $d_{-}^{2}(1-c)$ $d_{-}^{2}(1-c)^{2}$ $d^{4}(1-c)^{3}$ $\cdots$

Subsequently,

|  $r_{i}:i$ is odd |  $r_{i}:i$ is even
---|---|---
$u_{1}$ | $d^{i}(1-c)^{i-1}$ |  | $r_{i-1}\not\in S_{u_{1}}$ | $r_{i-1}\in S_{u_{1}}$
---|---
$d_{-}^{i-1}(1-c)^{i-2}$ | $d_{-}^{i-1}(1-c)^{i-1}$
$u_{2}$ |  | $r_{i-1}\not\in S_{u_{2}}$ | $r_{i-1}\in S_{u_{2}}$
---|---
$d_{-}^{i-1}(1-c)^{i-2}$ | $d_{-}^{i-1}(1-c)^{i-1}$
$d^{i}(1-c)^{i-1}$

  4. 4.

$Z_{u_{1}}(S)$ and $Z_{u_{2}}(S)$ both have curvature $c$. This is discussed
in more detail in Appendix 5.5.1.

  5. 5.

$\mathsf{GREEDY-M}$ solution:

    1. (a)

$(u_{1},r_{1})$ has the maximum initial valuation. Thus, the
$\mathsf{GREEDY-M}$ algorithm allocates $r_{1}$ to $u_{1}$. The discriminant
for the $1^{st}$ iteration is $d_{1}=d$.

    2. (b)

$(u_{2},r_{2})$ has the maximum greedy increment for the $2^{nd}$ iteration.
The discriminant for the $2^{nd}$ iteration is $d_{2}=\frac{d^{2}}{d_{-}}$.

    3. (c)

Continuing as above, it follows that the greedy solution generated by
$\mathsf{GREEDY-M}$ is
$G=\\{(u_{1},r_{1}),(u_{2},r_{2}),(u_{1},r_{3}),(u_{2},r_{4}),\dots,\\}$.
Hence,

$\displaystyle Z(G)$
$\displaystyle=d(1+d(1-c)+(d(1-c))^{2}+\dots+(d(1-c))^{n-1})$
$\displaystyle=\frac{d(1-(d(1-c))^{n})}{1-d(1-c)}.$ (37)

    4. $\bullet$

In this problem, $c_{u_{1}}=c_{u_{2}}=c$ as shown in Appendix 5.5.1, meaning
that $\forall i,\ c_{u_{i}}=c$. For iteration $1$, the discriminant,
$d_{1}=d$. Step $2$ onwards, the discriminant $d_{i}=\frac{d^{2}}{d_{-}}$.
Since $d_{-}<d$, for this problem, from Theorem $5$:

$\frac{Z(G)}{Z(\Omega)}\geq\frac{1}{c+\frac{1}{d}}.$

  6. 6.

The optimal solution is
$\Omega=\\{(u_{2},r_{1}),(u_{1},r_{2}),(u_{2},r_{3}),(u_{1},r_{4}),\dots,\\}$,
shown in Appendix 5.5.2. Hence,

$\displaystyle Z(\Omega)$
$\displaystyle=1+d_{-}(1+d_{-}(1-c)+(d_{-}(1-c))^{2}+\dots+(d_{-}(1-c))^{n-1})$
$\displaystyle=1+\frac{d_{-}(1-(d_{-}(1-c))^{n})}{1-d_{-}(1-c)}.$ (38)

  7. 7.

Thus, from (37) and (38),

$\lim_{\begin{subarray}{c}\epsilon\to 0,\\\
n\to\infty\end{subarray}}\frac{Z(G)}{Z(\Omega)}=\lim_{\epsilon\to
0}\frac{d}{1-d_{-}(1-c)+d_{-}}=\lim_{\epsilon\to
0}\frac{d}{1+d_{-}c}=\frac{1}{\frac{1}{d}+c}.$

Thus, from (37) it follows that the guarantee for Theorem 3.4 is met.

####  5.5.1 Curvatures of $Z_{u_{1}}(S)$ and $Z_{u_{2}}(S)$:

The definition of curvature for $Z_{u_{1}}(S)$ and $Z_{u_{2}}(S)$ is:

$\text{for }i=1,2\quad c_{u_{i}}=1-\underset{S,r\in S^{*}}{\text{min
}}\frac{\rho_{r}^{u_{i}}(S)}{\rho_{r}^{u_{i}}(\phi)},\qquad\text{where
}S^{*}=\\{r:r\in\mathcal{R}\setminus S,\ \rho_{r}^{u_{i}}(\phi)>0\\}.$ (39)

For any $r\in\mathcal{R}$, the minimizer for $S$ in (39) is
$\mathcal{R}\setminus\\{r\\}$. This is because for some $r$, any valid choice
for $S$ cannot contain $r$ (since $r\in S^{*}$), and hence
$S\subseteq\mathcal{R}\setminus\\{r_{i}\\}$. Submodularity of $Z_{u_{1}}(S)$
guarantees that the increment upon adding $r$ to any such $S$ would be more
than that for $\mathcal{R}\setminus\\{r_{i}\\}$. Considering
$S=\mathcal{R}\setminus\\{r\\}$ itself is a valid choice, since
$S^{*}=\\{r\\}$, which proves that it is the minimizer for $S$.

For $u_{1}$, the expression for curvature is evaluated below:

$\frac{\rho_{r}^{u_{1}}(S)}{\rho_{r}^{u_{1}}(\phi)}=\begin{cases}\frac{d_{-}^{i-1}(1-c)^{i-1}}{d_{-}^{i-1}(1-c)^{i-2}}=1-c&r_{i}:i\text{
is even, and }S=\mathcal{R}\setminus\\{r_{i}\\},\\\
\frac{d^{i}(1-c)^{i-1}+d_{-}^{i-1}(1-c)^{i}-d_{-}^{i-1}(1-c)^{i-1}}{d^{i}(1-c)^{i-2}}\overset{(\dagger)}{>}1-c\quad&r_{i}:i\text{
is odd, and }S=\mathcal{R}\setminus\\{r_{i}\\},\end{cases}$ (40)

where $(\dagger)$ follows from the fact that $d_{-}<d$. It follows from (40)
and the definition of curvature in (39) that:

$c_{u_{1}}=1-(1-c)=c.$

A similar analysis for $u_{2}$ gives:

$\frac{\rho_{r}^{u_{2}}(S)}{\rho_{r}^{u_{2}}(\phi)}=\begin{cases}\frac{d_{-}^{i-1}(1-c)^{i-1}}{d_{-}^{i-1}(1-c)^{i-2}}=1-c&r_{i}:i\text{
is odd, and }S=\mathcal{R}\setminus\\{r_{i}\\},\\\
\frac{d^{i}(1-c)^{i-1}+d_{-}^{i-1}(1-c)^{i}-d_{-}^{i-1}(1-c)^{i-1}}{d^{i}(1-c)^{i-2}}>1-c\quad&r_{i}:i\text{
is even, and }S=\mathcal{R}\setminus\\{r_{i}\\}.\end{cases}$ (41)

Together with the definition of curvature in (39), this once again gives:

$c_{u_{2}}=1-(1-c)=c.$

####  5.5.2 Optimal solution for tight example in Theorem 3.4

The optimal solution for the tight example in Appendix 5.5 is
$\Omega=\\{(u_{2},r_{1}),(u_{1},r_{2}),(u_{2},r_{3}),(u_{1},r_{4}),\dots,\\}$
The reasoning behind this is presented below. From the structure of the
problem instance in Appendix 5.5, it follows that any valid solution
$\Omega^{\prime}$ can be equivalently represented as an ordered set of users
$(\alpha_{1},\alpha_{2},\dots,\alpha_{K})$, where $\alpha_{i}$ is either
$u_{1}$ or $u_{2}$ and represents the user to which $r_{i}$ is allocated, and
$\Omega^{\prime}$ is ordered as per $r_{1},\dots,r_{K}$, the order in which
$\mathsf{GREEDY-M}$ allocates resources. Any such $\Omega^{\prime}$ can be
converted to $\Omega$ by replacing every $\alpha_{i}:i$ is odd, by $u_{2}$ and
every $\alpha_{i}:i$ is even, by $u_{1}$. We sequentially update
$\Omega^{\prime}$ in the following manner until is not further possible:

  1. 1.

Consider $i$ such that $\alpha_{i}=\alpha_{i+1}=u_{1}$. From the function
valuations of $Z_{u_{1}}(S)$ and $Z_{u_{2}}(S)$ and since
$d\leq\frac{1}{1-c}$, it follows that for odd $i$, replacing $\alpha_{i}$ by
$u_{2}$ and for even $i$, replacing $\alpha_{i+1}$ by $u_{2}$ would increase
the valuation of $\Omega^{\prime}$. $\Omega^{\prime}$ is updated by performing
this exchange.

  2. 2.

Consider all $i$ such that $\alpha_{i}=\alpha_{i+1}=u_{2}$. From the function
valuations of $Z_{u_{1}}(S)$ and $Z_{u_{2}}(S)$ and since
$d\leq\frac{1}{1-c}$, it follows that for odd $i$, replacing $\alpha_{i+1}$ by
$u_{1}$ and for even $i$, replacing $\alpha_{i}$ by $u_{1}$ would increase the
valuation of $\Omega^{\prime}$. $\Omega^{\prime}$ is updated by performing
this exchange.

$\Omega^{\prime}$ is recursively updated as per iterations $1$ and $2$, with
each iteration increasing the valuation of $\Omega^{\prime}$ until there no
longer exists $i$ such that $\alpha_{i}=\alpha_{i+1}=u_{1}$ or
$\alpha_{i}=\alpha_{i+1}=u_{2}$. We claim that unless $\Omega^{\prime}$ is
initially $\\{u_{1},u_{2},u_{1},\dots,\\}$, after the final update
$\Omega^{\prime}$ must be equal to $\\{u_{2},u_{1},u_{2},\dots,\\}$. This is
because, as per the update rule, for all $i$, $\alpha_{i}$ and $\alpha_{i+1}$
cannot both be $u_{1}$ or $u_{2}$. Hence the final $\Omega^{\prime}$ is either
$\\{u_{2},u_{1},u_{2},\dots,\\}$ or $\\{u_{1},u_{2},u_{1},\dots,\\}$. If even
a single update has taken place, the update rule ensures that either some
$\alpha_{i}:i$ is odd is replaced by $u_{2}$ (or) some $\alpha_{i}:i$ is even
is replaced by $u_{1}$. This eliminates $\\{u_{1},u_{2},u_{1},\dots,\\}$ as
the final outcome. If no update has taken place, it follows that
$\Omega^{\prime}=\\{u_{1},u_{2},u_{1},\dots,\\}$ since it is the only set
other than $\\{u_{2},u_{1},u_{2},\dots,\\}$ that cannot be updated.

Thus, we can transform any solution $\Omega^{\prime}$ to $\Omega$ with a net
increase in valuation. This proves that $\Omega$ is the optimal solution.

###  5.6 Proof of Lemma 2.11 \- Tight example for the bound in Theorem 2.10

We show that using the $\mathsf{GREEDY}$ algorithm on the following problem
instance, matches the bound in (22):

  1. 1.

Consider the ground set $N$ as:
$\\{\nu_{1},\nu_{2},\dots,\nu_{K},\epsilon_{1},\epsilon_{2},\dots,\epsilon_{K}\\}$.

  2. 2.

Define the matroid as $(N,\mathcal{M})$, where $\mathcal{M}=\\{S:S\subseteq
N,S\cap\\{\nu_{i},\epsilon_{i}\\}\leq 1,\ \forall i\\}$ [only one among
$\nu_{i}$ and $\epsilon_{i}$ can be members of any set $S\in\mathcal{M}$].

  3. 3.

For some $d\geq 1$, define the valuation function as:

$\begin{split}Z(S)=d\sum_{I_{1}}(d(1-c))^{i-1}+\sum_{i\in
I_{2}}(d(1-c))^{i-1}\\}+d\sum_{\ \in I_{3}}(d(1-c))^{i-2}.\end{split}$

where $I_{1}=\\{i:\epsilon_{i}\in S\\}$, $I_{2}=\\{i:\nu_{i}\in S\text{ and
}\left[\epsilon_{i-1}\in S\text{ or }i=1\right]\\}$ and $I_{3}=\\{i:\nu_{i}\in
S\text{ and }\epsilon_{i-1}\not\in S\\}$.

The idea behind such a valuation function is that at every iteration $i$ of
the $\mathsf{GREEDY}$ algorithm, there is a tie between $\epsilon_{i}$ and
$\nu_{i+1}$ (as seen below), and $\mathsf{GREEDY}$ picks arbitrarily among the
two, say $\epsilon_{i}$ which is the sub-optimal choice.

  4. 4.

$Z(S)$ can also be represented in the form of its marginal increments as:

$\displaystyle\rho_{\nu_{i}}(S)=\begin{cases}d(d(1-c))^{i-2},&\epsilon_{i-1}\not\in
S,\\\ (d(1-c))^{i-1},&\epsilon_{i-1}\in S\text{ or }i=1,\end{cases}$
$\displaystyle\rho_{\epsilon_{i}}(S)=\begin{cases}d(d(1-c))^{i-1},&\nu_{i+1}\not\in
S,\\\ (d(1-c))^{i},&\nu_{i+1}\in S.\end{cases}$ (42)

  5. 5.

Before proceeding with the analysis for the greedy algorithm, observe that the
optimal solution is $\Omega=\\{\nu_{1},\nu_{2},\dots,\nu_{K}\\}$.

This is shown below by showing a sequence of iterations by which any valid
solution $\Omega^{\prime}$ can be converted to $\Omega$ with an increase in
valuation in every iteration. From the structure of the matroid
$(N,\mathcal{M})$, it follows that any valid solution $\Omega^{\prime}$ can be
ordered as $(\alpha_{1},\alpha_{2},\dots,\alpha_{K})$ (where $\alpha_{i}$ is
either $\nu_{i}$ or $\epsilon_{i}$), and can be converted to $\Omega$ by
replacing every $\epsilon_{i}\in\Omega^{\prime}$ by $\nu_{i}$. Noting this
point, a sequence of iterations converting any such $\Omega^{\prime}$ to
$\Omega$ with an increase in valuation in every iteration is:

    1. i.

If $\epsilon_{K}\in\Omega^{\prime}$, update $\Omega^{\prime}$ by replacing
$\epsilon_{K}$ by $\nu_{K}$. From the incremental valuations defined in (42),
it follows that such an exchange provides a non-negative increment
$\sigma_{1}$ to the valuation of $\Omega^{\prime}$. In case
$\nu_{K}\in\Omega^{\prime}$, set $\sigma_{1}=0$.

    2. ii.

Starting from $K$, iterate over $i$ in the reverse order sequentially updating
$\Omega^{\prime}$; for every $i$ such that $\epsilon_{i}$ precedes
$\nu_{i+1}$, update $\Omega^{\prime}$ by replacing $\epsilon_{i}$ by
$\nu_{i}$. In case $\nu_{i}\in\Omega^{\prime}$, no update is made to
$\Omega^{\prime}$ in that iteration. From the function increments in (42), in
every iteration, this iteration gives a positive increment $\sigma_{i}$
($\sigma_{i}$ is set as $0$ in case there is no exchange).

    3. $\bullet$

In the $i^{th}$ iteration of this process, $\Omega^{\prime}$ would be
$(\alpha_{1},\alpha_{2},\dots,\alpha_{K-i},\nu_{K-i+1},\dots,\nu_{K})$.

Thus, the above series of steps sequentially convert any $\Omega^{\prime}$ to
$\Omega$, and give:

$Z(\Omega)=Z(\Omega^{\prime})+\sum_{i=1}^{K}\sigma_{i},\qquad\forall
i,\sigma_{i}\geq 0.$

This shows for every valid solution $\Omega^{\prime}$, $Z(\Omega)\geq
Z(\Omega^{\prime}).$ Thus, we conclude that $\Omega$ is the optimal solution,
having valuation:

$Z(\Omega)=1+d\sum_{i=1}^{K}(d(1-c))^{i-1}.$ (43)

  6. 6.

In order to compute $d_{i}^{\prime}$ for the bound in (22), we need to compute
the ordering of $\Omega$ as per Lemma 5.2. If the greedy solution is chosen in
the order $G=(\alpha_{i_{1}},\alpha_{i_{2}},\dots,\alpha_{i_{K}})$ (where
$\alpha_{i_{t}}$ takes either $\epsilon_{i_{t}}$ or $\nu_{i_{t}}$), an
ordering for $\Omega$ as per Lemma 5.2 is just
$(\nu_{i_{1}},\nu_{i_{2}},\dots,\nu_{i_{K}})$. It follows from the structure
of the matroid, that for all $t$, the set
$S_{t}=G^{t-1}\cup\\{\nu_{t}\\}=\\{\alpha_{i_{1}},\alpha_{i_{2}}\dots,\alpha_{i_{t-1}}\\}\cup\\{\nu_{i_{t}}\\}$
does not contain both $\nu_{i_{j}}$ and $\epsilon_{i_{j}}$ (since
$\alpha_{i_{j}}$ is uniquely either $\epsilon_{i_{j}}$ or $\nu_{i_{j}}$) for
all $j$. Hence $\forall t,\ S_{t}\in\mathcal{M}$. This shows that
$(\nu_{i_{1}},\nu_{i_{2}},\dots,\nu_{i_{K}})$ is a valid ordering as per Lemma
5.2.

  7. 7.

We now compute the $\mathsf{GREEDY}$ solution:

    1. (a)

iteration $\mathbf{1}$: $\epsilon_{1}$ and $\nu_{2}$ are tied ($d_{1}^{g}=1$),
both giving increment, $\rho_{\epsilon_{1}}(\phi)=\rho_{\nu_{2}}(\phi)=d$.
Assume that the $\mathsf{GREEDY}$ algorithm arbitrarily picks $\epsilon_{1}$
between the two. We have:

$d_{1}^{\prime}\overset{(i)}{=}\frac{\rho_{\epsilon_{1}}(\phi)}{\rho_{\nu_{1}}(\phi)}\overset{(ii)}{=}\frac{d}{1}=d,$

where $(i)$ follows from the definition of $d_{i}^{\prime}$ in (17), and from
the ordering of $\Omega$ established previously in point 6, and $(ii)$ follows
from the incremental valuations defined in (42).

    2. (b)

iterations $\mathbf{i=2,\dots,K}$: $\epsilon_{i}$ and $\nu_{i+1}$ are tied
($d_{i}=1$), both giving increment
$\rho_{\epsilon_{i}}(G^{i-1})=\rho_{\nu_{i+1}}(G^{i-1})=d(d(1-c))^{i-1}$.
Assume that the greedy algorithm picks $\epsilon_{i}$ arbitrarily, which
gives:

$d_{i}^{\prime}\overset{(iii)}{=}\frac{\rho_{\epsilon_{i}}(G^{i-1})}{\rho_{\nu_{i}}(G^{i-1})}\overset{(iv)}{=}\frac{d(d(1-c))^{i-1}}{d(1-c)^{i-1}}=d,$
(44)

where $(iii)$ once again follow from the definition of $d_{i}^{\prime}$ in
(17), and from the ordering of $\Omega$ established in point 6, and $(iv)$
follows from the function increments in (42).

Thus, the greedy solution is
$G=\\{\epsilon_{1},\epsilon_{2},\dots,\epsilon_{K}\\}$, and has valuation
$Z(G)=d\sum_{i=1}^{K}(d(1-c))^{i-1}.$
Therefore, with the optimal valuation in (43) we have:

$\displaystyle\lim_{K\to\infty}\frac{Z(G)}{Z(\Omega)}$
$\displaystyle=\lim_{K\to\infty}\frac{d\sum_{i=1}^{K}(d(1-c))^{i-1}}{1+d\sum_{i=1}^{K}(d(1-c))^{i-1}},$
$\displaystyle=\frac{d}{1-d(1-c)+d},$ $\displaystyle=\frac{1}{\frac{1}{d}+c}.$
(45)

  8. 8.

To compute the bound in (22), we need to compute $\underset{i<i_{0}}{\text{max
}}\frac{1}{d_{i}^{\prime}}$. Observe that in the $i^{th}$ stage of the greedy
algorithm, we have $2(K-i+1)>K-i+1$ choices,
$\\{\nu_{i},\nu_{i+1},\dots,\nu_{K},\epsilon_{i},\epsilon_{i+1},\dots,\epsilon_{K}\\}$.
Therefore $i_{0}=K+1$. Putting this together with (44), we have:

$\underset{i<i_{0}}{\text{max }}\frac{1}{d_{i}^{\prime}}=\underset{i\leq
K}{\text{max }}\frac{1}{d_{i}^{\prime}}=\frac{1}{d}.$

  9. 9.

Therefore the bound in (22) reduces to:

$\frac{Z(G)}{Z(\Omega)}\geq\frac{1}{\frac{1}{d}+c},$

which matches with the limit ($K\rightarrow\infty$) in (45).

## References

  * (1)
  * Calinescu et al. (2011) Gruia Calinescu, Chandra Chekuri, Martin Pál, and Jan Vondrák. 2011.  Maximizing a Monotone Submodular Function Subject to a Matroid Constraint.  SIAM J. Comput. 40, 6 (Dec. 2011), 1740–1766.  https://doi.org/10.1137/080733991
  * Conforti and Cornuéjols (1984) Michele Conforti and Gérard Cornuéjols. 1984.  Submodular set functions, matroids and the greedy algorithm: Tight worst-case bounds and some generalizations of the Rado-Edmonds theorem.  Discrete Applied Mathematics 7, 3 (1984), 251 – 274.  https://doi.org/10.1016/0166-218X(84)90003-9
  * Edmonds (1971) Jack Edmonds. 1971\.  Matroids and the greedy algorithm.  Mathematical programming 1, 1 (1971), 127–136.
  * Feige (1998) Uriel Feige. 1998\.  A threshold of ln n for approximating set cover.  Journal of the ACM (JACM) 45, 4 (1998), 634–652.
  * Feige et al. (2011) Uriel Feige, Vahab S Mirrokni, and Jan Vondrak. 2011\.  Maximizing non-monotone submodular functions.  SIAM J. Comput. 40, 4 (2011), 1133–1153.
  * Feige and Vondrak (2006) Uriel Feige and Jan Vondrak. 2006.  Approximation algorithms for allocation problems: Improving the factor of 1-1/e. In Foundations of Computer Science, 2006. FOCS’06. 47th Annual IEEE Symposium on. IEEE, 667–676.
  * Fisher et al. (1978) M. L. Fisher, G. L. Nemhauser, and L. A. Wolsey. 1978\.  An analysis of approximations for maximizing submodular set functions—II.  Springer Berlin Heidelberg, Berlin, Heidelberg, 73–87.  https://doi.org/10.1007/BFb0121195
  * Fleischer et al. (2006) Lisa Fleischer, Michel X Goemans, Vahab S Mirrokni, and Maxim Sviridenko. 2006.  Tight approximation algorithms for maximum general assignment problems. In Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm. Society for Industrial and Applied Mathematics, 611–620.
  * Goundan and Schulz (2007) Pranava R Goundan and Andreas S Schulz. 2007.  Revisiting the greedy approach to submodular set function maximization.  Optimization online (2007), 1–25.
  * Korula et al. (2015) Nitish Korula, Vahab S. Mirrokni, and Morteza Zadimoghaddam. 2015\.  Online Submodular Welfare Maximization: Greedy Beats 1/2 in Random Order. In STOC. 889–898.  http://dl.acm.org/ft_gateway.cfm?ftid=1588585&id=2746626
  * Nemhauser and Wolsey (1978) George L Nemhauser and Laurence A Wolsey. 1978.  Best algorithms for approximating the maximum of a submodular set function.  Mathematics of operations research 3, 3 (1978), 177–188.
  * Soma and Yoshida (2017) Tasuku Soma and Yuichi Yoshida. 2017.  A New Approximation Guarantee for Monotone Submodular Function Maximization via Discrete Convexity.  CoRR abs/1709.02910 (2017).  arXiv:1709.02910 http://arxiv.org/abs/1709.02910
  * Sviridenko and Ward (2013) Maxim Sviridenko and Justin Ward. 2013.  Tight Bounds for Submodular and Supermodular Optimization with Bounded Curvature.  CoRR abs/1311.4728 (2013).  arXiv:1311.4728 http://arxiv.org/abs/1311.4728
  * Thekumparampil et al. (2016) Kiran Thekumparampil, Andrew Thangaraj, and Rahul Vaze. 2016\.  Combinatorial resource allocation using submodularity of waterfilling.  IEEE Transactions on Wireless Communications 15, 1 (2016), 206–216.
  * Vondrák (2008) Jan Vondrák. 2008\.  Optimal approximation for the submodular welfare problem in the value oracle model. In Proceedings of the fortieth annual ACM symposium on Theory of computing. ACM, 67–74.