# Multilinear extension of $k$-submodular functions

Baoxiang Wang<EMAIL_ADDRESS>The Chinese University of Hong Kong,
Shenzhen. Huanjian Zhou<EMAIL_ADDRESS>Department of Complexity
Science and Engineering, Graduate School of Frontier Sciences, The University
of Tokyo.

###### Abstract

A $k$-submodular function is a function that given $k$ disjoint subsets
outputs a value that is submodular in every orthant. In this paper, we provide
a new framework for $k$-submodular maximization problems, by relaxing the
optimization to the continuous space with the multilinear extension of
$k$-submodular functions and a variant of pipage rounding that recovers the
discrete solution. The multilinear extension introduces new techniques to
analyze and optimize $k$-submodular functions.

When the function is monotone, we propose almost $\frac{1}{2}$-approximation
algorithms for unconstrained maximization and maximization under total size
and knapsack constraints. For unconstrained monotone and non-monotone
maximization, we propose an algorithm that is almost as good as any
combinatorial algorithm based on Iwata, Tanigawa, and Yoshida’s meta-framework
($\frac{k}{2k-1}$-approximation for the monotone case and
$\frac{k^{2}+1}{2k^{2}+1}$-approximation for the non-monotone case).

##  1 Introduction

A submodular set function is a set function $f\colon 2^{V}\to\mathbb{R}$ such
that for any $A,B\subseteq V$,

$f(A)+f(B)\geq f(A\cup B)+f(A\cap B)\,.$

A $k$-submodular function takes subsets of $k$ disjoint sets
$V_{1},\dots,V_{k}$ as input, and outputs a value that is submodular in every
orthant. Equivalently, $f\colon(k+1)^{V}\to\mathbb{R}$ is $k$-submodular if
and only if for every $k$-tuples $S=(S_{1},\dots,S_{k})$ and
$T=(T_{1},\dots,T_{k})$ of pairwise disjoint subsets of $V$,

$f(S)+f(T)\geq f(S\sqcap T)+f(S\sqcup T)\,,$

where

$S\sqcap T=(S_{1}\cap T_{1},\dots,S_{k}\cap T_{k})$

and

$S\sqcup T=((S_{1}\cup T_{1})\setminus\bigcup_{i\neq 1}(S_{i}\cup
T_{i}),\dots,(S_{k}\cup T_{k})\setminus\bigcup_{i\neq k}(S_{i}\cup T_{i}))\,.$

Submodular maximization takes an important role in many problems in
combinatorial optimization and machine learning, such as document
summarization, sensor placement, influence maximization, and feature selection
[LB10, KLG+08, KKT03, KLQ95]. Submodular maximization methods can be roughly
categorized into two types. The first type of approaches is combinatorial, and
is based on techniques such as local search and greedy rules [NWF78, NW78,
Svi04, LSV10, FNSW11, FMV11]. The other type finds a continuous extension of
the discrete problem and takes a 2-step approach. An optimization algorithm
finds an optimum in the continuous space and then a rounding algorithm
recovers the discrete solution from the fractional one.

Extension-based maximization methods are mostly based on the multilinear
extension, which extends a submodular functions from the binary cube
$\\{0,1\\}^{n}$ to the continuous cube $[0,1]^{n}$, where $n=|V|$. While the
function agrees with the extension on the binary cube, the extension $F$ can
map an arbitrary point $\mathbf{x}\in[0,1]^{n}$ as

$F(\mathbf{x})=\sum_{S\subseteq V}f(S)\prod_{i\in S}x_{i}\prod_{i\in
V\setminus S}(1-x_{i})\,.$

State-of-the-art results in a variety of settings have been obtained through
the multilinear extension [KST09, CCPV11, EN16, BF19].

Several techniques could round the fractional solution $\mathbf{x}$ to the
discrete space while approximately preserving the value of $F(\mathbf{x})$.
Pipage rounding, which was first introduced by Ageev and Sviridenko [AS04] for
bipartite matching polytopes, is adopted for submodular maximization methods.
These include the deterministic pipage rounding and its randomized variants
for matroid constraint [CCPV07, CCPV11], randomized rounding coupled with
alteration for knapsack constraints [KST09, KST13, LMNS10, BKNS12], and swap
rounding which achieves similar results in some settings such as the matroid
constraint [CVZ10]. The contention resolution scheme is a generic approach
that is feasible for general settings such as the intersection of two matroids
[CVZ14].

$k$-submodular maximization shares similar application areas as submodular
maximization, and has been investigated by many combinatorial algorithms. For
unconstrained $k$-submodular maximization, Ward and Živný [WŽ16] propose a
$\max\\{1/3,1/(1+a)\\}$-approximation algorithm, where
$a=\max\\{1,\sqrt{(k-1)/4}\\}$. Iwata, Tanigawa, and Yoshida [ITY16] propose a
discrete meta-framework which adds one element at a time according to some
probability distribution. They achieve a $\frac{k}{2k-1}$-approximation
guarantee for the monotone case and an $\frac{1}{2}$-approximation guarantee
for the non-monotone case, which is improved later by Oshima [Osh21] to
$\frac{k^{2}+1}{2k^{2}+1}$, $k\geq 3$ and $\frac{\sqrt{17}-3}{2}$, $k=3$ for
the non-monotone case.

For constrained $k$-submodular maximization, an $\frac{1}{2}$-approximation
algorithm for the total size constraint and an $\frac{1}{3}$-approximation
algorithm for the individual size constraint are proposed by Ohsaka and
Yoshida [OY15]. Sakaue designs an $\frac{1}{2}$-approximation algorithm for
maximizing monotone $k$-submodular functions under a matroid constraint
[Sak17]. Shi, Gu, and Wu design an
$(1-\frac{1}{e^{\frac{1}{k}}}-\epsilon)$-approximation algorithm for
maximizing non-monotone $k$-submodular functions with total size and
individual size difference constraints and an
$(1-\frac{1}{e}-\epsilon)$-approximation algorithm for maximizing non-monotone
$k$-submodular functions with individual size constraints [SGW20]. Tang, Wang,
and Chan propose an $(\frac{1}{2}-\frac{1}{2e})$-approximation algorithm for
maximizing $k$-submodular functions under a knapsack constraint [TWC21].

For both unconstrained $k$-submodular maximization and constrained
$k$-submodular maximization, a similar argument based on continuous extension
and rounding as analog to submodular functions is not available.

###  1.1 Our contributions

In this paper, we propose the multilinear extension
$F\colon\mathcal{P}\to\mathbb{R}$ for a $k$-submodular function
$f\colon(k+1)^{V}\to\mathbb{R}$ as

$F(\mathbf{x})=\sum\limits_{S_{1}\uplus\dots\uplus S_{k}=S\subseteq
V}f(S_{1},\dots,S_{k})\Big{(}\prod\limits_{j\in[k]}\prod\limits_{i\in
S_{j}}x_{i,j}\Big{)}\prod\limits_{i\in V\setminus
S}\Big{(}1-\sum\limits_{j=1}^{k}x_{i,j}\Big{)}\,,$ (1)

where $n=|V|$, “$\uplus$” denotes disjoint union, the polytope
$\mathcal{P}=\\{\mathbf{x}\in[0,1]^{n\times
k}:\sum\limits_{j=1}^{k}x_{i,j}\leq 1,~{}\forall i\in[n]\\}$ is the domain of
$F$ and $\mathbf{x}=(x_{1,1},\dots,x_{1,k},\dots,x_{n,1},\dots,x_{n,k})$ is a
vector in $[0,1]^{n\times k}$.

Armed with the multilinear extension for $k$-submodular functions, we design
optimization algorithms that maximize $F$ without constraints and with
constraints that are transformed from the knapsack and total size constraints
in the discrete space. We also modify randomized pipage rounding and swap
rounding and extend their results from submodular maximization to
$k$-submodular maximization. The multilinear extension and the techniques for
maximization and rounding are general enough to be applied to a wider range of
problems. Table 1 summarizes our results and illustrates the comparisons with
state-of-the-art algorithms.

| Previous work | Our work
---|---|---
Unconstrained (monotone) |  $\frac{k}{2k-1}$[ITY16] | $\frac{k}{2k-1}-\epsilon$
Unconstrained (non-monotone) |  $\frac{k^{2}+1}{2k^{2}+1}$[Osh21] | $\frac{k^{2}+1}{2k^{2}+1}-\epsilon$
Knapsack constraint (monotone) |  $\frac{1}{2}-\frac{1}{2e}$[TWC21] | $\frac{1}{2}-\epsilon$
Total size constraint (monotone) |  $\frac{1}{2}$ [OY15] | $\frac{1}{2}-\epsilon$
Table 1: Overview of our results.

###  1.2 Preliminaries

In order to understand the relation between $k$-submodular function
maximization and other maximization problems, it is useful to understand the
characteristic properties of $k$-submodular functions, namely the orthant
submodularity and the pairwise monotonicity. To present them, define a partial
order $\leq$ on $(k+1)^{V}$ such that for $\mathbf{x}=(X_{1},\dots,X_{k})$ and
$\mathbf{y}=(Y_{1},\dots,Y_{k})$ in $(k+1)^{V}$, if $X_{i}\subseteq Y_{i}$ for
every $i$ with $1\leq i\leq k$ then $\mathbf{x}\leq\mathbf{y}$. Also, define

$\Delta_{e,i}f(\mathbf{x})=f(X_{1},\dots,X_{i-1},X_{i}\cup\\{e\\},X_{i+1},\dots,X_{k})-f(X_{1},\dots,X_{k})$

for $\mathbf{x}\in(k+1)^{V},e\not\in\bigcup^{k}_{j=1}X_{j}$, and $i\in[k]$,
which represents the marginal gain when adding $e$ to the $i$-th component of
$\mathbf{x}$. Then it is straightforward to notice that the $k$-submodularity
implies the orthant submodularity

$\Delta_{e,i}f(\mathbf{x})\geq\Delta_{e,i}f(\mathbf{y}),~{}\forall\mathbf{x},\mathbf{y}\in(k+1)^{V}\mbox{
with }\mathbf{x}\leq\mathbf{y},e\not\in\bigcup^{k}_{j=1}Y_{j},i\in[k]\,,$

and the pairwise monotonicity

$\Delta_{e,i}f(\mathbf{x})+\Delta_{e,j}f(\mathbf{x})\geq
0,~{}\forall\mathbf{x}\in(k+1)^{V}\mbox{ with
}e\not\in\bigcup^{k}_{l=1}X_{l},\mbox{ and }i,j\in[k],i\neq j\,.$ (2)

Ward and Živný show that the converse is also true. Functions that are
submodular in every orthant and pairwise monotone must be $k$-submodular.
Similar results are proved for bisubmodular functions earlier by Ando,
Fujishige, and Naitoh [AFN96].

######  Lemma 1 (Ward and Živný [WŽ16]).

A function $f\colon(k+1)^{V}\to\mathbb{R}$ is $k$-submodular if and only if
$f$ is submodular in every orthant and is pairwise monotone.

When $f$ is assumed to be non-negative, a key fact for $k$-submodular
maximization pointed out by Iwata, Tanigawa, and Yoshida is that the maximum
of $f$ is achieved on the boundary.

######  Lemma 2 (Iwata, Tanigawa, and Yoshida [ITY16]).

For any non-negative $k$-submodular function $f:(k+1)^{V}\to\mathbb{R}^{+}$,
there exists a partition of $V$ that attains the maximum value of $f$.

These properties are repeatedly used in our maximization algorithms under a
variety of settings.

##  2 Multilinear extension of $k$-submodular functions

###  2.1 Intuition for the multilinear extension

The multilinear extension of $k$-submodular functions is inspired by the
multilinear extension of submodular functions. The multilinear extension $F$
of submodular functions $f$ can be defined by setting
$F(\mathbf{x})=\mathbb{E}[f(\hat{\mathbf{x}})]$ where $\hat{\mathbf{x}}$ is a
random set variable where $i$ belongs to $\hat{\mathbf{x}}$ with probability
$x_{i}$ independently for each $i$. For $k$-submodular functions, in a similar
way, we pick each element $i\in[n]$ independently with probability
$\sum\limits_{j=1}^{n}x_{i,j}$. If $i$ is selected in this process, $i$ is
assigned to $S_{j}$ exclusively following a categorical distribution $Pr[i\in
S_{j}]=x_{i,j}/\sum\limits_{j=1}^{n}x_{i,j}$. We regard the proposed
multilinear extension of $k$-submodular functions as a natural analogy of
multilinear extension of submodular functions.

###  2.2 Properties of the multilinear extension

######  Proposition 3.

Let $f$ be a $k$-submodular function. Then $F(\mathbf{x})$ defined in (1)
satisfies

  * •

(Multilinearity) $\partial F/\partial x_{i,j}$ is constant given that other
coordinates are fixed.

  * •

(Element-wise non-positive Hessian)

$\frac{\partial^{2}F}{\partial x_{i_{1},j_{1}}\partial
x_{i_{2},j_{2}}}\left\\{\begin{array}[]{cl}=0\textup{ if }i_{1}=i_{2}\\\ \leq
0\textup{ if }i_{1}\neq i_{2},\end{array}\right.\textup{for all
}i_{1},i_{2}\in[n],j_{1},j_{2}\in[k]\,.$

  * •

(Pairwise monotonicity)

$\frac{\partial F}{\partial x_{i,j_{1}}}+\frac{\partial F}{\partial
x_{i,j_{2}}}\geq 0,\textup{ for all }i\in[n],j_{1},j_{2}\in[k]\,.$ (3)

  * •

(Approximate linearity) When $f$ is non-negative, for
$\mathbf{x},\mathbf{x}^{\prime}\in[0,1]^{n\times k}$ such that
$|x_{i,j}-x^{\prime}_{i,j}|\leq\delta$ for every $i\in[n]$ and $j\in[k]$,

$F(\mathbf{x}^{\prime})-F(\mathbf{x})\geq\sum\limits_{i\in[n],j\in[k]}(x^{\prime}_{i,j}-x_{i,j})\cdot\partial_{i,j}F(\mathbf{x})-O(k^{3}n^{3}\delta^{2})\max\limits_{i,j}\Delta_{i,j}f(\emptyset)\,,$

for some sufficiently small $\delta$.

When $f$ is monotone,

  * •

(Monotonicity under monotonicity) $F$ is monotone.

These properties of the extension are intuitive and as such we defer the proof
to the appendix. Following the properties we establish a few more descriptions
of the multilinear extension.

######  Corollary 4.

Let $f$ be a $k$-submodular function. The multilinear extension
$F(\mathbf{x})$ defined in (1) satisfies

  * •

$F$ is concave along any line of direction $d\geq 0$.

  * •

Let $e_{i,j}$ denote the one-hot vector where the $(i,j)$-th element is $1$.
$F$ is convex along any line of direction $e_{i_{1},j_{1}}-e_{i_{2},j_{2}}$
for $i_{1},i_{2}\in[n]$ such that $i_{1}\neq i_{2}$ and $j_{1},j_{2}\in[k]$.

  * •

$\partial F/\partial x_{i,j}$ is constant given that all $x_{i^{\prime},j}$
are fixed for $i^{\prime}\neq i$, $j\in[k]$.

  * •

If $\mathbf{x}\leq\mathbf{y}$, then $\partial F(\mathbf{x})/\partial
x_{i,j}\geq\partial F(\mathbf{y})/\partial x_{i,j}$, for all $i\in[n]$ and
$j\in[k]$ .

###  2.3 Transforming discrete problem into continuous domain

Using multilinear extension, the unconstrained $k$-submodular maximization
problem can be transformed into continuous version as

$\max\limits_{\mathbf{x}\in\mathcal{P}}F(\mathbf{x})$

up to the rounding procedure, where
$\mathcal{P}=\\{\mathbf{x}\in\mathbb{R}^{n\times
k}:\sum\limits_{j=1}^{k}x_{i,j}\leq 1,~{}\forall i\in[n]\\}$ is the polytope
$F$ is defined on. Other constraints such as total cardinality constraints,
individual cardinality constraints, knapsack constraints, and matroid
constraints for some independent set $\mathcal{I}$ of a matroid can be applied
to $k$-submodular optimization. We list the transformation of these discrete
constraints into continuous constraints (denoted as $\mathcal{P}_{c}$) as
follows:

$\begin{array}[]{llcl}\vskip 6.0pt plus 2.0pt minus 2.0pt\textbf{total size
constraint:}&\lvert\bigcup\limits_{j=1}^{k}S_{k}\rvert\leq
B&\Longrightarrow&\mathcal{P}_{c}=\\{\mathbf{x}\in[0,1]^{n\times
k}:\sum\limits_{i,j}\mathbf{x}_{i,j}\leq B\\};\\\ \textbf{individual
constraint:}&\lvert S_{j}\rvert\leq B_{j},\forall
j\in[k]&\Longrightarrow&\mathcal{P}_{c}=\\{\mathbf{x}\in[0,1]^{n\times
k}:\sum\limits_{i}\mathbf{x}_{i,j}\leq B_{j},\forall j\in[k]\\};\\\
\textbf{knapsack constraint:}&\sum\limits_{i\in S}c_{i}\leq
B&\Longrightarrow&\mathcal{P}_{c}=\\{\mathbf{x}\in[0,1]^{n\times
k}:\sum\limits_{i}\left(c_{i}\sum\limits_{j}\mathbf{x}_{i,j}\right)\leq
B\\};\\\ \textbf{matroid
constraint:}&\bigcup\limits_{j\in[k]}S_{j}\in\mathcal{I}&\Longrightarrow&\mathcal{P}_{c}=\\{\mathbf{x}\in[0,1]^{n\times
k}:\sum\limits_{i\in S}\sum\limits_{j}\mathbf{x}_{i,j}\leq
r_{\mathcal{M}}(S)\\}.\end{array}$

In the rest of this paper, to simplify the exposition of our algorithms, we
assume that we have oracle access to $F$ and the gradient of $F$. When an
exact oracle is not available, every oracle access must be replaced with an
approximation via sampling. This makes the approximation ratio deteriorate by
a low order term only due to Chernoff-like theorems. The details are deferred
to the appendix.

##  3 Maximizing the multilinear extension function

In this section we give approximation algorithms for maximizing the
multilinear extension of $k$-submodular functions. The problem is discussed
under a different set of techniques and a variety of constraints.

Unlike submodular functions, minimizing a $k$-submodular function for $k\geq
3$ in polynomial time remains an open problem. We therefore need the
assumption that $f$ is non-negative throughout the section. We however do not
need the knowledge of the minimum point.

###  3.1 Framework of maximizing unconstrained $k$-submodular functions

Our approximation algorithms are inspired by the meta-framework proposed in
[ITY16], which results in the meta-framework (1) under the multilinear
extension. An algorithm is realized from this framework by carefully selecting
a direction $\mathbf{v}$ of update. This can be done for both the extension-
based methods and the combinatorial methods by solving the combinatorial
problem described below in Proposition 5 and Corollary 6.

Algorithm 1 Meta-framework for the multilinear extension

1:An oracle for $F$ and the gradient of $F$. A solvable down-closed polytope
$\mathcal{P}$.

2:A vector $s\in[0,1]^{n\times k}$

3:$\textbf{s}(0)\leftarrow\mathbf{0}$, $t\leftarrow 0$, set stepsize $\delta$;

4:while $s(t)$ does not reach the boundary of $\mathcal{P}$ do

5: Find a direction $\mathbf{v}\in[0,1]^{n\times k}$, such that
$\sum\limits_{j}\mathbf{v}_{i,j}=1$ for all $i$;

6: for $i\in[n]$ and $j\in[k]$ do

7:
$\mathbf{s}_{i,j}(t+1)\leftarrow\mathbf{s}_{i,j}(t)+\delta\mathbf{v}_{i,j}$;

8: $t\leftarrow t+1$. return $\mathbf{s}(T)$

To get an intuitive connection between our meta-framework and the meta-
framework for combinatorial algorithms, we note that the combinatorial meta-
framework can be viewed as a special case of our meta-framework with
$\delta=1$ and $v_{i,j}$ is the probability $p_{j}$ that the $j$-th element is
selected.

To analyze the performance of this algorithm, we adopt a few notations, which
will be used throughout this paper. Suppose that the temporary solution at the
$t$-th iteration is $\mathbf{s}(t)=(\mathbf{s}_{i,j}(t))_{i\in[n],j\in[k]}$
Specify that some integer optimum of $f$ is
$\mathbf{o}^{*}=(\mathbf{o}_{i,j})_{i\in[n],j\in[k]}$. It is noted that
$\mathbf{o}^{*}$ corresponds a partition of ground set $V$, that is,
$\\#\\{j:\mathbf{o}_{i,j}\neq 0\\}=1$, for all $i\in[n]$, and
$\\#\\{i:\mathbf{o}_{i,j}\neq 0\\}=n$. Also denote that for $\mathbf{o}^{*}$,
element $i$ is assigned to $S_{j_{i}^{*}}$, or equivalently
$\mathbf{o}_{i,j_{i}^{*}}=1$.

Define a point $\mathbf{o}(t)$ on the boundary of the polytope for the $t$-th
solution $\mathbf{s}(t)$ as

$\mathbf{o}_{i,j}(t)=\begin{cases}1-\sum\limits_{j\neq
j_{i}^{*}}\mathbf{s}_{i,j}(t)&j=j_{i}^{*}\\\ \mathbf{s}_{i,j}(t)&j\neq
j_{i}^{*},\\\ \end{cases}~{}\forall i\in[n]\,.$

Then, we have

$\mathbf{o}_{i,j}(t+1)=\begin{cases}1-\sum\limits_{j\neq
j_{i}^{*}}(\mathbf{s}_{i,j}(t)+\delta\mathbf{v}_{i,j}(t))&j=j_{i}^{*}\\\
\mathbf{s}_{i,j}(t)+\delta\mathbf{v}_{i,j}(t)&j\neq j_{i}^{*},\\\
\end{cases}~{}\forall i\in[n]\,.$

By definition, $\mathbf{o}(0)=\mathbf{o}^{*}$, as $\mathbf{s}(0)=\mathbf{0}$
and its projection must be the optimum, and $\mathbf{o}(T)=\mathbf{s}(T)$, as
$\mathbf{s}(T)$ is on the boundary of the polytope. Therefore as long as we
can find a $c\in\mathbb{R}^{+}$ such that

$c(F(\mathbf{s}(t+1))-F(\mathbf{s}(t)))\geq
F(\mathbf{o}(t))-F(\mathbf{o}(t+1))\,,$ (4)

we can conclude that

$F(\mathbf{s}(T))\geq
F(\mathbf{s}(T))-\dfrac{c}{c+1}F(\mathbf{s}(0))\geq\dfrac{1}{c+1}F(\mathbf{o}^{*})=\dfrac{1}{c+1}\cdot
OPT\,.$

Now we analyze Equation (4). By the approximate linearity, the LHS can be
lower bounded by

$c(F(\mathbf{s}(t+1))-F(\mathbf{s}(t)))\geq
c\sum\limits_{i\in[n],j\in[k]}\delta\mathbf{v}_{i,j}\partial_{i,j}F(\mathbf{s}(t))-O(ck^{3}n^{3}\delta^{2})\max\limits_{i,j}\Delta_{i,j}f(\emptyset)\,.$

For the RHS, we use the following algorithm to construct a sequence
$\mathbf{o}^{0}=\mathbf{o}(t+1),\mathbf{o}^{1},\dots,\mathbf{o}^{m}=\mathbf{o}(t)$
such that there is at most one coordinate where $\mathbf{o}^{l}$ and
$\mathbf{o}^{l+1}$ have different value for any $l\in[m]$. This algorithm is
not executed in $k$-submodular optimization and is only designed to analyze
Algorithm 1.

Algorithm 2 Sequence generation for
$\mathbf{o}^{0},\mathbf{o}^{1},\dots,\mathbf{o}^{m}$

1:Two different points $\mathbf{o}(t)$ and $\mathbf{o}(t+1)$ in
$[0,1]^{n\times k}$.

2:A sequence
$\mathbf{o}^{1,1},\dots,\mathbf{o}^{1,k},\dots,\mathbf{o}^{n,1},\dots,\mathbf{o}^{n,k},\mathbf{o}(t)$
in $[0,1]^{n\times k}$.

3:Let $\mathbf{o}^{1,1}=\mathbf{o}(t+1)$, $\mathbf{o}^{m}=\mathbf{o}(t)$;

4:Compute $I^{+}=\\{(i,j):\mathbf{o}_{i,j}(t)\geq\mathbf{o}_{i,j}(t+1)\\}$ and
$I^{-}=\\{(i,j):\mathbf{o}_{i,j}(t)<\mathbf{o}_{i,j}(t+1)\\}$;

5:for $i\in[n]$ do

6: Set index $l=1$.

7: for $j\mbox{ such that }(i,j)\in I^{-}$ do

8: $\mathbf{o}_{i,j}^{i,l+1}\leftarrow\mathbf{o}_{i,j}(t)$, for other indices
$(i_{1},j_{1})$,
$\mathbf{o}_{i_{1},j_{1}}^{i,l+1}\leftarrow\mathbf{o}_{i_{1},j_{1}}^{i,l}$;

9: $l\leftarrow l+1$

10: for $j\mbox{ such that }(i,j)\in I^{+}$ do

11: if $l\neq k$ then

12: $\mathbf{o}_{i,j}^{i,l+1}\leftarrow\mathbf{o}_{i,j}(t)$, for other indices
$(i_{1},j_{1})$,
$\mathbf{o}_{i_{1},j_{1}}^{i,l+1}\leftarrow\mathbf{o}_{i_{1},j_{1}}^{i,l}$;

13: $l\leftarrow l+1$

14: else

15: $\mathbf{o}_{i,j}^{i+1,1}\leftarrow\mathbf{o}_{i,j}(t)$, for other indices
$(i_{1},j_{1})$,
$\mathbf{o}_{i_{1},j_{1}}^{i+1,1}\leftarrow\mathbf{o}_{i_{1},j_{1}}^{i,l}$;

It is noted that the elements in the sequence always satisfy that
$\sum\limits_{j}\mathbf{o}^{l_{1},l_{2}}_{i,j}\leq 1$, for all $i\in n$,
$l_{1}\in[n]$, $l_{2}\in[k]$, which indicates that
$\mathbf{o}^{i,l}\in\mathcal{P}$. Thus, the RHS can be decomposed as

$\displaystyle F(\mathbf{o}(t))-F(\mathbf{o}(t+1))=$
$\displaystyle\sum\limits_{l=0}^{m-1}\left(F(\mathbf{o}^{l+1})-F(\mathbf{o}^{l})\right)$
$\displaystyle=$ $\displaystyle-\sum\limits_{i\in[n]}\sum\limits_{j\neq
j_{i}^{*}}\delta\mathbf{v}_{i,j}\partial_{i,j}F(\mathbf{o}^{i,j_{l}})+\sum\limits_{i\in[n]}\sum\limits_{j\neq
j_{i}^{*}}\delta\mathbf{v}_{i,j}\partial_{i,j_{i}^{*}}F(\mathbf{o}^{i,k})\,,$

where the last equality is by the multilinearity, and $(i,j_{l})$ represents
the upper index correspond to $(i,j)$ in every iteration, and the difference
in coordinate $(i,j)$ is $\delta\mathbf{v}_{i,j}$ when $j\neq j_{i}^{*}$,
while the difference is $\delta\sum\limits_{j\neq j_{i}^{*}}\mathbf{v}_{i,j}$
in coordinate $(i,j_{i}^{*})$. By the non-negativity of Hessian, we have

$\frac{\partial^{2}F}{\partial x_{i_{1},j_{1}}\partial
x_{i_{2},j_{2}}}\left\\{\begin{array}[]{cl}=0\textup{ if }i_{1}=i_{2}\\\ \leq
0\textup{ if }i_{1}\neq i_{2},\end{array}\right.\textup{for all
}i_{1},i_{2}\in[n],j_{1},j_{2}\in[k]\,.$

Thus for any two point $\mathbf{x}$ and $\mathbf{x}^{\prime}$, if there exists
at most one $i_{0}\in[n]$ such that for all $i\neq i_{0}$ and $j\in[k]$,
$\mathbf{x}_{i,j}=\mathbf{x}^{\prime}_{i,j}$, then

$\partial_{i_{0},j}F(\mathbf{x})=\partial_{i_{0},j}F(\mathbf{x}^{\prime}),~{}\forall
j\in[k]\,.$

Therefore,

$\displaystyle F(\mathbf{o}(t))-F(\mathbf{o}(t+1))=$
$\displaystyle-\sum\limits_{i\in[n]}\sum\limits_{j\neq
j_{i}^{*}}\delta\mathbf{v}_{i,j}\partial_{i,j}F(\mathbf{o}^{i,j_{l}})+\sum\limits_{i\in[n]}\sum\limits_{j\neq
j_{i}^{*}}\delta\mathbf{v}_{i,j}\partial_{i,j_{i}^{*}}F(\mathbf{o}^{i,k})$
$\displaystyle=$ $\displaystyle-\sum\limits_{i\in[n]}\sum\limits_{j\neq
j_{i}^{*}}\delta\mathbf{v}_{i,j}\partial_{i,j}F(\mathbf{o}^{i,1})+\sum\limits_{i\in[n]}\sum\limits_{j\neq
j_{i}^{*}}\delta\mathbf{v}_{i,j}\partial_{i,j_{i}^{*}}F(\mathbf{o}^{i,1})$
$\displaystyle=$
$\displaystyle-\sum\limits_{i\in[n]}\sum\limits_{j\in[k]}\delta\mathbf{v}_{i,j}\partial_{i,j}F(\mathbf{o}^{i,1})+\sum\limits_{i\in[n]}\sum\limits_{j\in[k]}\delta\mathbf{v}_{i,j}\partial_{i,j_{i}^{*}}F(\mathbf{o}^{i,1})\,.$

By definition, we have $\mathbf{s}(t)\leq\mathbf{o}(t)$ and
$\mathbf{s}(t)\leq\mathbf{o}(t+1)$. Then for all $i\in[n]$ and $l\in[k]$ we
have $\mathbf{s}(t)\leq\mathbf{o}^{i,l}$. Thus

$\partial_{i,j}F(\mathbf{s}(t))\geq\partial_{i,j}F(\mathbf{o}^{i_{0},l}),~{}\forall
i,i_{0}\in[n],j,l\in[k]\,.$

Let, for all $i\in[n]$, $j\in[k]$, $y_{i,j}=\partial_{i,j}F(\mathbf{s}(t))$,
$a_{i,j}=\partial_{i,j}F(\mathbf{o}^{i,1})$. We have by the pairwise
monotonicity

$y_{i,j}+y_{i,j^{\prime}}\geq 0,~{}~{}\forall j,j^{\prime}\in[k],j\neq
j^{\prime}\,,$ $a_{i,j}+a_{i,j^{\prime}}\geq 0,~{}~{}\forall
j,j^{\prime}\in[k],j\neq j^{\prime}\,,$

and

$y_{i}\geq a_{i}\,.$

As long as we can find a $\mathbf{v}$ such that

$\sum\limits_{i\in[n]}\sum\limits_{j\in[k]}\mathbf{v}_{i,j}\left(a_{i,j_{i}^{*}}-a_{i,j}\right)\leq
c\left(\sum\limits_{i\in[n]}\sum\limits_{j\in[k]}\mathbf{v}_{i,j}y_{i,j}\right)\,,$

we have

$c\left(F(\mathbf{s}(t+1))-F(\mathbf{s}(t))\right)\geq
F(\mathbf{o}(t))-F(\mathbf{o}(t+1))-O(ck^{3}n^{3}\delta^{2})\max\limits_{i,j}\Delta_{i,j}f(\emptyset)\,,$

which indicates that

$F(\mathbf{s}(T))\geq
F(\mathbf{s}(T))-\frac{c}{c+1}F(\mathbf{s}(0))\geq\frac{1}{c+1}F(\mathbf{o}^{*})-T\cdot\frac{c}{c+1}\cdot
O(k^{3}n^{3}\delta^{2})\max\limits_{i,j}\Delta_{i,j}f(\emptyset)\,.$

Due to the fact that for every iteration $\sum\limits_{j}\mathbf{s}_{i,j}(t)$
increases by at most $\delta$, $T=O(1/\delta)$. Thus by choosing some
sufficient small $\delta=O(k^{-3}n^{-3})$, the last term can be sufficiently
small.

The approximation factor for maximizing $F$ without constraints through the
meta-framework follows immediately.

######  Proposition 5.

Let $c\in\mathbb{R}^{+}$ be a constant. If in every iteration, given two
sequences $a_{i,j}$ and $y_{i,j}$, $i\in[n]$, $j\in[k]$, such that
$y_{i,j}+y_{i,j^{\prime}}\geq 0,~{}\forall j,j^{\prime}\in[k],j\neq
j^{\prime}$, $a_{i,j}+a_{i,j^{\prime}}\geq 0,~{}\forall
j,j^{\prime}\in[k],j\neq j^{\prime}$, and $y_{i}\geq a_{i}$, one can specify a
vector $\mathbf{v}\in[0,1]^{n\times k}$ such that
$\sum\limits_{i\in[n]}\sum\limits_{j\in[k]}\mathbf{v}_{i,j}\left(a_{i,j_{i}^{*}}-a_{i,j}\right)\leq
c\left(\sum\limits_{i\in[n]}\sum\limits_{j\in[k]}\mathbf{v}_{i,j}y_{i,j}\right)$
holds for an arbitrary assignment of $j_{i}^{*}$, then the output
$\mathbf{s}(T)$ of the meta-framework (Algorithm 1) satisfies

$F(\mathbf{s}(T))\geq\dfrac{1}{c+1}\cdot OPT-\epsilon\,.$

###### Proof.

The proposition is derived by the arguments preceding it. ∎

When $f$ is monotone, $y_{i,j}=\partial_{i,j}F(\mathbf{s}(t))\geq 0$,
$a_{i,j}=\partial_{i,j}F(\mathbf{o}^{i,1})\geq 0$. One only needs to solve the
same combinatorial problem under non-negative $y_{i,j}$ and $a_{i,j}$
sequences.

######  Corollary 6.

Let $c\in\mathbb{R}^{+}$ be a constant and $f$ be monotone $k$-submodular. If
in every iteration, given two sequences $a_{i,j}$ and $y_{i,j}$, $i\in[n]$,
$j\in[k]$, such that $y_{i,j}\geq 0,~{}\forall j\in[k]$, $a_{i,j}\geq
0,~{}\forall j\in[k]$, and $y_{i}\geq a_{i}$, one can specify a vector
$\mathbf{v}\in[0,1]^{n\times k}$ such that
$\sum\limits_{i\in[n]}\sum\limits_{j\in[k]}\mathbf{v}_{i,j}\left(a_{i,j_{i}^{*}}-a_{i,j}\right)\leq
c\left(\sum\limits_{i\in[n]}\sum\limits_{j\in[k]}\mathbf{v}_{i,j}y_{i,j}\right)$
holds for an arbitrary assignment of $j_{i}^{*}$, then the output
$\mathbf{s}(T)$ of the meta-framework (Algorithm 1) satisfies
$F(\mathbf{s}(T))\geq\dfrac{1}{c+1}\cdot OPT-\epsilon$.

Improving this specific combinatorial program can be slightly out of the scope
of this paper. But armed with the multilinear extension, we see that simply
setting $\mathbf{v}$ to be the one-hot vector that takes $1$ only on the index
with the largest gradient can result in an almost $\frac{1}{2}$-approximation
algorithm for the monotone case. This factor is asymptotically as good as the
best available results on $k$-submodular optimization.

######  Theorem 7.

Let $\mathbf{o^{*}}$ be a maximum of a multilinear extension $F$. By setting
$\mathbf{v}_{i,j_{i}(t)}(t)=1$ where
$j_{i}(t)=\operatorname*{arg\,max}_{j\in[k]}\partial_{i,j}F(\mathbf{s}(t))$
(ties break arbitrarily) and $0$ otherwise in Algorithm 1, we have
$F(\mathbf{s}(1/\delta))\geq\dfrac{1}{2}f(\mathbf{o})-\epsilon$ and
$\mathbf{s}(1/\delta)\in\mathcal{P}$ for some sufficiently small $\delta$ that
divides $1$.

###### Proof.

We first prove that $\mathbf{s}(1/\delta)\in\mathcal{P}$. In fact, as in every
iteration $\sum\limits_{j}\mathbf{v}_{i,j}(t)=1$ for any $i\in[n]$, we have

$\sum\limits_{j}\mathbf{s}_{i,j}(1/\delta)=\sum\limits_{j}\sum\limits_{t=0}^{1/\delta-1}\delta\cdot\mathbf{v}_{i,j}(t)=\delta\cdot
1/\delta=1\,.$

Thus $\mathbf{s}(1/\delta)$ is exactly on the boundary of $\mathcal{P}$. It
suffices to prove Equation (4) with $c=1$. We have

$\displaystyle\sum\limits_{i\in[n]}\sum\limits_{j\in[k]}\mathbf{v}_{i,j}\left(a_{i,j_{i}^{*}}-a_{i,j}\right)\leq\sum\limits_{i\in[n]}\sum\limits_{j\in[k]}\mathbf{v}_{i,j}a_{i,j_{i}^{*}}\leq\sum\limits_{i\in[n]}\sum\limits_{j\in[k]}\mathbf{v}_{i,j}y_{i,j_{i}^{*}}\leq\sum\limits_{i\in[n]}\max\limits_{j}y_{i,j}=\sum\limits_{i\in[n]}\sum\limits_{j\in[k]}\mathbf{v}_{i,j}y_{i,j}$

as desired. ∎

If we choose $\mathbf{v}$ such that $\\#\\{i\in[n]:\exists
j\in[k],\mathbf{v}_{i,j}\neq 0\\}=1$, and take the advantage of the
constructed probability distributions in [ITY16] and [Osh21] by setting
$\mathbf{v}_{i,j}=p_{j}$ for every $i\in[n]$, we can get three algorithms with
respective approximation factors.

######  Corollary 8.

There exist respective choices of $\mathbf{v}$ such that the approximation
factor of Algorithm 1 is almost

  * •

$\frac{k}{2k-1}$, for monotone $k$-submodular functions, and

  * •

$\frac{\sqrt{17}-1}{4}$, for monotone $3$-submodular functions, and

  * •

$\frac{k^{2}+1}{2k^{2}+1}$, for non-monotone $k$-submodular functions.

###  3.2 Maximizing monotone $k$-submodular functions under knapsack
constraint

In this section, we transform the knapsack constraint to the multilinear
extension and present the maximization algorithm under such a constraint. This
solves

$\max\limits_{\mathbf{x}\in\mathcal{P}\cap\mathcal{P}_{c}}F(\mathbf{x})\,,$

where $F(\mathbf{x})$ is a multilinear extension of a monotone $k$-submodular
function, $\mathcal{P}=\\{\mathbf{x}\in[0,1]^{n\times
k}:\sum\limits_{j=1}^{k}\mathbf{x}_{i,j}\leq 1,\forall i\in[n]\\}$, and
$\mathcal{P}_{c}=\\{\mathbf{x}\in[0,1]^{n\times
k}:\sum\limits_{i=1}^{n}c_{i}\sum\limits_{j=1}^{k}\mathbf{x}_{i,j}\leq B\\}$
for some knapsack $c_{i}$, $B$.

Algorithm 3 Maximization of the multilinear extension under knapsack
constraint

1:An oracle for $F$ and the gradient of $F$; Cost $c_{i}$ and budget $B$

2:A vector $s\in[0,1]^{n\times k}$

3:$\textbf{s}(0)\leftarrow\mathbf{0}$ and $t\leftarrow 0$, set stepsize
$\delta$

4:while s does not reach the boundary of $\mathcal{P}\cap\mathcal{P}_{c}$ do

5: Find
$(i(t),j(t))=\operatorname*{arg\,max}\limits_{i,j}\\{\dfrac{\partial_{i,j}F(\mathbf{s}(t))}{c_{i}}:\mathbf{s}(t)+\delta\cdot
e_{i,j}\in\mathcal{P}\cap\mathcal{P}_{c}\\}$

6: $\mathbf{v}_{i,j}=\begin{cases}1&\textup{ if }(i,j)=(i(t),j(t))\\\
0&\textup{ otherwise }\\\ \end{cases}$

7: for $i\in[n]$ and $j\in[k]$ do

8:
$\mathbf{s}_{i,j}(t+1)\leftarrow\mathbf{s}_{i,j}(t)+\delta\mathbf{v}_{i,j}(t)$

9: $t\leftarrow t+1$. return $\mathbf{s}(T)$

######  Theorem 9.

Let $f$ be a monotone $k$-submodular function and $F$ be its multilinear
extension. The output of Algorithm 3 satisfies

$F(\mathbf{s}(T))\geq\dfrac{1}{2}F(\mathbf{o}^{*})\,.$

The proof of this theorem is based on similar techniques that constructs a
sequence $\mathbf{o}^{0},\dots,\mathbf{o}^{m}$ on the boundary such that
$F(\mathbf{o}(t))-F(\mathbf{o}(t+1))$ can be decomposed by this sequence. Then
due to the multilinearity, every decomposed part
$F(\mathbf{o}^{l+1})-F(\mathbf{o}^{l})$ can be written into
$\left(\mathbf{o}^{l+1}_{i_{l},j_{l}}-\mathbf{o}^{l}_{i_{l},j_{l}}\right)\partial_{i_{l},j_{l}}F(\mathbf{o}^{l})$,
while the gain of every step is $\delta\partial_{i(t),j(t)}F(\mathbf{s}(t))$.
Thus it is sufficient to compare this sum of partial derivative and the gain
$\delta\partial_{i(t),j(t)}F(\mathbf{s}(t))$ in every step. The proof is
deferred to the appendix.

We can further restrict some coordinates to $0$. Let
$\mathcal{P}_{D}=\\{\mathbf{x}\in[0,1]^{n\times k}:\mathbf{x}_{i,j}=0$,
$(i,j)\in D\\}$. As the zero constraints do not affect the construction of
$\mathbf{o}(t)$, the same proof technique will apply and we obtain the same
approximation factor on the optimization problem

$\max\limits_{\mathbf{x}\in\mathcal{P}\cap\mathcal{P}_{c}\cap\mathcal{P}_{D}}F(\mathbf{x})\,.$

######  Corollary 10.

Let $f$ be a monotone $k$-submodular function and $F$ be its multilinear
extension. For the problem
$\max\limits_{\mathbf{x}\in\mathcal{P}\cap\mathcal{P}_{c}\cap\mathcal{P}_{D}}F(\mathbf{x})\,$,
the output of Algorithm 3 satisfies

$F(\mathbf{s}(T))\geq\dfrac{1}{2}F(\mathbf{o}^{*})\,.$

This result will be useful later in Algorithm 4, as we utilize it to handle
the items with large costs.

##  4 Rounding

Observing that the original polytope
$\mathcal{P}=\\{\mathbf{x}\in[0,1]^{n\times
k}:\sum\limits_{j}\mathbf{x}_{i,j}\leq 1,~{}\forall i\in[n]\\}$ is the
polytope of the partition matroid $\mathcal{P}(\mathcal{M})$, results in
randomized swap rounding and randomized pipage rounding could be useful
[CVZ09]. Some results are recalled in Lemma 11. However, to adopt them to
$k$-submodular functions, we will need to modify the lower-tail bound. For
unconstrained or total size-constrained problems, randomized swap rounding or
randomized pipage rounding can be utilized directly. For knapsack-constrained
problems, we use standard techniques like partial enumeration to eliminate all
items of large value or size. This allows us to scale down the constraints by
a small value so that a room is created for potential overflow in the rounding
process.

We first introduce existing tail bounds and the tail bound we observe for
$k$-submodular functions.

######  Lemma 11 (Chekuri, Vondrák, and Zenklusen [CVZ09]).

Let $a_{i,j}\in[0,1]$ and $X=\sum\limits_{i}a_{i,j}X_{i,j}$, where
$(X_{1,1},\dots,X_{n,k})$ are obtained by either randomized swap rounding or
randomized pipage rounding from a starting point $(x_{1},\dots
x_{n})\in\mathcal{P}(\mathcal{M})$.

  * •

If $\delta\geq 0$ and $\mu\geq\mathbb{[}X]=\sum\limits_{i}a_{i,j}X_{i,j}$,
then
$Pr[X\geq(1+\delta)\mu]\leq\left(\frac{e^{\delta}}{(1+\delta)^{1+\delta}}\right)^{\mu}$;

  * •

For $\delta\in[0,1]$, the bound can be simplified to
$\mbox{Pr}[X\geq(1+\delta)\mu]\leq e^{-\mu\delta^{2}/3}$.

######  Lemma 12.

Let $f(S)$ be a monotone $k$-submodular function with marginal values in
$[0,1]$, and $F(x)=\mathbb{E}[f(\hat{\mathbf{x}})]$ its multilinear extension.
Let
$(x_{1,1},\dots,x_{1,k},\dots,x_{n,1},\dots,x_{n,k})\in\mathcal{P}(\mathcal{M})$
be a point in a matroid polytope and $R$ a random independent set obtained
from it by randomized swap rounding. Let
$\mu_{0}=F(x_{1,1},\dots,x_{1,k},\dots,x_{n,1},\dots,x_{n,k})$ and $\delta>0$.
Then $\mathbb{E}[f(R)]\geq\mu_{0}$ and

$Pr[f(R)\leq(1-\delta)\mu_{0}]\leq e^{-\mu_{0}\delta^{2}/8}.$

For the unconstrained problem and the problem with a total size constraint,
suppose that we have approximately maximized the extension and get a
fractional solution $\mathbf{x}$ such that $F(\mathbf{x})\geq\alpha
f(\mathbf{o}^{*})-\epsilon$. Then by using randomized swap rounding directly
and the tail bound in Lemma 12, we obtain that with high probability
$\mathbb{E}[f(R)]\geq F(\mathbf{x})\geq\alpha f(\mathbf{o}^{*})-\varepsilon$.

Following Corollary 8 and the rounding, there exist respective algorithms
using the multilinear extension that outputs an $R$ such that the approximate
factor is almost

  * •

$\frac{k}{2k-1}$, for monotone $k$-submodular functions, and

  * •

$\frac{k^{2}+1}{2k^{2}+1}$, for non-monotone $k$-submodular functions, and

  * •

$\frac{1}{2}$, for monotone $k$-submodular function under the total size
constraint.

The last statement is true as randomized swap rounding does not change the
total size. For a monotone $k$-submodular function with a knapsack constraint,
we design the following algorithm to maximize it.

Algorithm 4 Maximization of $k$-submodular function with a knapsack constraint

1:Assume $0<\epsilon<1/4$. Enumerate all sets $A$ of at most $1/\epsilon^{4}$
items that form a feasible solution. For each candidate set $A$, repeat the
following. Suppose that the element $i$ chosen by $A$ is assigned to
$S_{j}^{*}$ in other word $A_{i,j^{*}_{i}}=1$.

2:For $i\in A$, delete $i$ from $[n]$ and get a new ground set $[\hat{n}]$.
Let $B^{\prime}=B-\sum\limits_{i}c_{i}$ be the remaining capacity in knapsack.

3:Let $D$ be the set of items $(i,j)\not\in A$ such that either
$f(A\vee\mathbf{1}_{i,j})>\varepsilon^{4}f(A)$ or
$c_{i}>\epsilon^{3}B^{\prime}$ (the item is relatively larger compared to the
size of the knapsack). Remove all the items in $D$.

4:We consider a reduced problem on the item set $[\hat{n}]\times[k]$. Define
the polytope  $\mathcal{P}^{\prime}=\\{\mathbf{x}\in[0,1]^{\hat{n}\times
k}:\sum_{j}\mathbf{x}_{i,j}\leq 1,~{}\forall i\in[\hat{n}]\mbox{ and
}\sum\limits_{i}\hat{c}_{i}\sum\limits_{j}\mathbf{x}_{i,j}\leq
B^{\prime}\,.\\}$ Let $G(\mathbf{x})$ be the multilinear extension of
$g(\mathbf{x})=f(\mathbf{x}\sqcup A)-f(A)$ on the ground set $[\hat{n}]$. Also
add constraint $\mathbf{x}_{i,j}=0$ when $(i,j)\in D$.

5:Solve the following problem
$\max\\{G(\mathbf{x}):\mathbf{x}\in(1-\epsilon)\mathcal{P}^{\prime}\mbox{ and
}\mathbf{x}_{i,j}=0\mbox{ when }(i,j)\in D\\}$ (5) and find a approximation
fractional solution $\mathbf{x}^{*}$ within factor-$1/2$ of optimal.

6:Apply randomized pipage rounding to $x^{*}$ with respect to the polytope
$\mathcal{P}_{M}=\\{\mathbf{x}\in[0,1]^{\hat{n}\times
k}:\sum\limits_{j}\mathbf{x}_{i,j}\leq 1,~{}\forall i\in[\hat{n}]\\}\,.$
Denote this result $R_{A}$. Among all candidate sets $A$ such that $A\cup
R_{A}$ is feasible, return the one that maximizes $f(A\sqcup R_{A})$.

7:return $A\sqcup R_{A}$

######  Theorem 13.

With some constant probability Algorithm 4 returns a solution of value at
least $(\frac{1}{2}-2\epsilon)\cdot OPT$.

###### Proof.

Consider an optimum solution $O=(O_{1},\dots,O_{k})\in[0,1]^{n\times k}$, such
that $OPT=f(O)$. Order the elements of $O$ greedily in decreasing marginal
values, and let $A\subseteq O$ be the elements whose marginal value are at
least $\epsilon^{4}\cdot OPT$. There can be at most $1/\epsilon^{4}$ such
elements and the algorithm will consider them as one of the candidate sets,
which guarantees that $A$ must be selected by the algorithm in its first step.

We consider the reduced instance, $O\setminus A:=(O_{1}\setminus
A_{1},\dots,O_{k}\setminus A_{k})\in[0,1]^{\hat{n}\times k}$, which lies in
the polytope $\mathcal{P}^{\prime}$. We observe that in $O\setminus A$, there
does not exist an item of marginal value more than the last item in $A$. In
particular,
$f(A_{1},\dots,A_{j}\cup\\{i\\},\dots,A_{k})-f(A)\leq\epsilon^{4}f(A)\leq\epsilon^{4}\cdot
OPT$ for all $i\in\bigcup\limits_{j\in[k]}\left(O_{j}\setminus A_{j}\right)$
and $j\in[k]$. We remove all items $(i,j)$ such that
$f(A_{1},\dots,A_{j}\cup\\{i\\},\dots,A_{k})-f(A)>\epsilon^{4}f(A)$ and this
will not affect any item in $O\setminus A$. We also remove the set
$D\subseteq[\hat{n}]\times[k]$ of items whose size in the knapsack
$B^{\prime}$ is more than $\epsilon^{3}B^{\prime}$. In
$\bigcup\limits_{j\in[k]}\left(O_{j}\setminus A_{j}\right)$, there can be at
most $1/\epsilon^{3}$ such items.

Consider that $g(O\sqcap D)=f((O\sqcap D)\sqcup A)-f(A)\leq\epsilon\cdot OPT$.
Let $O^{\prime}=(O_{1}\setminus(A_{1}\cup
D_{1}),\dots,O_{k}\setminus(A_{k}\cup D_{k}))$. Then,

$\displaystyle g(O^{\prime})=$ $\displaystyle\ g(O_{1}\setminus(A_{1}\cup
D_{1}),\dots,O_{k}\setminus(A_{k}\cup D_{k}))$ $\displaystyle=$
$\displaystyle\ g((O_{1}\setminus A_{1})\setminus(O_{1}\cap
D_{1}),\dots,(O_{k}\setminus A_{k})\setminus(O_{k}\cap D_{k}))$
$\displaystyle\geq$ $\displaystyle\ g(O\setminus A)-g(O\sqcap D)$
$\displaystyle\geq$ $\displaystyle\ OPT-f(A)-\varepsilon\cdot OPT\,.$

Now consider the reduced multilinear problem (5). We observe that the
indicator vector $\mathbf{1}_{O^{\prime}}$ is feasible in
$\mathcal{P}^{\prime}$ and therefore $(1-\epsilon)\mathbf{1}_{O^{\prime}}$ is
feasible in $(1-\epsilon)\mathcal{P}^{\prime}$. By the concavity of $G(x)$
along the line from the origin to $\mathbf{1}_{O^{\prime}}$, we have
$G((1-\epsilon)\mathbf{1}_{O^{\prime}})\geq(1-\epsilon)g(O^{\prime})\geq(1-2\epsilon)\cdot
OPT-f(A)$. Corollary 10 allows us to specify a fractional approximate optimum
$\mathbf{x}^{*}$ of value at least

$G(\mathbf{x}^{*})\geq\frac{1}{2}G((1-\epsilon)\mathbf{1}_{O^{\prime}})\geq(\frac{1}{2}-\epsilon)\cdot
OPT-f(A)\,.$

Finally, we apply randomized swap rounding (or pipage rounding) to
$\mathbf{x}^{*}$ and call the resulting set $R$. By the construction of
randomized swap rounding, $R$ is on the vertex of the polytope
$\mathcal{P}_{o}=\\{\mathbf{x}\in[0,1]^{\hat{n}\times
k}:\sum\limits_{j}\mathbf{x}_{i,j}\leq 1,~{}\forall i\in[\hat{n}]\\}$ with
probability $1$. It however may violate the knapsack constraint.

Our fractional solution $\mathbf{x}^{*}$ satisfies
$\sum\limits_{i}c_{i}\sum\limits_{j}\mathbf{x}^{*}_{i,j}\leq(1-\epsilon)B^{\prime}$.
Also, note that all sizes in the reduced instance are bounded by
$c_{i}\leq\epsilon^{3}B^{\prime}$. By scaling
$c_{i}^{\prime}=c_{i}/(\epsilon^{3}B^{\prime})$, we can apply Lemma 11 with
$\mu=(1-\epsilon)/\epsilon^{3}$ and obtain

$Pr[\sum\limits_{i\in R}c_{i}\geq B^{\prime}]\leq Pr[\sum\limits_{i\in
R}c_{i}^{\prime}\geq(1+\epsilon)\mu]\leq e^{-\mu\epsilon^{2}/3}\leq
e^{-1/4\epsilon}\,.$

Meanwhile, consider the objective function $g(R)$. In the reduced instance,
all items have their value $g(i)\leq\epsilon^{4}\cdot OPT$. Let
$\mu=G(\mathbf{x}^{*})/(\epsilon^{4}\cdot OPT)$. Then Lemma 12 implies that,

$Pr[g(R)\leq(1-\delta)G(\mathbf{x}^{*})]=Pr[g(R)/(\epsilon^{4}\cdot
OPT)\leq(1-\delta)\mu]\leq
e^{-\mu\delta^{2}/8}=e^{-\delta^{2}G(\mathbf{x}^{*})/8\epsilon^{4}\cdot
OPT}\,.$

Let $\delta=\frac{1}{G(\mathbf{x}^{*})}\epsilon\cdot OPT$. We have

$Pr[g(R)\leq G(\mathbf{x}^{*})-\epsilon\cdot OPT]\leq e^{-1/8\epsilon^{2}}\,.$

By the union bound,

$Pr[g(R)\leq G(\mathbf{x}^{*})-\epsilon\cdot OPT\mbox{ or }\sum\limits_{i\in
R}c_{i}\geq B^{\prime}]\leq e^{-1/4\epsilon}+e^{-1/8\epsilon^{2}}.$

For $\epsilon<1/4$, this probability is at most $e^{-2}+e^{-1}<1$. When this
event does not occur, which is with at least some constant probability, we
have a feasible solution of value $f(R)=f(A)+g(R)\geq
f(A)+G(\mathbf{x}^{*})-\epsilon\cdot OPT\geq(1/2-2\epsilon)\cdot OPT$. ∎

##  5 Conclusion

We propose the multilinear extension for $k$-submodular functions. This is an
analogy of the multilinear extension for submodular functions, which
transforms the combinatorial problem into continuous optimization and
rounding. We show that armed with the multilinear extension, a simple
algorithm can achieve an almost $\frac{1}{2}$-approximation algorithm for
monotone $k$-submodular functions, which is asymptotically as good as the best
results available. Results almost as good as the combinatorial meta-framework
can be achieved by the multilinear extension. For monotone $k$-submodular
maximization under knapsack and total size constraints, state-of-the-art
results are obtained through our extension.

The multilinear extension could lead to a new line of research for
$k$-submodular optimization. New techniques can be developed for a variety of
$k$-submodular optimization problems and constraints. For unconstrained
$k$-submodular maximization, it remains open if the multilinear extension
could obtain an improved approximation factor by investigating the
combinatorial problem in Proposition 5 and 6. For non-monotone $k$-submodular
functions, it leaves an interesting open problem to study algorithms and
techniques for pairwise monotone functions (3) and their optimization.

## References

  * [AFN96] Kazutoshi Ando, Satoru Fujishige, and Takeshi Naitoh.  A characterization of bisubmodular functions.  Discrete Mathematics, 148(1-3):299–303, 1996.
  * [AS04] Alexander A Ageev and Maxim I Sviridenko.  Pipage rounding: A new method of constructing algorithms with proven performance guarantee.  Journal of Combinatorial Optimization, 8(3):307–328, 2004.
  * [BF19] Niv Buchbinder and Moran Feldman.  Constrained submodular maximization via a nonsymmetric technique.  Mathematics of Operations Research, 44(3):988–1005, 2019.
  * [BKNS12] Nikhil Bansal, Nitish Korula, Viswanath Nagarajan, and Aravind Srinivasan.  Solving packing integer programs via randomized rounding with alterations.  Theory of Computing, 8(1):533–565, 2012.
  * [CCPV07] Gruia Calinescu, Chandra Chekuri, Martin Pál, and Jan Vondrák.  Maximizing a submodular set function subject to a matroid constraint.  In International Conference on Integer Programming and Combinatorial Optimization, pages 182–196. Springer, 2007.
  * [CCPV11] 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.
  * [CVZ09] Chandra Chekuri, Jan Vondrák, and Rico Zenklusen.  Dependent randomized rounding for matroid polytopes and applications.  arXiv preprint arXiv:0909.4348, 2009.
  * [CVZ10] Chandra Chekuri, Jan Vondrák, and Rico Zenklusen.  Dependent randomized rounding via exchange properties of combinatorial structures.  In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pages 575–584. IEEE, 2010.
  * [CVZ14] Chandra Chekuri, Jan Vondrák, and Rico Zenklusen.  Submodular function maximization via the multilinear relaxation and contention resolution schemes.  SIAM Journal on Computing, 43(6):1831–1879, 2014.
  * [EN16] Alina Ene and Huy L Nguyen.  Constrained submodular maximization: Beyond $1/e$.  In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science, pages 248–257. IEEE, 2016.
  * [FMV11] Uriel Feige, Vahab S Mirrokni, and Jan Vondrak.  Maximizing non-monotone submodular functions.  SIAM Journal on Computing, 40(4):1133–1153, 2011.
  * [FNSW11] Moran Feldman, Joseph Seffi Naor, Roy Schwartz, and Justin Ward.  Improved approximations for $k$-exchange systems.  In European Symposium on Algorithms, pages 784–798. Springer, 2011\.
  * [ITY16] Satoru Iwata, Shin-ichi Tanigawa, and Yuichi Yoshida.  Improved approximation algorithms for $k$-submodular function maximization.  In Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms, pages 404–413. SIAM, 2016.
  * [KKT03] David Kempe, Jon Kleinberg, and Éva Tardos.  Maximizing the spread of influence through a social network.  In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 137–146, 2003.
  * [KLG+08] Andreas Krause, Jure Leskovec, Carlos Guestrin, Jeanne VanBriesen, and Christos Faloutsos.  Efficient sensor placement optimization for securing large water distribution networks.  Journal of Water Resources Planning and Management, 134(6):516–526, 2008.
  * [KLQ95] Chun-Wa Ko, Jon Lee, and Maurice Queyranne.  An exact algorithm for maximum entropy sampling.  Operations Research, 43(4):684–691, 1995.
  * [KST09] Ariel Kulik, Hadas Shachnai, and Tami Tamir.  Maximizing submodular set functions subject to multiple linear constraints.  In Proceedings of the twentieth annual ACM-SIAM symposium on Discrete algorithms, pages 545–554. SIAM, 2009.
  * [KST13] Ariel Kulik, Hadas Shachnai, and Tami Tamir.  Approximations for monotone and nonmonotone submodular maximization with knapsack constraints.  Mathematics of Operations Research, 38(4):729–739, 2013.
  * [LB10] Hui Lin and Jeff Bilmes.  Multi-document summarization via budgeted maximization of submodular functions.  In Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics, pages 912–920, 2010.
  * [LMNS10] Jon Lee, Vahab S Mirrokni, Viswanath Nagarajan, and Maxim Sviridenko.  Maximizing nonmonotone submodular functions under matroid or knapsack constraints.  SIAM Journal on Discrete Mathematics, 23(4):2053–2078, 2010.
  * [LSV10] Jon Lee, Maxim Sviridenko, and Jan Vondrák.  Submodular maximization over multiple matroids via generalized exchange properties.  Mathematics of Operations Research, 35(4):795–806, 2010.
  * [NW78] George L Nemhauser and Laurence A Wolsey.  Best algorithms for approximating the maximum of a submodular set function.  Mathematics of operations research, 3(3):177–188, 1978.
  * [NWF78] George L Nemhauser, Laurence A Wolsey, and Marshall L Fisher.  An analysis of approximations for maximizing submodular set functions—i.  Mathematical programming, 14(1):265–294, 1978.
  * [Osh21] Hiroki Oshima.  Improved randomized algorithm for $k$-submodular function maximization.  SIAM Journal on Discrete Mathematics, 35(1):1–22, 2021.
  * [OY15] Naoto Ohsaka and Yuichi Yoshida.  Monotone $k$-submodular function maximization with size constraints.  Advances in Neural Information Processing Systems, 28:694–702, 2015\.
  * [Sak17] Shinsaku Sakaue.  On maximizing a monotone $k$-submodular function subject to a matroid constraint.  Discrete Optimization, 23:105–113, 2017.
  * [SGW20] Ganquan Shi, Shuyang Gu, and Weili Wu.  k-submodular maximization with two kinds of constraints.  Discrete Mathematics, Algorithms and Applications, page 2150036, 2020.
  * [Svi04] Maxim Sviridenko.  A note on maximizing a submodular set function subject to a knapsack constraint.  Operations Research Letters, 32(1):41–43, 2004.
  * [TWC21] Zhongzheng Tang, Chenhao Wang, and Hau Chan.  On maximizing a monotone $k$-submodular function under a knapsack constraint.  arXiv preprint arXiv:2105.15159, 2021.
  * [WŽ16] Justin Ward and Stanislav Živnỳ.  Maximizing $k$-submodular functions and beyond.  ACM Transactions on Algorithms, 12(4):1–26, 2016.

##  Appendix A Proof of the properties of the multilinear extension

###### Proof of Proposition 3.

#### Multilinearity

Taking derivative of (1) with respect to $x_{i,j}$,

$\displaystyle\frac{\partial F}{\partial x_{i,j}}=$
$\displaystyle\sum\limits_{i\in
S_{j}}f(S_{1},\dots,S_{k})\prod\limits_{t\in[k]}\prod\limits_{l\in S_{t}\atop
l\neq i}x_{l,t}\prod\limits_{l\in V\setminus
S}\Big{(}1-\sum\limits_{t=1}^{k}x_{l,t}\Big{)}$
$\displaystyle-\sum\limits_{i\notin
S}f(S_{1},\dots,S_{k})\prod\limits_{t\in[k]}\prod\limits_{l\in
S_{t}}x_{l,t}\prod\limits_{l\in V\setminus S\atop l\neq
i}\Big{(}1-\sum\limits_{t=1}^{k}x_{l,t}\Big{)}\,.$

As both the terms do not depend on $x_{i,j}$, the derivative is constant when
other coordinates are fixed.

#### Element-wise non-positive Hessian

Taking the second-order derivative of (1) with respect to $x_{i_{1},j_{1}}$
and $x_{i_{2},j_{2}}$,

$\displaystyle\begin{split}\frac{\partial^{2}F}{\partial
x_{i_{1},j_{1}}\partial x_{i_{2},j_{2}}}=&\sum\limits_{i_{1}\in S_{j_{1}}\atop
i_{2}\in
S_{j_{2}}}f(S_{1},\dots,S_{k})\prod\limits_{t\in[k]}\prod\limits_{l\in
S_{t}\atop l\neq i_{1},i_{2}}x_{l,t}\prod\limits_{l\in V\setminus
S}\Big{(}1-\sum\limits_{t=1}^{k}x_{l,t}\Big{)}\\\ &-\sum\limits_{i_{1}\notin
S\atop i_{2}\in
S_{j_{2}}}f(S_{1},\dots,S_{k})\prod\limits_{t\in[k]}\prod\limits_{l\in
S_{t}\atop l\neq i_{2}}x_{l,t}\prod\limits_{l\in V\setminus S\atop l\neq
i_{1}}\Big{(}1-\sum\limits_{t=1}^{k}x_{l,t}\Big{)}\\\ &-\sum\limits_{i_{1}\in
S_{j_{1}}\atop i_{2}\notin
S}f(S_{1},\dots,S_{k})\prod\limits_{t\in[k]}\prod\limits_{l\in S_{t}\atop
l\neq i_{1}}x_{l,t}\prod\limits_{i\in V\setminus S\atop l\neq
i_{2}}\Big{(}1-\sum\limits_{t=1}^{k}x_{l,t}\Big{)}\\\
&+\sum\limits_{i_{1}\notin S\atop i_{2}\notin
S}f(S_{1},\dots,S_{k})\prod\limits_{t\in[k]}\prod\limits_{l\in
S_{t}}x_{l,t}\prod\limits_{l\in V\setminus S\atop l\neq
i_{1},i_{2}}\Big{(}1-\sum\limits_{t=1}^{k}x_{l,t}\Big{)}\,.\end{split}$ (6)

If $i_{1}\neq i_{2}$, for every subset tuple $S=S_{1}\uplus\dots\uplus S_{k}$
such that $i_{1},i_{2}\notin S$ which is in the fourth term, we can find a
subset tuple $S^{1}$ such that

$S^{1}=S_{1}\uplus\dots\uplus
S_{j_{1}-1}\uplus(S_{j_{1}}\cup\\{i_{1}\\})\uplus S_{j_{1}+1}\uplus\dots\uplus
S_{k}\,,$

in the third sum, and a subset tuple $S^{2}$ such that,

$S^{2}=S_{1}\uplus\dots\uplus
S_{j_{2}-1}\uplus(S_{j_{2}}\cup\\{i_{2}\\})\uplus S_{j_{2}+1}\uplus\dots\uplus
S_{k}\,,$

in the second sum, and a subset tuple $S^{0}$ such that

$S^{0}=S_{1}\uplus\dots\uplus
S_{j_{1}-1}\uplus(S_{j_{1}}\cup\\{i_{1}\\})\uplus S_{j_{1}+1}\uplus\dots\uplus
S_{j_{2}-1}\uplus(S_{j_{2}}\cup\\{i_{2}\\})\uplus S_{j_{2}+1}\uplus\dots\uplus
S_{k}\,,$

assuming $j_{1}\leq j_{2}$ without loss of generality. Thus we have
$S^{1}\sqcap S^{2}=S$ and $S^{1}\sqcup S^{2}=S^{0}$. Due to submodularity, we
have

$f(S^{0})+f(S)-f(S^{1})-f(S^{2})\leq 0\,,$

which implies that

$\frac{\partial^{2}F}{\partial x_{i_{1},j_{1}}\partial x_{i_{2},j_{2}}}\leq
0\,.$

If $i_{1}=i_{2}=i$, by the multilinearity we have

$\frac{\partial^{2}F}{\partial x_{i,j_{1}}\partial x_{i,j_{2}}}=0\,.$

#### Pairwise monotonicity

Taking derivative of (1),

$\displaystyle\frac{\partial F}{\partial x_{i,j_{1}}}+\frac{\partial
F}{\partial x_{i,j_{2}}}=$ $\displaystyle\sum\limits_{i\in
S_{j_{1}}}f(S_{1},\dots,S_{k})\prod\limits_{t\in[k]}\prod\limits_{l\in
S_{t}\atop l\neq i}x_{l,t}\prod\limits_{l\in V\setminus
S}\Big{(}1-\sum\limits_{t=1}^{k}x_{l,t}\Big{)}$
$\displaystyle-\sum\limits_{i\notin
S}f(S_{1},\dots,S_{k})\prod\limits_{t\in[k]}\prod\limits_{l\in
S_{t}}x_{l,t}\prod\limits_{l\in V\setminus S\atop l\neq
i}\Big{(}1-\sum\limits_{t=1}^{k}x_{l,t}\Big{)}$
$\displaystyle\sum\limits_{i\in
S_{j_{2}}}f(S_{1},\dots,S_{k})\prod\limits_{t\in[k]}\prod\limits_{l\in
S_{t}\atop l\neq i}x_{l,t}\prod\limits_{l\in V\setminus
S}\Big{(}1-\sum\limits_{t=1}^{k}x_{l,t}\Big{)}$
$\displaystyle-\sum\limits_{i\notin
S}f(S_{1},\dots,S_{k})\prod\limits_{t\in[k]}\prod\limits_{l\in
S_{t}}x_{l,t}\prod\limits_{l\in V\setminus S\atop l\neq
i}\Big{(}1-\sum\limits_{t=1}^{k}x_{l,t}\Big{)}\,.$

For every set tuple $S=S_{1}\uplus\dots\uplus S_{k}$ such that $i\notin S$,
which is in the second term and the fourth term, we can find a set tuple
$S^{1}$ such that

$S^{1}=S_{1}\uplus\dots\uplus S_{j_{1}-1}\uplus(S_{j_{1}}\cup\\{i\\})\uplus
S_{j_{1}+1}\uplus\dots\uplus S_{k}$

in the first term, and a set tuple $S^{2}$ such that

$S^{2}=S_{1}\uplus\dots\uplus S_{j_{2}-1}\uplus(S_{j_{2}}\cup\\{i\\})\uplus
S_{j_{2}+1}\uplus\dots\uplus S_{k}$

in the third term. By the (discrete) pairwise monotonicity (2) of
$k$-submodular functions, we have

$S^{1}-S+S^{2}-S=\Delta_{i,j_{1}}f(S)+\Delta_{i,j_{2}}f(S)\geq 0\,.$

Thus

$\frac{\partial F}{\partial x_{i,j_{1}}}+\frac{\partial F}{\partial
x_{i,j_{2}}}\geq 0\,.$

#### Approximate linearity

Since $F$ is polynomial in $\mathbf{x}$, by Taylor’s Theorem we can expand
$F(\mathbf{x}^{\prime})$ at $F(\mathbf{x})$ as

$\displaystyle F(\mathbf{x}^{\prime})-F(\mathbf{x})$
$\displaystyle=(\mathbf{x}^{\prime}-\mathbf{x})^{T}\nabla
F(\mathbf{x})+\dfrac{1}{2}(\mathbf{x}^{\prime}-\mathbf{x})^{T}H(\mathbf{x})(\mathbf{x}^{\prime}-\mathbf{x})+O(\|\mathbf{x}^{\prime}-\mathbf{x}\|^{3})$
$\displaystyle=(\mathbf{x}^{\prime}-\mathbf{x})^{T}\nabla
F(\mathbf{x})+\dfrac{1}{2}(\mathbf{x}^{\prime}-\mathbf{x})^{T}H(\mathbf{x})(\mathbf{x}^{\prime}-\mathbf{x})+O(k^{\frac{3}{2}}n^{\frac{3}{2}}\delta^{3})\,,$

where $H(\mathbf{x})$ is the Hessian matrix. Now we consider an element
$\frac{\partial^{2}F}{\partial x_{i_{1},j_{1}}\partial x_{i_{2},j_{2}}}$ in
$H(\mathbf{x})$. By Equation (6), we have

$\lvert\frac{\partial^{2}F}{\partial x_{i_{1},j_{1}}\partial
x_{i_{2},j_{2}}}\rvert\leq 4\max f(S_{1},\dots,S_{k})\leq
4n\max\limits_{i,j}\Delta_{i,j}f(\emptyset)\,,$

where the last inequality uses the assumption that $f$ is non-negative. Thus
$\lvert\dfrac{1}{2}(\mathbf{x}^{\prime}-\mathbf{x})^{T}H(\mathbf{x})(\mathbf{x}^{\prime}-\mathbf{x})+O(k^{\frac{3}{2}}n^{\frac{3}{2}}\delta^{3})\rvert\leq\dfrac{1}{2}k^{2}n^{2}\cdot
4n\cdot\delta^{2}\max\limits_{i,j}\Delta_{i,j}f(\emptyset)+O(k^{\frac{3}{2}}n^{\frac{3}{2}}\delta^{3})=O(k^{3}n^{3}\delta^{2})\max\limits_{i,j}\Delta_{i,j}f(\emptyset)$,
for sufficiently small $\delta$. Therefore,

$F(\mathbf{x}^{\prime})-F(\mathbf{x})\geq\sum\limits_{i\in[n],j\in[k]}(x^{\prime}_{i,j}-x_{i,j})\cdot\partial_{i,j}F(\mathbf{x})-O(k^{3}n^{3}\delta^{2})\max\limits_{i,j}\Delta_{i,j}f(\emptyset)\,.$

#### Monotonicity under monotonicity

As

$\displaystyle\frac{\partial F}{\partial x_{i,j}}=$
$\displaystyle\sum\limits_{i\in
S_{j}}f(S_{1},\dots,S_{k})\prod\limits_{t\in[k]}\prod\limits_{l\in S_{t}\atop
l\neq i}x_{l,t}\prod\limits_{l\in V\setminus
S}\Big{(}1-\sum\limits_{t=1}^{k}x_{l,t}\Big{)}$
$\displaystyle-\sum\limits_{i\notin
S}f(S_{1},\dots,S_{k})\prod\limits_{t\in[k]}\prod\limits_{l\in
S_{t}}x_{l,t}\prod\limits_{l\in V\setminus S\atop l\neq
i}\Big{(}1-\sum\limits_{t=1}^{k}x_{l,t}\Big{)}\,,$

for every set tuple $S=S_{1}\uplus\dots\uplus S_{k}$ such that $i\notin S$,
which is in the second term, we can find $S^{\prime}$ such that

$S^{\prime}=S_{1}\uplus\dots\uplus S_{j-1}\uplus(S_{j}\cup\\{i\\})\uplus
S_{j+1}\uplus\dots\uplus S_{k}$

in the first term. When $f$ is monotone (assume that $f$ is increasing without
loss of generality), we have $f(S^{\prime})\geq f(S)$. Thus $\frac{\partial
F}{\partial x_{i,j}}\geq 0$, for all $i\in[n]$ and $j\in[k]$, which indicates
that $F$ is also monotone as desired. ∎

##  Appendix B Chernoff-like lemmas for approximate oracle

Given only oracle access to $k$-submodular function $f$, the following
Chernoff-like theorem allows us to approximate the value of the multilinear
extension $F$ to an arbitrary accuracy.

######  Lemma 14.

If $F$ is the multilinear extension of $f$, $\mathbf{x}\in\mathcal{P}$, and
$R_{1},\dots,R_{t}$ are independent samples of random sets as, then

$\left|\dfrac{1}{t}\sum\limits_{i=1}^{t}f(R_{i})-F(\mathbf{x})\right|\leq\epsilon|\max
f(S)|$

with probability at least $1-e^{-t\epsilon^{2}/4}$.

With this approximation, the value of the gradient of $F$ can also be
approximated.

######  Corollary 15.

Let $F$ be the multilinear extension of $f$ and
$\mathbf{x},~{}\mathbf{x}+\delta e_{i,j}\in\mathcal{P}$. If
$R_{1},\dots,R_{t}$ are independent samples of random sets at point
$\mathbf{x}$ while $S_{1},\dots,S_{t}$ are independent samples of random sets
at point $\mathbf{x}+\delta e_{i,j}$, then

$\left|\frac{\frac{1}{t}\sum\limits_{i=1}^{t}f(R_{i})-\dfrac{1}{t}\sum\limits_{i=1}^{t}f(S_{i})}{\delta}-\frac{\partial
F(\mathbf{x})}{\partial\mathbf{x}_{i,j}}\right|\leq\frac{2\epsilon}{\delta}|\max
f(S)|$

with probability at least $1-2e^{-t\epsilon^{2}/4}$.

##  Appendix C Proof of maximizing monotone $F$ under knapsack constraint

###### Proof of Theorem 9.

Suppose the optimal solution of original $k$-submodular function maximization
problem is $\mathbf{o}^{*}\in\\{0,1\\}^{kV}$.Define
$O_{i}^{*}=\\{i\in[n]:\exists j\in[k]\mbox{ such that }\mathbf{o}_{i,j}=1\\}$
and assume some fixed order in $O_{i}^{*}$ when it is enumerated over. Recall
that $j_{i}^{*}\in[k]$ is defined as the index $j\in[k]$ such that
$\mathbf{o}_{i,j}=1$.

For each iteration’s output $\mathbf{s}(t)$, we construct a point
$\mathbf{o}(t)$ on the boundary of the polytope by the following procedure.
This procedure is only for the analysis.

Algorithm 5 Construction of $\mathbf{o}(t)$

1:$\mathbf{s}(t)$; knapsack $c_{i}$, $B$; $\mathbf{o}^{*}$ and $O_{i}^{*}$.

2:Set $\mathbf{o}_{i,j}(t)=\mathbf{s}_{i,j}(t)$ initially

3:Compute knapsack residual
$res_{B}=B-\sum\limits_{i\in[n]}c_{i}\sum\limits_{j\in[k]}\mathbf{o}_{i,j}(t)$

4:for $i\in O_{i}^{*}$ with fixed order do

5: Compute element residual
$res_{i}=1-\sum\limits_{j\in[k]}\mathbf{o}_{i,j}(t)$

6: if $res_{i}\cdot c_{i}\leq res_{B}$ then

7: $\mathbf{o}_{i,j_{i}^{*}}(t)=1-\sum\limits_{j\neq
j_{i}^{*}}\mathbf{o}_{i,j}(t)$

8:
$res_{B}=B-\sum\limits_{i\in[n]}c_{i}\sum\limits_{j\in[k]}\mathbf{o}_{i,j}(t)$

9: else

10: Set $\mathbf{o}_{i,j_{i}^{*}}(t)=\dfrac{res_{B}}{c_{i}}$ and break the for
loop return Sequence $\mathbf{o}(t)$

For every $\mathbf{o}_{i,j}(t+1)$ and $\mathbf{o}_{i,j}(t)$, we construct such
sequence denoted as

$(\mathbf{o}^{0},\dots,\mathbf{o}^{m})=(\mathbf{o}^{0},\mathbf{o}^{1,1},\dots,\mathbf{o}^{1,k},\dots,\mathbf{o}^{n,1},\dots,\mathbf{o}^{n,k})$

by Algorithm 2. And we decompose
$F(\mathbf{o}_{i,j}(t))-F(\mathbf{o}_{i,j}(t+1))$ into
$F(\mathbf{o}(t))-F(\mathbf{o}(t+1))=\sum\limits_{l=0}^{m-1}\left(F(\mathbf{o}^{l+1})-F(\mathbf{o}^{l})\right)$.

Denote, in the $t$-th iteration, the move direction as $(i(t),j(t))$. Now we
discuss the influence of the move from $\mathbf{o}(t+1)$ to $\mathbf{o}(t)$.
Specifically, we compare $\mathbf{o}(t)$ and $\mathbf{o}(t+1)$ in every
coordinate. The movement from $\mathbf{s}(t)$ to $\mathbf{s}(t+1)$ can be
viewed as the shrinking of budget in Algorithm 5 while
$\mathbf{o}_{i(t),j(t)}(t)$ is increased. This can be exhausted by two cases.

  1. 1.

If $i(t)\notin O_{i}^{*}$ or $i(t)$ has not been chosen in Algorithm 5, then
the only influences is the budget shrinking. Denote the indexes affected by
the budget shrinking as $i_{s}^{1},\dots,i_{s}^{m_{s}}$ in $O_{i}^{*}$, and
let $\mathbf{o}_{i_{s}^{l},z_{s}^{l}}$ decrease by $\delta_{i_{s}^{l}}$, where
$z_{s}^{l}$ denotes $j_{i_{s}^{l}}^{*}$. By definition
$c_{i(t)}\delta=\sum\limits_{l=1}^{m_{s}}c_{i_{s}^{l}}\delta_{i_{s}^{l}}$.
Then

$\displaystyle\sum\limits_{l=0}^{m-1}\left(F(\mathbf{o}^{l+1})-F(\mathbf{o}^{l})\right)=$
$\displaystyle\sum\limits_{l=1}^{m_{s}}\delta_{i_{s}^{l}}\partial_{i_{s}^{l},z_{s}^{l}}F(\mathbf{o}^{i_{s}^{l},1})-\delta\partial_{i(t),j(t)}F(\mathbf{o}^{i(t),1})$
$\displaystyle\leq$
$\displaystyle\sum\limits_{l=1}^{m_{s}}\delta_{i_{s}^{l}}\partial_{i_{s}^{l},z_{s}^{l}}F(\mathbf{s}(t))$
$\displaystyle=$
$\displaystyle\sum\limits_{l=1}^{m_{s}}\delta_{i_{s}^{l}}c_{i_{s}^{l}}\frac{\partial_{i_{s}^{l},z_{s}^{l}}F(\mathbf{s}(t))}{c_{i_{s}^{l}}}$
$\displaystyle\leq$
$\displaystyle\sum\limits_{l=1}^{m_{s}}\delta_{i_{s}^{l}}c_{i_{s}^{l}}\frac{\partial_{i(t),j(t)}F(\mathbf{s}(t))}{c_{i(t)}}=\delta\partial_{i(t),j(t)}F(\mathbf{s}(t))\,.$

  2. 2.

If $i(t)\in O_{i}^{*}$ and $i(t)$ has been chosen in Algorithm 5, the the move
shrinks the upper bound $1-\sum\limits_{j}\mathbf{o}_{i(t),j}(t)$ and the
budget simultaneously. It is important to observe that the upper bound shrinks
as fast as budget does. Equivalently, $\delta\cdot c_{i(t)}=\delta\cdot
c_{i(t)}$. The left part denotes the shrinking of the upper bound
$1-\sum\limits_{j}\mathbf{o}_{i(t),j}(t)$ which release $\delta\cdot c_{i(t)}$
budget to other $i$, while the right part denotes the shrinking of the budget
influenced by the increasing at coordinate $(i(t),j(t))$. Then all influenced
coordinate will not increase. Similarly,

$\displaystyle\sum\limits_{l=0}^{m-1}\left(F(\mathbf{o}^{l+1})-F(\mathbf{o}^{l})\right)\leq\delta\partial_{i(t),j(t)}F(\mathbf{s}(t))\,.$

Then, In either of the cases

$F(\mathbf{o}(t))-F(\mathbf{o}(t+1))\leq\delta\partial_{i(t),j(t)}F(\mathbf{s}(t))=\mathbf{s}(t+1)-\mathbf{s}(t)\,,$

where the equality is by the multilinearity. As we have defined that
$\mathbf{o}(0)=\mathbf{o}^{*}$ and $\mathbf{o}(T)=\mathbf{s}(T)$, we conclude
that

$\frac{1}{2}F(\mathbf{o}^{*})\leq F(\mathbf{s}(T))-F(\mathbf{s}(0))\leq
F(\mathbf{s}(T))\,.\qed$

##  Appendix D Proof of lower-tail bound

In this section, we prove Lemma 12, which is an exponential estimate for the
lower tail of the distribution of a monotone $k$-submodular function under
randomized swap rounding. This proof is obtained by sightly modifying the
proof in Appendix D of [CVZ09]. In fact, the proof in [CVZ09] only uses the
decreasing of the first derivative (submodularity) and the cross-convexity of
$F$. Thus for $k$-submodular functions the multilinear extension maintain
these two properties and the proof can be adopted. Meanwhile, since the domain
of $F$ can be viewed as the polytope of the partition matroid, we can apply
the proof directly.

We first note that the bound $\mathbb{E}[f(R)]\geq\mu_{0}$ on the expected
value of the rounded solution. This follows the fact that $F$ is convex along
any line of the direction $e_{i_{1},j_{1}}-e_{i_{2},j_{2}}$ for
$i_{1},i_{2}\in[n]$ and $j_{1},j_{2}\in[k]$, as pointed out in [AS04, CCPV07].

Before we proceed to the Chernoff-like bound, we introduce some notations. The
rounding procedure (swap rounding) starts from a linear combination of the
bases $\mathbf{x}_{0}=\sum\limits_{i=1}^{nk}\beta_{i}\mathbf{1}_{B_{i}}$. The
rounding proceeds in stages. In the first stage we merge two bases randomly
(without loss of generality denoted as $B_{1},B_{2}$) into a new base $C_{2}$,
and replace $\beta_{1}\mathbf{1}_{B_{1}}+\beta_{2}\mathbf{1}_{B_{2}}$ in the
linear combination by $\gamma_{2}\mathbf{1}_{C_{2}}$, with
$\gamma_{2}=\beta_{1}+\beta_{2}$. In general, in the $l$-th stage, we merge
$C_{l}$ and $B_{l+1}$ into a new base $C_{l+1}$ (set $C_{1}=B_{1}$ in the
first stage), and replace
$\gamma_{l}\mathbf{1}_{C_{l}}+\beta_{l+1}\mathbf{1}_{B_{l+1}}$ in the linear
combination by $\gamma_{l+1}\mathbf{1}_{C_{l+1}}$. Inductively,
$\gamma_{l+1}=\gamma_{l}+\beta_{l+1}=\sum\limits_{i=1}^{l+1}\beta_{i}$. After
$nk-1$ stages, we obtain a linear combination $\gamma_{nk}\mathbf{1}_{C_{nk}}$
and $\gamma_{nk}=1$, which is an integer solution. Denote that
$\mathbf{b}_{i}=\beta_{i}\mathbf{1}_{B_{i}}$,
$\mathbf{c}_{i}=\gamma_{i}\mathbf{1}_{C_{i}}$,
$\mathbf{y}_{l}=\sum\limits^{nk}_{i=l}\mathbf{b}_{i}=\sum\limits^{nk}_{i=l}\beta_{i}\mathbf{1}_{B_{i}}$,
$\mathbf{x}_{l}=\mathbf{c}_{l+1}+\mathbf{y}_{l+2}=\gamma_{l+1}\mathbf{1}_{C_{l+1}}+\sum\limits^{nk}_{i=l+2}\beta_{i}\mathbf{1}_{B_{i}}$,
where $\mathbf{b}_{i}$ are the initial vectors in the linear combination and
are gradually replaced by $\mathbf{c}_{i}$ and $\mathbf{x}_{l}$ is the
fractional solution after $l$ stages.

We note that $\mathbf{x}_{l}$ denotes the entire fractional solution at a
certain stage and not to be confused with the value of its $l$-th coordinate.
The coordinates of the fractional solution are denoted by $X_{i,j}$. The value
of $X_{i,j}$ after $l$ stages is referred to as $X_{i,j}^{l}$. Denote
$\frac{\partial F}{\partial x_{i,j}}$ as $F_{i,j}$.

######  Lemma 16 (Chekuri, Vondrák, and Zenklusen [CVZ09]).

For any $p\in[0,1]$ and $\eta\in[-1,1]$,

$pe^{\eta(1-p)}+(1-p)e^{-\eta p}\leq e^{\eta^{2}p(1-p)}\,.$

We now apply this lemma to each step of the rounding procedure.

######  Lemma 17.

Let $F(\mathbf{x})$ be the multilinear extension of a monotone $k$-submodular
function with marginal values in $[0,1]$. Let $\lambda\in[0,1]$. Consider one
elementary operation of randomized swap rounding, where two variables
$X_{i_{1},j_{1}}$, $X_{i_{2},j_{2}}$ are modified. Let $\mathbf{x}$ denote the
fractional solution before, $\mathbf{x}^{\prime}$ after this step, and let
$\mathcal{H}$ denote the complete history prior to this rounding step. Denote
the values of the two variables before the rounding step as
$X_{i_{1},j_{1}}=\gamma,X_{i_{2},j_{2}}=\beta$. Then,

$\mathbb{E}[e^{\lambda(F(\mathbf{x})-F(\mathbf{x}^{\prime}))}|\mathcal{H}]\leq
e^{\lambda^{2}\beta\gamma(F_{i_{2},j_{2}}(\mathbf{x})-F_{i_{1},j_{1}}(\mathbf{x}))^{2}}\,.$

###### Proof.

Fix the history $\mathcal{H}$, which includes the point $\mathbf{x}$ before
the rounding step. With probability $p=\frac{\gamma}{\beta+\gamma}$ the
rounding step is $X_{i_{1},j_{1}}^{\prime}=X_{i_{1},j_{1}}+\beta$ and
$X_{i_{2},j_{2}}^{\prime}=X_{i_{2},j_{2}}-\beta$. In other words,
$\mathbf{x}^{\prime}=\mathbf{x}+\beta e_{i_{1},j_{1}}-\beta e_{i_{2},j_{2}}$.
Since $F(\mathbf{x})$ is linear when only one coordinate is modified, we have

$F(\mathbf{x}^{\prime})=F(\mathbf{x})+\beta F_{i_{1},j_{1}}(\mathbf{x})-\beta
F_{i_{2},j_{2}}(\mathbf{x}+\beta e_{i_{1},j_{1}})\,.$

By the submodularity, $F_{i_{2},j_{2}}(\mathbf{x}+\beta e_{i_{1},j_{1}})\leq
F_{i_{2},j_{2}}(\mathbf{x})$, and subsequently

$F(\mathbf{x}^{\prime})=F(\mathbf{x})+\beta F_{i_{1},j_{1}}(\mathbf{x})-\beta
F_{i_{2},j_{2}}(\mathbf{x}+\beta e_{i_{1},j_{1}})\geq F(\mathbf{x})+\beta
F_{i_{1},j_{1}}(\mathbf{x})-\beta F_{i_{2},j_{2}}(\mathbf{x})\,.$

With probability $1-p$, we set
$X_{i_{1},j_{1}}^{\prime}=X_{i_{1},j_{1}}-\gamma$ and
$X_{i_{2},j_{2}}^{\prime}=X_{i_{2},j_{2}}+\gamma$. By similar arguments, in
this case we have

$F(\mathbf{x}^{\prime})=F(\mathbf{x})-\gamma
F_{i_{1},j_{1}}(\mathbf{x})+\gamma F_{i_{2},j_{2}}(\mathbf{x}-\gamma
e_{i_{1},j_{1}})\geq F(\mathbf{x})-\gamma F_{i_{1},j_{1}}(\mathbf{x})+\gamma
F_{i_{2},j_{2}}(\mathbf{x})\,.$

Taking expectation over the two cases, we obtain

$\displaystyle\mathbb{E}[e^{\lambda(F(\mathbf{x})-F(\mathbf{x}^{\prime}))}|\mathcal{H}]$
$\displaystyle\leq
pe^{\lambda\beta(F_{i_{2},j_{2}}(\mathbf{x})-F_{i_{1},j_{1}}(\mathbf{x}))}+(1-p)e^{-\lambda\gamma(F_{i_{2},j_{2}}(\mathbf{x})-F_{i_{1},j_{1}}(\mathbf{x}))}$
$\displaystyle=pe^{\lambda(1-p)(\beta+\gamma)(F_{i_{2},j_{2}}(\mathbf{x})-F_{i_{1},j_{1}}(\mathbf{x}))}+(1-p)e^{-\lambda
p(\beta+\gamma)(F_{i_{2},j_{2}}(\mathbf{x})-F_{i_{1},j_{1}}(\mathbf{x}))}$
$\displaystyle\leq
e^{\lambda^{2}\beta\gamma(F_{i_{2},j_{2}}(\mathbf{x})-F_{i_{1},j_{1}}(\mathbf{x}))^{2}}\,.$
∎

######  Lemma 18.

Let $F(\mathbf{x})$ be the multilinear extension of a monotone $k$-submodular
function with marginal values in $[0,1]$. Let $\lambda\in[0,1]$. Consider the
$l$-th stage of the rounding process, where the bases $C_{l}$ and $B_{l+1}$
(with coefficients $\gamma_{l}$ and $\beta_{l+1}$, respectively) are merged
into $C_{l+1}$. Denote the fractional solution before this stage as
$\mathbf{x}_{l-1}$ and after this stage as $\mathbf{x}_{l}$. Conditioned on
any history $\mathcal{H}$ of the rounding process throughout the first $l-1$
stages,

$\mathbb{E}[e^{\lambda(F(\mathbf{x}_{l-1})-F(\mathbf{x}_{l}))}|\mathcal{H}]\leq
e^{\lambda^{2}(\beta_{l+1}F(\mathbf{c}_{l})+\gamma_{l}(F(\mathbf{y}_{l+1})-F(\mathbf{y}_{l+2})))}\,.$

###### Proof.

The $l$-th stage merges the bases $C_{l}$ and $B_{l+1}$ into $C_{l+1}$ by
taking elements in pairs and performing rounding steps as is in Lemma 17.
Denote the pairs of elements considered by the rounding procedure as
$(c_{1},b_{1}),\dots,(c_{d},b_{d})$, where $C_{l}=\\{c_{1},\dots,c_{d}\\}$ and
$B_{l+1}=\\{b_{1},\dots,b_{d}\\}$. The matching is not determined beforehand:
$(c_{2},b_{2})$ might depend on the random choice between $c_{1},b_{1}$ and so
forth. In the following, we drop the index $l$ and denote by $\mathbf{x}^{i}$
the fractional solution obtained after processing
$(c_{1},b_{1}),\dots,(c_{i},b_{i})$. We start with
$\mathbf{x}^{0}=\mathbf{x}^{l-1}$ and after processing all the $d$ pairs we
obtain $\mathbf{x}^{d}=\mathbf{x}_{l}$. We also replace
$\beta_{l+1},\gamma_{l}$ by $\beta$, $\gamma$ for simplicity. Denote by
$\mathcal{H}_{i}$ the complete history prior to the rounding step involving
$(c_{i+1},b_{i+1})$. In particular, this includes the fractional solution
$\mathbf{x}^{i}$.

Using Lemma 17 for the rounding step involving $(c_{i+1},b_{i+1})$, we have

$\mathbb{E}[e^{\lambda(F(\mathbf{x}^{i})-F(\mathbf{x}^{i+1}))}|\mathcal{H}_{i}]\leq
e^{\lambda^{2}\beta\gamma(F_{c_{i+1}}(\mathbf{x}^{i})-F_{b_{i+1}}(\mathbf{x}^{i}))^{2}}\leq
e^{\lambda^{2}\beta\gamma(F_{c_{i+1}}(\mathbf{x}^{i})+F_{b_{i+1}}(\mathbf{x}^{i}))}\,,$

where we use the fact that the partial derivatives $F_{i,j}(\mathbf{x}^{i})$
are bounded by the marginal values and are hence in $[0,1]$.

Further, we modify the exponent of the right-hand side as follows. The vector
$\mathbf{x}^{i}$ is obtained after processing $i$ pairs and still contains the
coordinates $c_{i+1},\dots,c_{d}$ of $\mathbf{c}_{l}=\gamma\mathbf{1}_{C_{l}}$
intact. In other words, $\mathbf{x}^{i}\geq\gamma
1_{\\{}c_{i+1},\dots,c_{d}\\}$. Define
$\mathbf{c}^{i}=\gamma\mathbf{1}_{\\{c_{i+1},\dots,c_{d}\\}}$. Then,
$\mathbf{x}^{i}\geq\mathbf{c}^{i}\geq\mathbf{c}^{i+1}$. By the submodularity,
we have $F_{c_{i+1}}(\mathbf{x}^{i})\leq F_{c_{i+1}}(\mathbf{c}^{i+1})$.

Similarly, the vector $\mathbf{x}^{i}$ also contains the coordinates
$b_{i+1},\dots,b_{d}$ of $\mathbf{b}_{l+1}$ and all of
$\mathbf{y}_{l+2}=\sum\limits_{v=l+2}^{n}\mathbf{b}_{v}$ intact. And
$\mathbf{x}^{i}\geq\beta_{1}\\{b_{i+1},\dots,b_{d}\\}+\mathbf{y}^{l+2}$.
Define
$\mathbf{y}^{i}=\beta\mathbf{1}_{\\{b_{i+1},\dots,b_{d}\\}}+\mathbf{y}_{l+2}$.
In other words, $\mathbf{x}^{i}\geq\mathbf{y}^{i}\geq\mathbf{y}^{i+1}$. By the
submodularity, we get $F_{b_{i+1}}(\mathbf{x}^{i})\leq
F_{b_{i+1}}(\mathbf{y}^{i+1})$. Therefore,

$\mathbb{E}[e^{\lambda(F(\mathbf{x}^{i})-F(\mathbf{x}^{i+1}))}|\mathcal{H}_{i}]\leq
e^{\lambda^{2}\beta\gamma(F_{c_{i+1}}(\mathbf{c}^{i+1})+F_{b_{i+1}}(\mathbf{y}^{i+1}))}\,.$

By induction on $d-i$, this implies that

$\mathbb{E}[e^{\lambda(F(\mathbf{x}^{i})-F(\mathbf{x}^{d}))}|\mathcal{H}_{i}]\leq
e^{\lambda^{2}(\beta
F(\mathbf{c}^{i+1})+\gamma(F(\mathbf{y}^{i})-F(\mathbf{y}^{d})))}\,.$

For the base case $i=0$, since
$\mathbf{x}^{0}=\mathbf{x}_{l-1},\mathbf{x}^{d}=\mathbf{x}_{l},\mathbf{c}^{0}=\mathbf{c}_{l},\mathbf{y}^{0}=\mathbf{y}_{l+1}$
and $\mathbf{y}^{d}=\mathbf{y}_{l+2}$, the statement is validated, and so does
the lemma. ∎

Armed with the lemmas, we finally proceed to the proof of the lower tail
bound.

###### Proof of Lemma 12.

We prove inductively the following statement:

$\mathbb{E}[e^{\lambda(\mu_{0}-F(\mathbf{x}_{l})}]\leq
e^{\lambda^{2}(\mu_{0}(1+\sum\limits_{i=1}^{l}\beta_{i+1})-F(\mathbf{y}_{l+2}))},\
\forall\lambda\in[0,1],l\,.$ (7)

Note that $\mu_{0}=F(\mathbf{x}_{0})$, $\mathbf{x}_{l}$ is the fractional
solution after $l$ stages, and
$\mathbf{y}_{l+2}=\sum\limits_{i=l+2}^{nk}\mathbf{b}_{i}$. We proceed by
induction on $l$.

For $l=0$, the claim is trivial, as $F(\mathbf{y}_{2})\leq
F(\mathbf{x}_{0})=\mu_{0}$ by the monotonicity. For $l\geq 1$, we unroll the
expectation as

$\mathbb{E}\left[e^{\lambda(\mu_{0}-F(\mathbf{x}_{l})}\right]=\mathbb{E}\left[e^{\lambda(\mu_{0}-F(\mathbf{x}_{l-1}))}\mathbb{E}\left[e^{\lambda(F(\mathbf{x}_{l-1})-F(\mathbf{x}_{l}))}\mid\mathcal{H}\right]\right]\,,$

where $\mathcal{H}$ is the complete history prior to stage $l$ (up to
$\mathbf{x}_{l-1}$). We estimate the inside expectation using Lemma 18 and the
monotonicity $\mathbf{c}_{l}\leq\mathbf{x}_{l-1}$,
$\mathbf{y}_{l+2}\leq\mathbf{y}_{l+1}$ and the fact $\gamma_{l}\leq 1$ as

$\mathbb{E}\left[e^{\lambda(F(\mathbf{x}_{l-1})-F(\mathbf{x}_{l}))}\mid\mathcal{H}\right]\leq
e^{\lambda^{2}(\beta_{l+1}F(\mathbf{c}_{l})+\gamma_{l}(F(\mathbf{y}_{l+1})-F(\mathbf{y}_{l+2})))}\leq
e^{\lambda^{2}(\beta_{l+1}F(\mathbf{x}_{l-1})+F(\mathbf{y}_{l+1})-F(\mathbf{y}_{l+2}))}\,.$

Therefore,

$\displaystyle\mathbb{E}\left[e^{\lambda(\mu_{0}-F(\mathbf{x}_{l})}\right]$
$\displaystyle=\mathbb{E}\left[e^{\lambda(\mu_{0}-F(\mathbf{x}_{l-1}))}\mathbb{E}\left[e^{\lambda(F(\mathbf{x}_{l-1})-F(\mathbf{x}_{l}))}\mid\mathcal{H}\right]\right]$
$\displaystyle\leq\mathbb{E}\left[e^{\lambda(\mu_{0}-F(\mathbf{x}_{l-1}))}e^{\lambda^{2}(\beta_{l+1}F(\mathbf{x}_{l-1})+F(\mathbf{y}_{l+1})-F(\mathbf{y}_{l+2}))}\right]$
$\displaystyle=e^{\lambda^{2}(\beta_{l+1}\mu_{0}+F(\mathbf{y}_{l+1}-F(\mathbf{y}_{l+2}))}\mathbb{E}\left[e^{(\lambda-\lambda^{2}\beta_{l+1})(\mu_{0}-F(\mathbf{x}_{l-1})}\right]\,.$

By the inductive hypothesis (7) with
$\lambda^{\prime}=\lambda-\lambda^{2}\beta_{l+1}\in[0,1]$,

$\mathbb{E}\left[e^{(\lambda-\lambda^{2}\beta_{l+1})(\mu_{0}-F(\mathbf{x}_{l-1})}\right]\leq
e^{(\lambda-\lambda^{2}\beta_{l+1})^{2}(\mu_{0}(1+\sum\limits_{i=1}^{l-1}\beta_{i+1})-F(\mathbf{y}_{l+1}))}\leq
e^{\lambda^{2}(\mu_{0}(1+\sum\limits_{i=1}^{l-1}\beta_{i+1})-F(\mathbf{y}_{l+1}))}\,.$

The last inequality is by the fact $F(\mathbf{y}_{l+1})\leq\mu_{0}$, which
holds by the monotonicity. Plugging this into the preceding equation,

$\displaystyle\mathbb{E}\left[e^{\lambda(\mu_{0}-F(\mathbf{x}_{l})}\right]$
$\displaystyle\leq
e^{\lambda^{2}(\beta_{l+1}\mu_{0}+F(\mathbf{y}_{l+1}-F(\mathbf{y}_{l+2}))}e^{\lambda^{2}(\mu_{0}(1+\sum\limits_{i=1}^{l-1}\beta_{i+1})-F(\mathbf{y}_{l+1}))}$
$\displaystyle=e^{\lambda^{2}(\mu_{0}(1+\sum\limits_{i=1}^{l}\beta_{i+1})-F(\mathbf{y}_{l+2}))}\,.$

By induction (7) is now proved.

Finally, for $l=nk-1$ we obtain $F(\mathbf{x}_{nk-1})=f(R)$ where $R$ is the
rounded solution, $\mathbf{y}_{nk+1}=0$, and by the fact that
$\sum\limits_{i=1}^{nk-1}\beta_{i+1}\leq 1$

$\mathbb{E}\left[e^{\lambda(\mu_{0}-f(R)}\right]\leq
e^{\lambda^{2}\mu_{0}(1+\sum\limits_{i=1}^{nk-1}\beta_{i+1})}\leq
e^{2\lambda^{2}\mu_{0}}\,.$

The final step is to apply Markov’s inequality to the exponential moment. By
Markov’s inequality, we obtain

$Pr\left[f(R)\leq(1-\delta)\mu_{0}\right]=Pr\left[e^{\lambda(\mu_{0}-f(R))}\geq
e^{\lambda\delta\mu_{0}}\right]\leq\frac{\mathbb{E}\left[e^{\lambda(\mu_{0}-f(R)}\right]}{e^{\lambda\delta\mu_{0}}}\leq
e^{2\lambda^{2}\mu_{0}-\lambda\delta\mu_{0}}\,.$

Setting $\lambda=\delta/4$ concludes the lemma. ∎