# Lipschitz Continuous Algorithms for Covering Problems

Soh Kumabe  Yuichi Yoshida

###### Abstract

Combinatorial algorithms are widely used for decision-making and knowledge
discovery, and it is important to ensure that their output remains stable even
when subjected to small perturbations in the input. Failure to do so can lead
to several problems, including costly decisions, reduced user trust, potential
security concerns, and lack of replicability. Unfortunately, many fundamental
combinatorial algorithms are vulnerable to small input perturbations. To
address the impact of input perturbations on algorithms for weighted graph
problems, Kumabe and Yoshida (FOCS’23) recently introduced the concept of
Lipschitz continuity of algorithms. This work explores this approach and
designs Lipschitz continuous algorithms for covering problems, such as the
minimum vertex cover, set cover, and feedback vertex set problems.

Our algorithm for the feedback vertex set problem is based on linear
programming, and in the rounding process, we develop and use a technique
called cycle sparsification, which may be of independent interest.

###### Contents

  1. 1 Introduction
    1. 1.1 Lipschitz Continuity
    2. 1.2 Our Results
    3. 1.3 Proof Overview
    4. 1.4 Related Work
    5. 1.5 Preliminaries
    6. 1.6 Organization
  2. 2 Vertex Cover
    1. 2.1 Approximation Ratio
    2. 2.2 Lipschitz Continuity
  3. 3 Naive Algorithm for Set Cover
  4. 4 Greedy-based Algorithm for Set Cover
    1. 4.1 Algorithm Description
    2. 4.2 Approximation Ratio
    3. 4.3 Lipschitz Continuity
  5. 5 LP-based Algorithm for Set Cover
    1. 5.1 LP Relaxation
    2. 5.2 Rounding
    3. 5.3 Putting things together
  6. 6 Feedback Vertex Set
    1. 6.1 Cycle Sparsification
      1. 6.1.1 Sparsification Guarantee
      2. 6.1.2 Properties of the Induced Set
    2. 6.2 Rounding
    3. 6.3 Algorithm and Proof of Theorem 6.1
  7. 7 Lipschitz Continuity under Shared Randomness
    1. 7.1 Algorithm 1
    2. 7.2 Algorithm 2
    3. 7.3 Algorithm 4
    4. 7.4 Algorithm 6
    5. 7.5 Algorithm 9
  8. A Naive Bound on Lipschitz Constant
  9. B Proof of Lemma 6.4

##  1 Introduction

Combinatorial algorithms are widely used for decision-making and knowledge
discovery, and it is important to ensure that their output remains stable even
when subjected to small perturbations in the input. As was discussed in [8,
11, 15], failure to do so can lead to several problems, including costly
decisions, reduced user trust, potential security concerns, and lack of
replicability. Unfortunately, many fundamental combinatorial algorithms are
vulnerable to small perturbations to the input. To address the impact of input
perturbations on algorithms for weighted graph problems, Kumabe and Yoshida
[11] recently introduced the concept of Lipschitz continuity of algorithms,
and several fundamental graph problems, such as the minimum spanning tree
problem, the shortest path problem, and the maximum matching problem, were
studied from the viewpoint of Lipschitz continuity. In this work, we further
explore their approach and develop Lipschitz continuous algorithms for
covering problems, or more specifically, the minimum vertex cover, set cover,
and feedback vertex set problems.

###  1.1 Lipschitz Continuity

In this section, we formally define the Lipschitz continuity of an algorithm.
We explain the definition using graph algorithms that generate a vertex set as
its output, but the definition can be easily generalized to other
combinatorial problems, such as the set cover problem.

Consider a graph algorithm $\mathcal{A}$, that takes a graph $G=(V,E)$ and a
weight vector $w\in\mathbb{R}_{\geq 0}^{V}$, and outputs a vertex set
$S\subseteq V$. To define the Lipschitz continuity of $\mathcal{A}$, we need
to define distances between input weights and output sets. For the input
weights, we use the $\ell_{1}$ distance. For the output sets, we follow the
approach in [11]. Namely, we map a vertex set $S\subseteq V$ to a vector
$\sum_{v\in S}w_{v}\bm{1}_{v}$, where $\bm{1}_{v}\in\mathbb{R}^{V}$ is the
characteristic vector of $v\in V$, that is, $\bm{1}_{v}(u)=1$ if $u=v$ and $0$
otherwise. Then, we use the $\ell_{1}$ distance between the mapped vectors to
measure the distance between two outputs. Specifically, for two vertex sets
$S,S^{\prime}\subseteq V$ and weight vectors $w,w^{\prime}\in\mathbb{R}_{\geq
0}^{V}$, we use the distance defined as

$\displaystyle
d_{\mathrm{w}}((S,w),(S^{\prime},w^{\prime})):=\left\|\sum_{v\in
S}w_{v}\bm{1}_{v}-\sum_{v\in
S^{\prime}}w^{\prime}_{v}\bm{1}_{v}\right\|_{1}=\sum_{v\in S\cap
S^{\prime}}|w_{v}-w^{\prime}_{v}|+\sum_{v\in S\setminus
S^{\prime}}w_{v}+\sum_{v\in S^{\prime}\setminus S}w^{\prime}_{v}.$

Unfortunately, it is known that there is no deterministic Lipschitz continuous
algorithm with respect to $d_{\mathrm{w}}$ for most problems [11]. Hence, our
focus is on randomized algorithms, and we need to define the distance between
distributions over sets. For two probability distributions $\mathcal{S}$ and
$\mathcal{S}^{\prime}$ over subsets of $V$, the _earth mover’s distance_
between $\mathcal{S}$ and $\mathcal{S}^{\prime}$ is defined as

$\mathrm{EM}_{\mathrm{w}}\left((\mathcal{S},w),(\mathcal{S}^{\prime},w^{\prime})\right):=\min_{\mathcal{D}}\mathop{\mathbf{E}}_{(S,S^{\prime})\sim\mathcal{D}}\left[d_{\mathrm{w}}\left((S,w),(S^{\prime},w^{\prime})\right)\right],$

where the minimum is taken over _couplings_ of $\mathcal{S}$ and
$\mathcal{S}^{\prime}$, that is, distributions over pairs of sets such that
its marginal distributions on the first and second coordinates are equal to
$\mathcal{S}$ and $\mathcal{S}^{\prime}$, respectively. We note that
$\mathrm{EM}_{\mathrm{w}}$ coincides with $d_{\mathrm{w}}$ if the
distributions $\mathcal{S}$ and $\mathcal{S}^{\prime}$ are supported by single
vertex sets.

For a randomized algorithm $\mathcal{A}$, a graph $G=(V,E)$, and a weight
vector $w\in\mathbb{R}_{\geq 0}^{V}$, let $\mathcal{A}(G,w)$ denote the
(random) output of $\mathcal{A}$ on $G$ and $w$. Abusing the notation, we
often identify the output with its distribution. Then, we define the Lipschitz
constant of a randomized algorithm as follows:

######  Definition 1.1 (Lipschitz constant of a randomized algorithm [11]).

Let $\mathcal{A}$ be a randomized algorithm that, given a graph $G=(V,E)$ and
a weight vector $w\in\mathbb{R}_{\geq 0}^{V}$, outputs a (random) vertex set
$\mathcal{A}(G,w)\subseteq V$. Then, the _Lipschitz constant_ of the algorithm
$\mathcal{A}$ on a graph $G=(V,E)$ is

$\displaystyle\sup_{\begin{subarray}{c}w,w^{\prime}\in\mathbb{R}_{\geq
0}^{V},\\\ w\neq
w^{\prime}\end{subarray}}\frac{\mathrm{EM}_{\mathrm{w}}\left((\mathcal{A}(G,w),w),(\mathcal{A}(G,w^{\prime}),w^{\prime})\right)}{\|w-w^{\prime}\|_{1}}.$

We say that $\mathcal{A}$ is _Lipschitz continuous_ if its Lipschitz constant
is bounded for any graph $G=(V,E)$.

It is not hard to show that, if there exists an $\alpha$-approximation
algorithm for a minimization problem on graphs, then for any $\epsilon>0$, we
can transform it to a $(1+\epsilon)\alpha$-approximation algorithm with
Lipschitz constant $\epsilon^{-1}|V|$ (see Appendix A for details). Hence, the
question is whether we can design algorithms with Lipschitz constant sublinear
in $|V|$.

Although Definition 1.1 is natural, it may not be apparent whether bounding
the Lipschitz constant of a randomized algorithm is practically relevant
because, even if the output distributions for two weighted graphs $(G,w)$ and
$(G,w^{\prime})$ are close, the outputs obtained by running the algorithm on
$(G,w)$ and $(G,w^{\prime})$ independently may be completely different.
Therefore, we consider randomized algorithms such that the outputs for two
similar weighted graphs are close in expectation over the internal randomness.
More specifically, for a randomized algorithm $\mathcal{A}$, let $A_{\pi}$
denote the deterministic algorithm obtained from $\mathcal{A}$ by fixing its
internal randomness to $\pi$. Then, we define the Lipschitz constant with
shared randomness of $\mathcal{A}$ as follows:

######  Definition 1.2 (Lipschitz constant of a randomized algorithm with
shared randomness [11]).

Let $\mathcal{A}$ be a randomized algorithm that, given a graph $G=(V,E)$ and
a weight vector $w\in\mathbb{R}_{\geq 0}^{V}$, outputs a (random) vertex set
$\mathcal{A}(G,w)\subseteq V$. Then, the _Lipschitz constant under shared
randomness_ of the algorithm $\mathcal{A}$ on a graph $G=(V,E)$ is

$\displaystyle\sup_{\begin{subarray}{c}w,w^{\prime}\in\mathbb{R}_{\geq
0}^{V},\\\ w\neq
w^{\prime}\end{subarray}}\mathop{\mathbf{E}}_{\pi}\left[\frac{d_{\mathrm{w}}\left((\mathcal{A}_{\pi}(G,w),w),(\mathcal{A}_{\pi}(G,w^{\prime}),w^{\prime})\right)}{\|w-w^{\prime}\|_{1}}\right],$

where $\pi$ represents the internal randomness of $\mathcal{A}$. We say that
$\mathcal{A}$ is _Lipschitz continuous under shared randomness_ if its
Lipschitz constant under shared randomness is bounded for any graph $G=(V,E)$.

Note that if a randomized algorithm has a Lipschitz constant $L$ under shared
randomness, then it has Lipschitz constant $L$, and hence the former is a
stronger property.

###  1.2 Our Results

Table 1: Summary of our results. For the minimum set cover problem, $n$ and $m$ denote the numbers of elements and sets, respectively, and $s$ and $f$ denote the maximum size of a set and maximum frequency of an element, respectively. For the minimum feedback vertex set problem, $n$ denotes the number of vertices. $\epsilon>0$ is an arbitrary constant and $H_{s}=\sum_{i=1}^{s}1/i$. Problem | Approximation guarantee | Lipschitz constant | Reference
---|---|---|---
(under shared randomness)
Vertex Cover | $2\cdot\mathrm{OPT}$ | $4$ | Sec. 2
Set Cover | $(s+\epsilon)\cdot\mathrm{OPT}$ | $O(\epsilon^{-1}s^{2})$ | Sec. 3
$(H_{s}+\epsilon)\cdot\mathrm{OPT}$ | $\exp O(\epsilon^{-2}(s+\log f)s^{2}\log^{3}s)$ | Sec. 4
$O(\log n\cdot\mathrm{OPT})+\epsilon\|w\|_{1}$ | $O(\epsilon^{-1}\sqrt{m}\log^{2}n)$ | Sec. 5
Feedback Vertex Set | $O(\log n\cdot\mathrm{OPT})+\epsilon\|w\|_{1}$ | $O(\epsilon^{-1}\sqrt{n}\log^{2}n)$ | Sec. 6

In this work, we provide Lipschitz continuous algorithms under shared
randomness for various covering problems. Our results are summarized in Table
1.

For a graph $G=(V,E)$, we say that a set $S\subseteq V$ is a _vertex cover_ if
every edge $e\in E$ is incident to a vertex in $S$. In the minimum vertex
cover problem, given a graph $G=(V,E)$ and a weight vector
$w\in\mathbb{R}_{\geq 0}^{V}$, the goal is to find a vertex cover $S\subseteq
V$ that minimizes the total weight $\sum_{v\in S}w_{v}$. For the minimum
vertex cover problem, we show a polynomial-time $2$-approximation algorithm
with Lipschitz constant of at most $4$. Given that computing
$(2-\epsilon)$-approximate solution for the minimum vertex cover problem is
NP-hard under the unique games conjecture for any $\epsilon>0$ [10], our
results show that we can reduce the Lipschitz constant to a small constant
without sacrificing the approximation ratio.

Let $U$ be a set of elements and $\mathcal{F}$ be a family of subsets of $U$.
Then, we say that $\mathcal{S}\subseteq\mathcal{F}$ is a _set cover_ if every
element $e\in U$ is included in a set in $\mathcal{S}$. In the minimum set
cover problem, given a pair $(U,\mathcal{F})$ and a weight vector
$w\in\mathbb{R}_{\geq 0}^{\mathcal{F}}$, the goal is to find a set cover
$\mathcal{S}\subseteq\mathcal{F}$ that minimizes the total weight
$\sum_{S\in\mathcal{S}}w_{S}$. We provide three algorithms for the minimum set
cover problem that are Lipschitz continuous with respect to the weight vector
$w$.

First, we show that for any $\epsilon>0$, there is a polynomial-time
$(s+\epsilon)$-approximation algorithm with Lipschitz constant
$O(\epsilon^{-1}s^{2})$, where $s$ is the maximum set size in the instance,
that is, $s:=\max_{S\in\mathcal{F}}|S|$. Our algorithm is obtained by
modifying a naive $s$-approximation algorithm that selects, for each element
$e\in U$, a set $S\subseteq\mathcal{F}$ including $e$ with the minimum weight,
and add it to the output.

Next, we show that for any $\epsilon>0$, there is an
$(H_{s}+\epsilon)$-approximation algorithm with Lipschitz constant $\exp
O(\epsilon^{-2}(s+\log f)s^{2}\log^{3}s)$, where
$H_{s}=\sum_{i=1}^{s}(1/i)=O(\log s)$ and $f$ is the maximum frequency of an
element, that is, $f:=\max_{e\in U}|\\{S\in\mathcal{F}:e\in S\\}|$. The time
complexity is polynomial when $s=O(\log n)$. It is known that the greedy
algorithm achieves $H_{s}$-approximation [4, 9, 12], and we modify the
algorithm to have a small Lipschitz constant when $s$ and $f$ are bounded.
Compared to the first algorithm, this algorithm has a better approximation
ratio and a worse Lipschitz constant, which shows the trade-off between them.

Finally, we show that for any $\epsilon>0$, there exists a polynomial-time
algorithm that outputs a set cover with total weight $O(\log
n\cdot\mathrm{OPT})+\epsilon\|w\|_{1}$ with Lipschitz constant
$O(\epsilon^{-1}\sqrt{m}\log^{2}n)$, where $n$ and $m$ are the numbers of
elements and sets, respectively. We note that it is NP-hard to achieve
approximation ratio of $(1-\epsilon)\log n$ for any $\epsilon>0$ [5]. Although
we have an additive error of $\epsilon\|w\|_{1}$, the algorithm works even
when $s$ and $f$ are not bounded and its Lipschitz constant is sublinear in
the output size.

Given a graph $G=(V,E)$, a vertex set $S\subseteq V$ is called a _feedback
vertex set_ if every cycle in $G$ has a vertex in $S$. In the minimum feedback
vertex set problem, given a graph $G=(V,E)$ and a weight vector
$w\in\mathbb{R}_{\geq 0}^{V}$, the goal is to find a feedback vertex set
$S\subseteq V$ that minimizes the total weight $\sum_{v\in S}w_{v}$. We
provide a polynomial-time algorithm for the minimum feedback problem whose
performance is similar to the LP-based algorithm for the minimum set cover
problem. Specifically, we show that for any $\epsilon>0$, there exists a
polynomial-time algorithm that outputs a feedback vertex set with total weight
$O(\log n\cdot\mathrm{OPT})+\epsilon\|w\|_{1}$ with Lipschitz constant
$O(\epsilon^{-1}\sqrt{n}\log^{2}n)$, where $n$ is the number of vertices. We
mention that the minimum feedback vertex set problem admits $2$-approximation
[1] and determing whether we can improve the multiplicative error of our
algorithm to two (or a constant) is an interesting open problem.

###  1.3 Proof Overview

If an algorithm comprises multiple steps and the later steps depend on the
results of earlier steps, the Lipschitz constant generally increases at each
step, eventually reaching a large value. To achieve a small Lipschitz
constant, Lipschitz constant should not increase at each step or we should
break the dependencies between steps. We provide an overview of our algorithm
and how we achieve a small Lipschitz constant (without shared randomness) for
each problem. Then we discuss modifications required to achieve small
Lipschitz constant under shared randomness.

##### Vertex Cover

Our algorithm is a primal-dual algorithm based on the following LP:

$\displaystyle\begin{array}[]{llll}\text{Primal}(G,w):=&\text{minimize}&\displaystyle\sum_{v\in
V}w_{v}x_{v},\\\ &\text{subject to}&x_{u}+x_{v}\geq 1&(e=(u,v)\in E),\\\
&&x_{v}\geq 0&(v\in V).\end{array}$

$\displaystyle\begin{array}[]{llll}\text{Dual}(G,w):=&\text{maximize}&\displaystyle\sum_{e\in
E}y_{e},\\\ &\text{subject to}&\displaystyle\sum_{e\in\delta(v)}y_{e}\leq
w_{v}&(v\in V),\\\ &&y_{e}\geq 0&(e\in E).\end{array}$

Here $\delta(v)$ denotes the set of edges incident to the vertex $v$. The
algorithm uses the concept of time to obtain feasible solutions for the dual
problem. A vertex $v\in V$ is called _tight_ when it satisfies
$\sum_{e\in\delta(v)}y_{e}=w_{v}$. At time $0$, we set $y_{e}=0$ for all edges
$e\in E$, and simultaneously increment the value of $y_{e}$ by $1$ per unit of
time as long as neither of the endpoints of $e$ is tight. Once all edges are
incident to tight vertices, the algorithm adds each vertex $v$ to the output
with probability $\sum_{e\in\delta(v)}y_{e}/w_{v}$. The approximation
guarantee of $2$ follows from the weak LP duality.

The main technical part lies in the analysis of the Lipschitz constant. Let
$w$ and $w^{\prime}$ be two different weight vectors. We denote the value of
$y_{e}$ at time $t$ when the algorithm is executed with weights $w$ and
$w^{\prime}$ as $y_{e}(t)$ and $y^{\prime}_{e}(t)$, respectively. We define
the _residual distance_ as

$\mathrm{RD}(t):=\sum_{v\in
V}\left|\left(w_{v}-\sum_{e\in\delta(v)}y_{e}(t)\right)-\left(w^{\prime}_{v}-\sum_{e\in\delta(v)}y^{\prime}_{e}(t)\right)\right|.$

We can prove that the residual distance does not increase over time. It
implies that for any given time $t\in\mathbb{R}_{\geq 0}$, $\sum_{e\in
E}|y_{e}(t)-y^{\prime}_{e}(t)|\leq|w-w^{\prime}|$, which can be used to bound
the Lipschitz constant.

##### Naive algorithm for Set Cover

The algorithm that selects, for each element $e\in U$, a set $S\ni e$ with the
minimum weight and outputs them is a trivial $s$-approximation algorithm,
where $s$ is the maximum set size in $\mathcal{F}$. We make slight
modifications to obtain a Lipschitz continuous algorithm. Specifically,
instead of selecting the set with the minimum weight that contains each $e\in
U$, we sample a set uniformly at random from the family of sets with their
weight less than a constant times the minimum weight independently from
others. By setting the constant to achieve an approximation ratio of
$s+\epsilon$, we obtain the Lipschitz constant of $O(\epsilon^{-1}s^{2})$
using the independence of the sampling process.

##### Greedy-based algorithm for Set Cover

A well-known greedy algorithm for the minimum set cover problem is as follows:
Start with an empty solution. At each step, let $R\subseteq U$ be the set of
vertices already covered, select the set $S\in\mathcal{F}$ that minimizes
$w_{S}/|R\cap S|$, and add it to the solution. This algorithm is an
$H_{s}$-approximation algorithm, where $H_{s}:=\sum_{i=1}^{s}(1/i)$.

We modify this algorithm to obtain a Lipschitz continuous algorithm. First, we
rewrite the operations of the original algorithm as follows: Define a
multifamily $\mathcal{F}^{\downarrow}$ as
$\bigcup_{S\in\mathcal{F}}(2^{S}\setminus\\{\emptyset\\})$, and define the
weight $w^{\downarrow}_{A}$ for each element $A\in\mathcal{F}^{\downarrow}$ as
the weight $w_{S}$ of the corresponding $S\in\mathcal{F}$. By this rephrasing,
each step of the greedy algorithm can be seen as the operation of selecting
the set $A\subseteq\mathcal{F}^{\downarrow}$ of the minimum relative weight
$w^{\downarrow}_{A}/|A|$ that has no intersection with already covered
elements. Then, we introduce a positive integer constant $M$ and round
$w^{\downarrow}_{A}$ to an integer power of $s^{1/M}$.

The main trick of our algorithm is to apply the greedy algorithm after
discarding some sets of $\mathcal{F}^{\downarrow}$. Specifically, we introduce
a positive integer constant $K$ and discard a set
$A\in\mathcal{F}^{\downarrow}$ if $\log_{s}w^{\downarrow}_{A}$ belongs to a
specific interval of width $1$ modulo $K$. Then, whether to include $A$ in the
solution only affects choices of having elements with weights less than
$s^{K}\cdot w^{\downarrow}_{A}$, which breaks the dependencies between steps
in the greedy algorithm. Because we round the weights, there are at most $sKM$
possible values for $w^{\downarrow}_{A}/|A|$. If we randomly decide whether to
include elements with equal (rounded) weights in the solution, we can prove
that the Lipschitz constant can be bounded by a constant determined by $s$ and
$f$ raised to the power of $sKM$.

##### LP-based algorithm for Set Cover

To handle general set cover instances, we utilize the standard LP-based
algorithm and introduce modifications to ensure a low Lipschitz constant.

Let us begin by recalling the standard LP-based algorithm for the minimum set
cover problem. Given an instance $(U,\mathcal{F})$ of the minimum set cover
problem and a weight vector $w\in\mathbb{R}_{\geq 0}^{\mathcal{F}}$, we
consider the following LP relaxation:

$\displaystyle\begin{array}[]{lll}\text{minimize}&\displaystyle\sum_{S\in\mathcal{F}}w_{S}x_{S},\\\
\text{subject to}&\displaystyle\sum_{S\in\mathcal{F}:e\in S}x_{S}\geq
1&\forall e\in U,\\\ &0\leq x_{S}\leq 1&\forall S\in\mathcal{F}.\end{array}$
(4)

Let $x\in\mathbb{R}^{\mathcal{F}}$ be the solution to (4). Then for each
$S\in\mathcal{F}$, we independently add it to the solution with probability
$x_{S}$, repeating this process $O(\log n)$ times to ensure that the output
solution becomes a set cover with a high probability, where $n=|U|$ is the
number of elements.

Now, we explain the modification required to make the algorithm above
Lipschitz continuous. Suppose we have two weight vectors
$w,w^{\prime}\in\mathbb{R}_{\geq 0}^{\mathcal{F}}$ and their corresponding
solutions to LP (4) are denoted by $x$ and $x^{\prime}$, respectively. To
achieve Lipschitz continuity in the rounding part, we need to ensure that
$\sum_{S\in\mathcal{F}}|w_{S}x_{S}-w^{\prime}_{S}x^{\prime}_{S}|$ is small. To
accomplish this, we introduce two regularizers in the objective function:

$\sum_{S\in\mathcal{F}}w_{S}x_{S}+\frac{\lambda}{2}\sum_{S\in\mathcal{F}}x_{S}^{2}+\frac{\kappa}{2}\sum_{S\in\mathcal{F}}w_{S}x_{S}^{2},$

where $\lambda=\Theta(\epsilon\|w\|_{1}/(m\log n))$ and
$\kappa=\Theta(\epsilon/\log n)$, where $m=|\mathcal{F}|$ is the number of
sets. The addition of the first type of regularizer has been utilized in [15]
to design an algorithm for the $s$-$t$ minimum cut problem with low average
sensitivity, and in [11] to design a Lipschitz continuous algorithm for the
bipartite maximum matching problem, where the distance between two matchings
is computed without using the respective weights (as opposed to
$\mathrm{EM}_{\mathrm{w}}$). We also incorporate the second type of
regularizer to handle weighted instances and the weighted distance
$d_{\mathrm{w}}$. With these regularizers, we can show that
$\sum_{S\in\mathcal{F}}|w_{S}x_{S}-w^{\prime}_{S}x^{\prime}_{S}|=O(\epsilon^{-1}\sqrt{m}\log
n\cdot\|w-w^{\prime}\|_{1})$ while the additional error in the objective value
is $O(\epsilon\|w\|_{1}/\log n)$.

We can show that the Lipschitz constant for a single iteration of the rounding
part is
$\sum_{S\in\mathcal{F}}|w_{S}x_{S}-w^{\prime}_{S}x^{\prime}_{S}|/\|w-w^{\prime}\|_{1}=O(\epsilon^{-1}\sqrt{m}\log
n)$ using the independence of the sampling process. Since we repeat the
iteration $O(\log n)$ times, the final Lipschitz constant becomes
$O(\epsilon^{-2}\sqrt{m}\log^{2}n)$, while the expected total weight of the
output is $O(\log n\cdot\|x\|_{1})+\epsilon\|w\|_{1}=O(\log
n\cdot\text{OPT})+\epsilon\|w\|_{1}$.

##### Feedback Vertex Set

The minimum feedback vertex set problem can be represented as a minimum set
cover problem, where vertices correspond to sets and cycles correspond to
elements. Therefore, given a graph $G=(V,E)$ and a weight vector
$w\in\mathbb{R}_{\geq 0}^{V}$, we consider the LP relaxation (4), and we solve
it using our algorithm for the minimum set cover problem with
$\lambda=\Theta(\epsilon\|w_{1}\|/(n\log n))$ and $\kappa=\Theta(\epsilon/\log
n)$, where $n:=|V|$ is the number of vertices (corresponding to $m$ in the set
cover case). This will yield an LP solution $x\in\mathbb{R}_{\geq 0}^{V}$ such
that $\sum_{v\in V}w_{v}x_{v}\leq\mathrm{OPT}+O(\epsilon\|w\|_{1}/\log n)$ and
$\sum_{v\in C}x_{v}\geq 1$ for every cycle $C$ in $G$. In addition, for LP
solutions $x,x^{\prime}\in\mathbb{R}^{V}$ constructed from weight vectors
$w,w^{\prime}\in\mathbb{R}^{V}$, respectively, we have $\sum_{v\in
V}|w_{v}x_{v}-w^{\prime}_{v}x^{\prime}_{v}|=O(\epsilon^{-1}\sqrt{n}\log
n\cdot\|w-w^{\prime}\|_{1})$.

However, an issue arises in the rounding part. To ensure that the output is a
feedback vertex set, the independent sampling process needs to be repeated
$O(\log|\mathcal{C}|)$ times, where $\mathcal{C}$ is the set of simple cycles
in $G$. However, because $|\mathcal{C}|$ can be exponential in the number of
vertices in $G$, this rounding approach leads to polynomial approximation
ratio and Lipschitz constant, which are excessively large.

To address this issue, we introduce a technique called _cycle sparsification_
and use it to round the LP solution. For two weight vectors
$z,\tilde{z}\in\mathbb{R}^{V}$, we say that $(G,\tilde{z})$ is an _$\epsilon$
-cycle sparsifier_ of $(G,z)$ if

$(1-\epsilon)z(C)\leq\tilde{z}(C)\leq(1+\epsilon)z(C)$

holds for every cycle $C$ in $G$, where $z(C)=\sum_{v\in C}z_{v}$ and
$\tilde{z}(C)=\sum_{v\in C}\tilde{z}_{v}$. A similar notion for cuts has been
extensively studied under the name of _cut sparsifier_ [2, 6].

To obtain a cycle sparsifier, we modify the cut sparsification algorithm for
integer-weighted graphs proposed by Fung et al. [6]. In their algorithm, they
compute the _edge connectivity_ $k_{e}$ of each edge $e\in E$, which is the
minimum weight of a cut that separates the endpoints of $e$. Then for each
edge $e\in E$ with weight $z_{e}\in\mathbb{Z}_{\geq 0}$, they sample a number
$c_{e}$ from the binomial distribution $\mathcal{B}(z_{e},p_{e})$, where
$p_{e}=O(\log n/k_{e})$, and assign the weight $c_{e}/p_{e}$ to it. To
construct a cycle sparsifier, we first compute the _girth_ $g_{v}$ of a vertex
$v\in V$, the minimum weight of a cycle passing through the vertex. Then for
each vertex $v\in V$ with weight $z_{e}\in\mathbb{Z}_{\geq 0}$, we sample a
number $c_{v}$ from the binomial distribution $\mathcal{B}(z_{v},p_{v})$,
where $p_{v}=O(\log n/g_{v})$, and assign the weight $c_{v}/p_{v}$ to it.

In the analysis of the cut sparsifier proposed by Fung et al. [6], they used a
cut counting lemma, which asserts that, for any edge set $F\subseteq E$, the
number of subsets of $F$ induced by small cuts is small. We need a counterpart
of this lemma for cycles, that is, we want to show that for any vertex set
$S\subseteq V$, the number of subsets of $S$ induced by small cycles is small.
We prove this by generalizing the known argument for $S=V$ [14].

Now, we explain how we use the cycle sparsification result for rounding.
Consider an LP solution $x\in\mathbb{R}_{\geq 0}^{V}$ for the minimum feedback
vertex set problem. Note that in the weighted graph $(G,x)$, every vertex has
a girth of at least one. To round the LP solution $x$, we first construct an
integer vector $z\in\mathbb{Z}_{\geq 0}^{V}$ by scaling it by a factor
$n^{2}$. Then, we apply cycle sparsification to $z$ using the girth lower
bound of $n^{2}$. The resulting vector $\tilde{z}\in\mathbb{R}_{\geq 0}^{V}$
is a cycle sparsifier with a high probability. This implies that the set
$S=\\{v\in V:\tilde{z}_{v}>0\\}$ is a feedback vertex set because every cycle
has a positive weight in $\tilde{z}$. Furthermore, we can show that the total
weight of $S$ is $O(\sum_{v\in V}w_{v}x_{v}\log n)$, which is $O(\log
n\cdot\mathrm{OPT})+\epsilon\|w\|_{1}$.

Now let us consider Lipschitz continuity of the algorithm. Let
$x,x^{\prime}\in\mathbb{R}^{V}$ be the LP solutions for weight vectors
$w,w^{\prime}\in\mathbb{R}^{V}$, respectively. Then, considering that our
cycle sparsification algorithm samples weights of vertices independently, we
can show that it amplifies the Lipschitz constant merely by $O(\log n)$.
Combined with the bound $\sum_{v\in
V}|w_{v}x_{v}-w^{\prime}_{v}x^{\prime}_{v}|=O(\epsilon^{-1}\sqrt{n}\log
n\cdot\|w-w^{\prime}\|_{1})$, we can show that the Lipschitz constant of the
entire algorithm is $O(\epsilon^{-1}\sqrt{n}\log^{2}n)$.

##### Lipschitz Continuity under Shared Randomness

Our algorithms can be straightforwardly made Lipschitz continuous even in the
shared randomness setting. Specifically, we replace the random sampling
processes in our algorithms with stable sampling procedures developed by
Kumabe and Yoshida [11] to ensure Lipschitz continuity under shared
randomness.

###  1.4 Related Work

As mentioned earlier, Kumabe and Yoshida introduced the concept of
Lipschitzness for graph algorithms [11]. They devised Lipschitz continuous
algorithms for the minimum spanning tree, shortest path, and maximum matching
problems. This work expands the scope of Lipschitz continuous algorithms to
covering problems. Although different possible notions of Lipschitz continuity
were considered, the ones used in this work (Definitions 1.1 and 1.2) are
arguably the most natural.

The average sensitivity of algorithms, introduced by Varma and Yoshida [15],
is a concept closely related to Lipschitz continuity. The _average
sensitivity_ of an algorithm on an (unweighted) instance
$X=(x_{1},\ldots,x_{n})$ consisting of $n$ elements is the average earth
mover’s distance between the output for $X$ and that for
$X\setminus\\{x_{i}\\}$, where we take the expectation over
$i\in\\{1,2,\ldots,n\\}$. They showed algorithms for the minimum spanning
tree, minimum cut, and maximum matching problems with low average sensitivity.
Since then algorithms with low average sensitivity have been proposed for
various problems, including the minimum cut and maximum matching problems
[18], $k$-means [17], decision tree learning [7], spectral clustering [13]. We
note that bounding the Lipschitz constant is usually more challenging than
bounding the average sensitivity because it considers the worst-case input
modification and requires dealing with arbitrarily small yet non-zero
perturbations.

###  1.5 Preliminaries

We use bold symbols to denote random variables. For a (continuous or discrete)
set $X$, let $\mathcal{U}(X)$ denote the uniform distribution over $X$. For a
vector $w\in\mathbb{R}^{V}$ and a set $S\subseteq V$, we define
$w(S):=\sum_{v\in S}w_{v}$.

The following is useful to bound the Lipschitz constant. The proof is quite
similar to that of Lemma 1.7 of [11].

######  Lemma 1.3.

Let $\mathcal{A}$ be an algorithm that takes a graph $G=(V,E)$ and a weight
vector $w\in\mathbb{R}_{\geq 0}^{V}$ and outputs a subset of $V$. Suppose that
there exist some $c>0$ and $L>0$ such that

$\mathrm{EM}_{\mathrm{w}}\left((\mathcal{A}(G,w),w),(\mathcal{A}(G,w+\delta\mathbf{1}_{v}),w+\delta\mathbf{1}_{v})\right)\leq\delta
L$

holds for any $v\in V$, $w\in\mathbb{R}_{\geq 0}^{V}$, and $\delta>0$ such
that either $0<\delta\leq c\cdot w_{v}$ or $w_{v}=0$ holds. Then,
$\mathcal{A}$ has Lipschitz constant $L$ on $G$.

###  1.6 Organization

We provide Lipschitz continuous algorithm for the minimum vertex cover problem
in Section 2. Then, we provide naive, greedy-based, and LP-based algorithms
for the minimum set cover problem in Sections 3, 4, and 5, respectively. We
provide Lipschitz continuous algorithm for the feedback vertex set problem and
the cycle sparsification result in Section 6. Finally, we discuss
modifications needed to bound the Lipschitz constant under shared randomness
in Section 7.

##  2 Vertex Cover

The goal of this section is to show the following:

######  Theorem 2.1.

There exists a polynomial-time $2$-approximation algorithm for the minimum
vertex cover problem with Lipschitz constant $4$.

We first look at the primal and dual LP formulations for the minimum vertex
cover problem. In the primal LP, the variable $x_{v}$ for a vertex $v\in V$
represents whether it belongs to a vertex cover.

$\displaystyle\begin{array}[]{llll}\text{Primal}(G,w):=&\text{minimize}&\displaystyle\sum_{v\in
V}w_{v}x_{v},\\\ &\text{subject to}&x_{u}+x_{v}\geq 1&(e=(u,v)\in E),\\\
&&x_{v}\geq 0&(v\in V).\end{array}$
$\displaystyle\begin{array}[]{llll}\text{Dual}(G,w):=&\text{maximize}&\displaystyle\sum_{e\in
E}y_{e},\\\ &\text{subject to}&\sum_{e\in\delta(v)}y_{e}\leq w_{v}&(v\in
V),\\\ &&y_{e}\geq 0&(e\in E).\end{array}$

1 Procedure  __VertexCover($G,w$)__

Input: A graph $G=(V,E)$ and a weight vector $w\in\mathbb{R}_{\geq 0}^{V}$.

2 Let $y_{e}\leftarrow 0$ for all $e\in E$;

3 Let $A\leftarrow E$;

4 while  _$A\neq\emptyset$_ do

5 Let $\Delta t$ be the minimum value of
$\frac{w_{v}-\sum_{e\in\delta(v)}y_{e}}{|\delta(v)\cap A|}$ among all non-
tight vertices $v\in V$;

6 for  _$e\in A$_ do

7 $y_{e}\leftarrow y_{e}+\Delta t$;

8 Remove all edges incident to a tight vertex from $A$;

9

10

11 Let $\bm{C}\leftarrow\emptyset$;

12 for  _$v\in V$_ do

13 Sample $\bm{z}(v)$ uniformly from $[0,1]$;

14 if  _$w_{v}=0$ or $\bm{z}(v)\leq\frac{\sum_{e\in\delta(v)}y_{e}}{w_{v}}$_
then

15 Add $v$ to $\bm{C}$;

16

17

18 return $\bm{C}$;

19

Algorithm 1 Lipschitz continuous algorithm for the minimum vertex cover
problem

Our algorithm, VertexCover, is presented in Algorithm 1. In the while loop
starting from Line 1, we call a vertex _tight_ if
$w_{v}=\sum_{e\in\delta(v)}y_{e}$. This algorithm is nearly identical to the
standard primal-dual algorithm (see, e.g., Section 7.1 of [16]) for the
minimum vertex cover problem, and our main contribution lies in the analysis
of the Lipschitz constant.

We analyze the approximation ratio and Lipschitz continuity of VertexCover in
Sections 2.1 and 2.2, respectively.

###  2.1 Approximation Ratio

The following holds.

######  Lemma 2.2.

VertexCover is a $2$-approximation algorithm.

###### Proof.

Since removing vertices $v\in V$ with $w_{v}=0$ does not affect the algorithm
and the optimal value, we can assume $w_{v}>0$ for every $v\in V$ to analyze
approximation ratio without loss of generality. At the end of each iteration
in the while loop starting at Line 1, $A$ forms a set of edges such that at
least one of the endpoints is tight. By the termination condition of the loop,
at the end of the loop, at least one endpoint of each edge is tight. Since the
output must include all tight vertices, Algorithm 1 outputs a vertex cover.

Note that the value of $y_{e}$ corresponding to an edge $e\in E$ incident to a
tight vertex does not increase further. Therefore, at the end of the
algorithm, for every vertex $v\in V$, we have $\sum_{e\in\delta(v)}y_{e}\leq
w_{v}$. In particular, $y$ is a feasible solution for $\mathrm{Dual}(G,w)$.
Let $\bm{C}=\textsc{VertexCover}(G,w)$. Then, we have

$\displaystyle\mathop{\mathbf{E}}\left[\sum_{v\in\bm{C}}w_{v}\right]$
$\displaystyle=\sum_{v\in
V}\left(w_{v}\cdot\frac{\sum_{e\in\delta(v)}y_{e}}{w_{v}}\right)=\sum_{v\in
V}\left(\sum_{e\in\delta(v)}y_{e}\right)=2\sum_{e\in E}y_{e}\leq
2\cdot\mathrm{OPT},$

where the last inequality is because $y$ is a feasible solution for
$\mathrm{Dual}(G,w)$ and the weak duality theorem of linear programming. ∎

###  2.2 Lipschitz Continuity

Now we evaluate the Lipschitz continuity. For two weight vectors
$w,w^{\prime}\in\mathbb{R}_{\geq 0}^{V}$, let us evaluate

$\displaystyle\mathrm{EM}_{\mathrm{w}}\left((\textsc{VertexCover}(G,w),w),(\textsc{VertexCover}(G,w^{\prime}),w^{\prime})\right).$

Let $y_{e}$ and $y^{\prime}_{e}$ denote the values of the variable $y_{e}$ in
VertexCover($G,w$) and VertexCover($G,w^{\prime}$), respectively. We introduce
the concept of _time_ to the loop starting from Line 1 and regard that the
algorithm continuously increments the value of $y_{e}$ for each edge $e\in E$
by $1$ per unit time unless one of the endpoints is tight. Let $y_{e}(t)$ and
$y^{\prime}_{e}(t)$ be the value of $y_{e}$ and $y^{\prime}_{e}$ at time $t$
during the execution of VertexCover($G,w$) and VertexCover($G,w^{\prime}$),
respectively. It can be easily observed that, for every $e\in E$, there exists
a time $t_{e}$ such that $y_{e}(t)$ is expressed as follows:

$\displaystyle y_{e}(t)=\left\\{\begin{array}[]{cc}t&(t\leq t_{e})\\\
t_{e}&(t_{e}<t).\end{array}\right.$

We call the value

$\mathrm{RD}(t)=\sum_{v\in
V}\left|\left(w_{v}-\sum_{e\in\delta(v)}y_{e}(t)\right)-\left(w^{\prime}(v)-\sum_{e\in\delta(v)}y^{\prime}_{e}(t)\right)\right|$

the _residual distance_ between $y_{e}$ and $y^{\prime}_{e}$ at time $t$. Let
us evaluate how the residual distance changes during the loop starting at Line
1. At the beginning of the loop, the residual distance is
$\mathrm{RD}(0)=\|w-w^{\prime}\|_{1}$.

For a function $f:\mathbb{R}\to\mathbb{R}$, we denote the right derivative of
$f$ by $\partial_{+}f(t)$, i.e.,

$\displaystyle\partial_{+}f(t):=\lim_{x\rightarrow+0}\frac{f(t+x)-f(t)}{x}.$

The following lemma is the heart of our Lipschitz continuity analysis.

######  Lemma 2.3.

$\partial_{+}\mathrm{RD}(t)\leq 0$.

###### Proof.

Treating $y_{e}(t)$’s and $y^{\prime}_{e}(t)$’s as functions of $t$, using an
integer function $c_{e}:\mathbb{R}_{\geq 0}\to\\{-2,-1,0,1,2\\}$ defined for
each $e\in E$, the right derivative of $\mathrm{RD}(t)$ can be represented as

$\displaystyle\partial_{+}\mathrm{RD}(t)=\sum_{e\in
E}c_{e}(t)\left(\partial_{+}y_{e}(t)-\partial_{+}y^{\prime}_{e}(t)\right),$

where $c_{e}(t)$ takes only values from $\\{-2,-1,0,1,2\\}$ because for each
edge $e\in E$, the term $y_{e}(t)-y^{\prime}_{e}(t)$ appears twice in the
expression of $\mathrm{RD}(t)$.

Let $A(t)$ and $A^{\prime}(t)$ denote the set $A$ at time $t$ in
$\textsc{VertexCover}(G,w)$ and $\textsc{VertexCover}(G,w^{\prime})$,
respectively. Then, $\partial_{+}y_{e}(t)$ takes the value $1$ if $e\in A(t)$
and $0$ otherwise. Similarly, $\partial_{+}y^{\prime}_{e}(t)$ takes the value
$1$ if $e\in A^{\prime}(t)$ and $0$ otherwise. Using these facts, we have

$\displaystyle\partial_{+}\mathrm{RD}(t)$ $\displaystyle=\sum_{e\in
E}c_{e}\left(\partial_{+}y_{e}(t)-\partial_{+}y^{\prime}_{e}(t)\right)$
$\displaystyle=\sum_{e\in A(t)\cap A^{\prime}(t)}c_{e}\cdot 0+\sum_{e\in
A(t)\setminus A^{\prime}(t)}c_{e}\cdot 1+\sum_{e\in A^{\prime}(t)\setminus
A(t)}c_{e}\cdot(-1)+\sum_{e\in E\setminus(A(t)\cap A^{\prime}(t))}c_{e}\cdot
0$ $\displaystyle=\sum_{e\in A(t)\setminus A^{\prime}(t)}c_{e}-\sum_{e\in
A^{\prime}(t)\setminus A(t)}c_{e}.$

Let $e=(u,v)\in A(t)\setminus A^{\prime}(t)$. From the definitions of $A(t)$
and $A^{\prime}(t)$, neither $u$ nor $v$ is tight at time $t$ in
VertexCover($G,w$), while in VertexCover($G,w^{\prime}$), at least one of
them, say $u$, is tight. Therefore, we have

$\displaystyle\partial_{+}\left|\left(w_{u}-\sum_{e\in\delta(u)}y_{e}(t)\right)-\left(w^{\prime}_{u}-\sum_{e\in\delta(u)}y^{\prime}_{e}(t)\right)\right|=\partial_{+}\left|\left(w_{u}-\sum_{e\in\delta(u)}y_{e}(t)\right)-0\right|$
$\displaystyle=\partial_{+}\left(w_{u}-\sum_{e\in\delta(u)}y_{e}(t)\right)=-\sum_{e\in\delta(u)}\partial_{+}y_{e}(t).$

In particular, at least once in the sum of $\partial_{+}\mathrm{RD}(t)$, the
term $\partial_{+}y_{e}(t)$ makes a negative contribution. Additionally,
because $y_{e}(t)-y^{\prime}_{e}(t)$ appears twice in the expression of
$\mathrm{RD}(t)$, we have $c_{e}\leq 0$.

By a similar argument, we obtain $c_{e}\geq 0$ for $e\in
A^{\prime}(t)\setminus A(t)$. Therefore, the claim holds. ∎

The following is immediate from Lemma 2.3.

######  Lemma 2.4.

At the end of the loop starting at Line 1, we have

$\displaystyle\sum_{v\in
V}\left|\sum_{e\in\delta(v)}y_{e}-\sum_{e\in\delta(v)}y^{\prime}_{e}\right|\leq
2\|w-w^{\prime}\|_{1}.$

###### Proof.

Let $T$ be the later of the times $\textsc{VertexCover}(G,w)$ and
$\textsc{VertexCover}(G,w^{\prime})$ terminate. Then, from Lemma 2.3, we have
$\mathrm{RD}(T)\leq\|w-w^{\prime}\|_{1}$. Therefore,

$\displaystyle\sum_{v\in
V}\left|\sum_{e\in\delta(v)}y_{e}(T)-\sum_{e\in\delta(v)}y^{\prime}_{e}(T)\right|$
$\displaystyle\leq\sum_{v\in
V}\left(\left|\left(w_{v}-\sum_{e\in\delta(v)}y_{e}(t)\right)-\left(w^{\prime}_{v}-\sum_{e\in\delta(v)}y^{\prime}_{e}(t)\right)\right|+\left|w_{v}-w^{\prime}_{v}\right|\right)$
$\displaystyle=\mathrm{RD}(T)+\|w-w^{\prime}\|_{1}\leq
2\|w-w^{\prime}\|_{1}.\qed$

######  Lemma 2.5.

VertexCover has Lipschitz constant $4$.

###### Proof.

By Lemma 1.3, we can assume there exists a vertex $u\in V$ such that
$w_{v}=w^{\prime}_{v}$ holds for $v\in V\setminus\\{u\\}$ and
$w_{u}<w^{\prime}_{u}$. To bound the earth mover’s distance between the output
vertex covers for $(G,w)$ and $(G,w^{\prime})$, we consider the coupling
$\mathcal{W}$ between $\bm{z}$ and $\bm{z}^{\prime}$, defined as follows: For
each $z\in[0,1]^{V}$, we transport the probability mass for $\bm{z}=z$ to that
for $\bm{z}^{\prime}=z$. When $w_{u}=0$, we have

$\displaystyle\mathrm{EM}_{\mathrm{w}}\left((\textsc{VertexCover}(G,w),w),(\textsc{VertexCover}(G,w^{\prime}),w^{\prime})\right)$
$\displaystyle\leq\sum_{v\in V\setminus\\{u\\}\colon
w_{v}>0}\left|\frac{\sum_{e\in\delta(v)}y_{e}}{w_{v}}-\frac{\sum_{e\in\delta(v)}y^{\prime}_{e}}{w_{v}}\right|\cdot
w_{v}+\frac{\sum_{e\in\delta(u)}y^{\prime}_{e}}{w^{\prime}_{u}}\cdot
w^{\prime}_{u}$ $\displaystyle\leq\sum_{v\in V\setminus\\{u\\}\colon
w_{v}>0}\left|\sum_{e\in\delta(v)}y_{e}-\sum_{e\in\delta(v)}y^{\prime}_{e}\right|+1\cdot
w^{\prime}_{u}$ $\displaystyle\leq\sum_{v\in
V}\left|\sum_{e\in\delta(v)}y_{e}-\sum_{e\in\delta(v)}y^{\prime}_{e}\right|+\|w-w^{\prime}\|_{1}\leq
3\|w-w^{\prime}\|_{1},$

where the first inequality is because $w_{v}\neq w^{\prime}_{v}$ holds for
$u=v$ and $w_{u}=0$. Otherwise, we have

$\displaystyle\mathrm{EM}_{\mathrm{w}}\left((\textsc{VertexCover}(G,w),w),(\textsc{VertexCover}(G,w^{\prime}),w^{\prime})\right)$
$\displaystyle\leq\sum_{v\in V\setminus\\{u\\}\colon
w_{v}>0}\left|\frac{\sum_{e\in\delta(v)}y_{e}}{w_{v}}-\frac{\sum_{e\in\delta(v)}y^{\prime}_{e}}{w_{v}}\right|\cdot
w_{v}$
$\displaystyle\quad+\min\left(\frac{\sum_{e\in\delta(u)}y_{e}}{w_{u}},\frac{\sum_{e\in\delta(u)}y^{\prime}_{e}}{w^{\prime}_{u}}\right)\cdot(w^{\prime}_{u}-w_{u})+\left|\frac{\sum_{e\in\delta(u)}y_{e}}{w_{u}}-\frac{\sum_{e\in\delta(u)}y^{\prime}_{e}}{w^{\prime}_{u}}\right|\cdot
w^{\prime}_{u}$ $\displaystyle\leq\sum_{v\in V\setminus\\{u\\}\colon
w_{v}>0}\left|\sum_{e\in\delta(v)}y_{e}-\sum_{e\in\delta(v)}y^{\prime}_{e}\right|+1\cdot(w^{\prime}_{u}-w_{u})+\left|\frac{\sum_{e\in\delta(u)}y_{e}}{w_{u}}-\frac{\sum_{e\in\delta(u)}y^{\prime}_{e}}{w^{\prime}_{u}}\right|\cdot
w^{\prime}_{u}$ $\displaystyle\leq\sum_{v\in V\setminus\\{u\\}\colon
w_{v}>0}\left|\sum_{e\in\delta(v)}y_{e}-\sum_{e\in\delta(v)}y^{\prime}_{e}\right|+(w^{\prime}_{u}-w_{u})$
$\displaystyle\quad+\left(\left|\frac{\sum_{e\in\delta(u)}y_{e}}{w_{u}}-\frac{\sum_{e\in\delta(u)}y_{e}}{w^{\prime}_{u}}\right|+\left|\frac{\sum_{e\in\delta(u)}y_{e}}{w^{\prime}_{u}}-\frac{\sum_{e\in\delta(u)}y^{\prime}_{e}}{w^{\prime}_{u}}\right|\right)\cdot
w^{\prime}_{u}$ $\displaystyle\leq\sum_{v\in V\setminus\\{u\\}\colon
w_{v}>0}\left|\sum_{e\in\delta(v)}y_{e}-\sum_{e\in\delta(v)}y^{\prime}_{e}\right|+(w^{\prime}_{u}-w_{u})+\left|\frac{w_{u}}{w_{u}}-\frac{w_{u}}{w^{\prime}_{u}}\right|\cdot
w^{\prime}_{u}+\left|\sum_{e\in\delta(u)}y_{e}-\sum_{e\in\delta(u)}y^{\prime}_{e}\right|$
$\displaystyle\leq\sum_{v\in V\colon
w_{v}>0}\left|\sum_{e\in\delta(v)}y_{e}-\sum_{e\in\delta(v)}y^{\prime}_{e}\right|+2(w^{\prime}_{u}-w_{u})$
$\displaystyle\leq
2\|w-w^{\prime}\|_{1}+2\|w-w^{\prime}\|_{1}=4\|w-w^{\prime}\|_{1},$

where the first inequality is because $w_{v}=w^{\prime}_{v}$ holds for $v\neq
u$. The contribution of vertex $u$ to the earth mover’s distance is

$\displaystyle\frac{\sum_{e\in\delta(u)}y_{e}}{w_{u}}\cdot|w^{\prime}_{u}-w_{u}|+\left(\frac{\sum_{e\in\delta(u)}y^{\prime}_{e}}{w^{\prime}_{u}}-\frac{\sum_{e\in\delta(u)}y_{e}}{w_{u}}\right)\cdot
w^{\prime}_{u}$
$\displaystyle\leq\min\left(\frac{\sum_{e\in\delta(u)}y_{e}}{w_{u}},\frac{\sum_{e\in\delta(u)}y^{\prime}_{e}}{w^{\prime}_{u}}\right)\cdot(w^{\prime}_{u}-w_{u})+\left|\frac{\sum_{e\in\delta(u)}y_{e}}{w_{u}}-\frac{\sum_{e\in\delta(u)}y^{\prime}_{e}}{w^{\prime}_{u}}\right|\cdot
w^{\prime}_{u}$

for
$\frac{\sum_{e\in\delta(u)}y_{e}}{w_{u}}\leq\frac{\sum_{e\in\delta(u)}y^{\prime}_{e}}{w^{\prime}_{u}}$
and

$\displaystyle\frac{\sum_{e\in\delta(u)}y^{\prime}_{e}}{w^{\prime}_{u}}\cdot|w^{\prime}_{u}-w_{u}|+\left(\frac{\sum_{e\in\delta(u)}y_{e}}{w_{u}}-\frac{\sum_{e\in\delta(u)}y^{\prime}_{e}}{w^{\prime}_{u}}\right)\cdot
w_{u}$
$\displaystyle\leq\min\left(\frac{\sum_{e\in\delta(u)}y_{e}}{w_{u}},\frac{\sum_{e\in\delta(u)}y^{\prime}_{e}}{w^{\prime}_{u}}\right)\cdot(w^{\prime}_{u}-w_{u})+\left|\frac{\sum_{e\in\delta(u)}y_{e}}{w_{u}}-\frac{\sum_{e\in\delta(u)}y^{\prime}_{e}}{w^{\prime}_{u}}\right|\cdot
w^{\prime}_{u}$

otherwise.

Therefore, the Lipschitz constant of Algorithm 1 is

$\displaystyle\sup_{\begin{subarray}{c}w,w^{\prime}\in\mathbb{R}_{\geq
0}^{V},\\\ w\neq
w^{\prime}\end{subarray}}\frac{\mathrm{EM}_{\mathrm{w}}\left((\textsc{VertexCover}(G,w),w),(\textsc{VertexCover}(G,w^{\prime}),w^{\prime})\right)}{\|w-w^{\prime}\|_{1}}\leq\sup_{\begin{subarray}{c}w,w^{\prime}\in\mathbb{R}_{\geq
0}^{V},\\\ w\neq
w^{\prime}\end{subarray}}\frac{4\|w-w^{\prime}\|_{1}}{\|w-w^{\prime}\|_{1}}=4.$

Hence, the claim holds. ∎

Theorem 2.1 follows by combining Lemmas 2.2 and 2.5.

##  3 Naive Algorithm for Set Cover

The goal of this section is to show the following:

######  Theorem 3.1.

For any $\epsilon>0$, there exists a polynomial-time
$(s+\epsilon)$-approximation algorithm for the minimum set cover problem with
Lipschitz constant $O(\epsilon^{-1}s^{2})$, where $s$ is the maximum size of a
set in the instance.

Algorithm, NaiveSetCover, is presented in Algorithm 2. The idea is simple: For
each element $e\in U$, we sample one set containing $e$ with nearly minimum
weight, and collect these sets to form the output.

1 Procedure  __NaiveSetCover($U,\mathcal{F},w,\epsilon$)__

Input: A set $U$, $\mathcal{F}\subseteq 2^{U}$, a weight vector
$w\in\mathbb{R}_{\geq 0}^{\mathcal{F}}$, and $\epsilon>0$.

2 $s\leftarrow\max_{S\in\mathcal{F}}|S|$;

3 Sample $\bm{b}$ uniformly from $[0,1]$;

4 Let $\bm{\mathcal{C}}\leftarrow\emptyset$;

5 for  _$e\in U$_ do

6 Let $\bm{t}_{e}$ be the minimum integer such that the set
$\bm{X}_{e,\bm{t}_{e}}=\left\\{S\in\mathcal{F}:e\in
S\wedge\left(1+\frac{\epsilon}{s}\right)^{\bm{b}+\bm{t}_{e}}\leq
w_{S}<\left(1+\frac{\epsilon}{s}\right)^{\bm{b}+\bm{t}_{e}+1}\right\\}$ is
nonempty;

7 Sample $\bm{S}_{e}$ uniformly from $\bm{X}_{e,\bm{t}_{e}}$ and add it to
$\bm{\mathcal{C}}$;

8

9 return $\bm{\mathcal{C}}$;

10

Algorithm 2 Naive Lipschitz continuous algorithm for the minimum set cover
problem

We begin by analyzing the approximation ratio.

######  Lemma 3.2.

NaiveSetCover has approximation ratio $s+\epsilon$.

###### Proof.

Let $\mathcal{F}^{*}$ be a minimum set cover of $(U,\mathcal{F},w)$. Then, we
have

$\displaystyle w(\bm{\mathcal{C}})\leq\sum_{e\in
U}\left(1+\frac{\epsilon}{s}\right)\min_{S\ni e}w_{S}=(s+\epsilon)\sum_{e\in
U}\min_{S\ni e}\frac{w_{S}}{s}$ $\displaystyle\leq(s+\epsilon)\sum_{e\in
U}\sum_{S\ni e\colon
S\in\mathcal{F}^{*}}\frac{w_{S}}{s}=(s+\epsilon)\sum_{S\in\mathcal{F}^{*}}\sum_{e\in
S}\frac{w_{S}}{s}\leq(s+\epsilon)\sum_{S\in\mathcal{F}^{*}}w_{S}=(s+\epsilon)\mathrm{OPT},$

where the last inequality is because $|S|\leq s$ holds for all
$S\in\mathcal{F}$. ∎

Next we analyze the Lipschitz continuity. For a weight vector
$w\in\mathbb{R}_{\geq 0}^{\mathcal{F}}$, let $w^{\prime}=w+\delta\bm{1}_{T}$
for $T\in\mathcal{F}$. Then by Lemma 1.3, it suffices to analyze

$\displaystyle\mathrm{EM}_{\mathrm{w}}\left((\textsc{NaiveSetCover}(U,\mathcal{F},w,\epsilon),w),(\textsc{NaiveSetCover}(U,\mathcal{F},w^{\prime},\epsilon),w^{\prime})\right).$

Moreover, we can assume $\delta\leq w_{T}$ or $w_{T}=0$.

Let $\bm{b}$ and $\bm{b}^{\prime}$ be the parameter $\bm{b}$ sampled in
$\textsc{NaiveSetCover}(U,\mathcal{F},w,\epsilon)$ and
$\textsc{NaiveSetCover}(U,\mathcal{F},w^{\prime},\epsilon)$, respectively. We
use similar notations for $\bm{t}_{e}$, $\bm{X}_{e,\bm{t}_{e}}$ and
$\bm{S}_{e}$. To bound the earth mover’s distance, we consider the coupling
$\mathcal{W}$ between $\left(\bm{b},(\bm{S}_{e})_{e\in U}\right)$ and
$\left(\bm{b}^{\prime},(\bm{S}^{\prime}_{e})_{e\in U}\right)$ defined as
follows: for each $b\in[0,1]$, the probability mass for $\bm{b}=b$ is
transported to that for $\bm{b}^{\prime}=b$. For the probability mass with
$\bm{b}=\bm{b}^{\prime}=b$, for each $e\in E$ and $S\in\mathcal{F}$, the
probability mass for $\bm{S}_{e}=S$ is transported to that for
$\bm{S}^{\prime}_{e}=S$ as much as possible. Suppose
$\left(\left(\bm{b},(\bm{S}_{e})_{e\in
U}\right),\left(\bm{b}^{\prime},(\bm{S}^{\prime}_{e})_{e\in
U}\right)\right)\sim\mathcal{W}$. Then, $\bm{S}_{e}=\bm{S}^{\prime}_{e}$ holds
for $e\in U\setminus T$. The following lemma bounds the probability that
$\bm{S}_{e}=\bm{S}^{\prime}_{e}$ holds for $e\in T$.

######  Lemma 3.3.

Let $e\in T$. If $w_{T}>0$, then we have

$\displaystyle\Pr_{\mathcal{W}}\left[\bm{S}_{e}\neq\bm{S}^{\prime}_{e}\right]\leq\frac{2s\delta}{\epsilon
w_{T}}.$

###### Proof.

We have

$\displaystyle\Pr_{\mathcal{W}}\left[\bm{S}_{e}\neq\bm{S}^{\prime}_{e}\right]$
$\displaystyle\leq\Pr_{b\sim\mathcal{U}([0,1])}\left[\exists
t,\bm{X}_{e,t_{e}}\neq\bm{X}^{\prime}_{e,t_{e}}\mid\bm{b}=\bm{b}^{\prime}=b\right]$
$\displaystyle=\Pr_{b\sim\mathcal{U}([0,1])}\left[\left\lfloor{\log_{1+\epsilon/s}w_{T}-b}\right\rfloor\neq\left\lfloor{\log_{1+\epsilon/s}(w_{T}+\delta)-b}\right\rfloor\right]$
$\displaystyle=\left(\log_{1+\epsilon/s}(w_{T}+\delta)-\log_{1+\epsilon/s}w_{T}\right)=\log_{1+\epsilon/s}\left(1+\frac{\delta}{w_{T}}\right)$
$\displaystyle\leq\frac{\delta}{w_{T}\log(1+\epsilon/s)}\leq\frac{\delta}{w_{T}}\cdot\frac{2s}{\epsilon},$

where the third inequality is from $\log(1+x)\leq x$ and the last inequality
is from $\log\left(1+\epsilon/s\right)\geq\epsilon/(2s)$ for $\epsilon/s\leq
1$. ∎

Using this, we can bound the Lipschitz constant of NaiveSetCover.

######  Lemma 3.4.

NaiveSetCover has Lipschitz constant $O(\epsilon^{-1}s^{2})$.

###### Proof.

For each $e\in T$, we have

$\displaystyle w_{\bm{S}_{e}}$
$\displaystyle\leq\left(1+\frac{\epsilon}{s}\right)\min_{S\ni
e}w_{S}\leq\left(1+\frac{\epsilon}{s}\right)w_{T},\text{ and}$ $\displaystyle
w^{\prime}_{\bm{S}^{\prime}_{e}}$
$\displaystyle\leq\left(1+\frac{\epsilon}{s}\right)\min_{S\ni
e}w^{\prime}_{S}\leq\left(1+\frac{\epsilon}{s}\right)w^{\prime}_{T}=\left(1+\frac{\epsilon}{s}\right)(w_{T}+\delta).$

Assume $w_{T}=0$. Then, we have

$\displaystyle\mathrm{EM}_{\mathrm{w}}\left((\textsc{NaiveSetCover}(U,\mathcal{F},w,\epsilon),w),(\textsc{NaiveSetCover}(U,\mathcal{F},w+\delta\bm{1}_{T},\epsilon),w+\delta\bm{1}_{T})\right)$
$\displaystyle\leq\mathop{\mathbf{E}}_{\mathcal{W}}\left[\sum_{e\in
U,\bm{S}_{e}\neq\bm{S}^{\prime}_{e}}\left(w_{\bm{S}_{e}}+w^{\prime}_{\bm{S}^{\prime}_{e}}\right)\right]\leq\mathop{\mathbf{E}}_{\mathcal{W}}\left[\sum_{e\in
T}\left(w_{\bm{S}_{e}}+w^{\prime}_{\bm{S}^{\prime}_{e}}\right)\right]\leq
s\cdot\left(0+\left(1+\frac{\epsilon}{s}\right)\delta\right)\leq 2s\delta\leq
12s^{2}\epsilon^{-1}\delta,$

where the third inequality is from $w_{T}=0$ and the last inequality is from
$\frac{\epsilon}{s}\leq 1$. Otherwise, we have

$\displaystyle\mathrm{EM}_{\mathrm{w}}\left((\textsc{NaiveSetCover}(U,\mathcal{F},w,\epsilon),w),(\textsc{NaiveSetCover}(U,\mathcal{F},w+\delta\bm{1}_{T},\epsilon),w+\delta\bm{1}_{T})\right)$
$\displaystyle\leq\mathop{\mathbf{E}}_{\mathcal{W}}\left[\sum_{e\in
U,\bm{S}_{e}\neq\bm{S}^{\prime}_{e}}\left(w_{\bm{S}_{e}}+w^{\prime}_{\bm{S}^{\prime}_{e}}\right)\right]$
$\displaystyle\leq\sum_{e\in
T}\left(\Pr_{\mathcal{W}}\left[\bm{S}_{e}\neq\bm{S}^{\prime}_{e}\right]\cdot\mathop{\mathbf{E}}_{\mathcal{W}}\left[w_{\bm{S}_{e}}+w^{\prime}_{\bm{S}^{\prime}_{e}}\mid\bm{S}_{e}\neq\bm{S}^{\prime}_{e}\right]\right)$
$\displaystyle\leq\sum_{e\in
T}\left(\Pr_{\mathcal{W}}\left[\bm{S}_{e}\neq\bm{S}^{\prime}_{e}\right]\cdot\left(1+\frac{\epsilon}{s}\right)(w_{T}+(w_{T}+\delta))\right)$
$\displaystyle\leq s\cdot\frac{2s\delta}{\epsilon
w_{T}}\cdot\left(1+\frac{\epsilon}{s}\right)\cdot
3w_{T}\leq\frac{12s^{2}}{\epsilon}\cdot\delta,$

where the fourth inequality is from Lemma 3.3 and $\delta\leq w_{T}$, and the
last inequality is from $\epsilon/s\leq 1$. Therefore, Algorithm 2 has
Lipschitz constant
$\frac{12\epsilon^{-1}s^{2}\cdot\delta}{\delta}=O(\epsilon^{-1}s^{2})$. ∎

Theorem 3.1 follows by combining Lemmas 3.2 and 3.4.

##  4 Greedy-based Algorithm for Set Cover

In this section, we provide an algorithm for the set cover problem where the
size of each set is at most $s$ and each element appears in at most $f$ sets.
Specifically, we show the following:

######  Theorem 4.1.

For any $\epsilon\in(0,1]$, there exists an
$\left(H_{s}+\epsilon\right)$-approximation algorithm for the minimum set
cover problem with Lipschitz constant $\exp{O\left(\epsilon^{-2}\left(s+\log
f\right)s^{2}\log^{3}s\right)}$, where $H_{s}:=\sum_{i=1}^{s}(1/i)$. The time
complexity is polynomial when $s=O(\log n)$, where $n$ is the number of
elements.

###  4.1 Algorithm Description

1 Procedure  __ClassicalGreedy($U,\mathcal{F},w$)__

Input: A set $U$, $\mathcal{F}\subseteq 2^{U}$, and a weight vector
$w\in\mathbb{R}_{\geq 0}^{\mathcal{F}}$.

2 $\mathcal{C}\leftarrow\emptyset,R\leftarrow V$;

3 while  _$R\neq\emptyset$_ do

4 Let $S=\mathrm{argmin}_{S^{\prime}\in\mathcal{F}\colon R\cap
S^{\prime}\neq\emptyset}w_{S^{\prime}}/|R\cap S^{\prime}|$;

5 Add $S$ to $\mathcal{C}$;

6 $R\leftarrow R\setminus S$;

7

8 return $\mathcal{C}$;

9

Algorithm 3 Greedy algorithm for the minimum set cover problem [4, 9, 12]

1 Procedure  __LipschitzGreedy($U,\mathcal{F},w,K,M$)__

Input: A set $U$, $\mathcal{F}\subseteq 2^{U}$, a weight vector
$w\in\mathbb{R}_{\geq 0}^{\mathcal{F}}$, and $K,M\in\mathbb{Z}_{\geq 1}$.

2 $s\leftarrow\max_{S\in\mathcal{F}}|S|$;

3 Sample $\bm{b}$ uniformly from $[0,1]$;

4 Let $\bm{\pi}$ be a random permutation over $\\{A\subseteq U\colon|A|\leq
s\\}$;

5 $\bm{Q}\leftarrow\emptyset$;

6 for  _$S\in\mathcal{F}$_ do

7 Let $\bm{i}_{S}$ be the integer $s^{K\bm{b}+\bm{i}_{S}/M}\leq
w_{S}<s^{K\bm{b}+(\bm{i}_{S}+1)/M}$ if $w_{S}>0$, otherwise
$\bm{i}_{S}=-\infty$;

8 for  _$\emptyset\neq A\subseteq S$_ do

9 if  _$\bm{i}_{S}\bmod KM\geq M\log_{s}|A|$ _ then

10 Add $\left(\bm{i}_{S}-M\log_{s}|A|,A,S\right)$ to $\bm{Q}$;

11

12

13

14 $\bm{\mathcal{C}}\leftarrow\emptyset,\bm{R}\leftarrow U$;

15 for  _$(x,A,S)\in\bm{Q}$ in increasing order of $x$, where ties are broken
according to $\pi(A)$_ do

16 if  _$A\subseteq\bm{R}$_ then

17 Add $S$ to $\bm{\mathcal{C}}$;

18 Remove all elements in $A$ from $\bm{R}$;

19

20

21 return $\bm{\mathcal{C}}$;

22

Algorithm 4 Lipschitz continuous algorithm for the minimum set cover problem

Before explaining the algorithm, let us first introduce the
$H_{s}$-approximation algorithm for the set cover problem given by Johnson
[9], Lovász [12] and Chvátal [4]. The $H_{s}$-approximation algorithm in
Algorithm 3 follows a greedy approach where sets are sequentially added to the
solution starting from an empty set. At each step of the greedy algorithm,
denoting the set of currently uncovered elements as $R\subseteq U$, the
algorithm selects a set $S\in\mathcal{F}$ with $R\cap S\neq\emptyset$ that
minimizes $w_{S}/|R\cap S|$ and adds it to the solution.

To evaluate the Lipschitz continuity, let us compare the processes of
ClassicalGreedy($U,\mathcal{F},w$) and
ClassicalGreedy($U,\mathcal{F},w+\delta\bm{1}_{T}$) for $\delta>0$ and
$T\in\mathcal{F}$. Let $S_{i}$ and $S^{\prime}_{i}$ be the set selected during
the $i$-th iteration of the loop starting from Line 3 for
ClassicalGreedy($U,\mathcal{F},w$) and
ClassicalGreedy($U,\mathcal{F},w+\delta\bm{1}_{T}$), respectively. Let $R_{i}$
and $R^{\prime}_{i}$ be the $R$ sets at the end of that iteration for
ClassicalGreedy($U,\mathcal{F},w$) and
ClassicalGreedy($U,\mathcal{F},w+\delta\bm{1}_{T}$), respectively. Assume
there exists $i$ such that $T=S_{i}$. Up until the $i$-th iteration,
ClassicalGreedy behaves the same for both instances, and particularly,
$R_{j}=R^{\prime}_{j}$ for $j<i$. However, since $S_{i}$ may not be equal to
$S^{\prime}_{i}$, $R_{i}$ may not be equal to $R^{\prime}_{i}$. Thus, the
value of $|R\cap S|$ in the $(i+1)$-st iteration of
ClassicalGreedy($U,\mathcal{F},w$) may differ from its value in
ClassicalGreedy($U,\mathcal{F},w+\delta\bm{1}_{T}$) (even for $S\neq T$), and
we cannot guarantee $S_{i+1}=S^{\prime}_{i+1}$, causing the algorithm’s
behavior to diverge for the two instances.

To address this problem, we modify the criterion for selecting a set $S$ to be
added to set $\mathcal{C}$ in the loop starting from Line 3 in
ClassicalGreedy. We define a multifamily of sets $\mathcal{F}^{\downarrow}$ as
$\bigcup_{S\in\mathcal{F}}(2^{S}\setminus\emptyset)$ as the union of
(nonempty) subsets of sets in $\mathcal{F}$, and we define the weight
$w^{\downarrow}_{A}$ of set $A\in\mathcal{F}^{\downarrow}$ as the weight of
its corresponding set in $\mathcal{F}$. In this context, we can interpret Line
3 in ClassicalGreedy as the process of selecting an set $A$ from
$\mathcal{F}^{\downarrow}$ that satisfies $A\subseteq R$ and minimizes
$w^{\downarrow}_{A}/|A|$.

Let us describe our algorithm, LipschitzGreedy, given in Algorithm 4. It takes
two positive integers, $K$ and $M$. Then, we sample two parameters $\bm{b}$
and $\bm{\pi}$ from uniform distributions over $[0,1]$ and permutations over
$\\{A\subseteq U\colon|A|\leq s\\}$, respectively. For the purpose we describe
later, at Line 4, we round the weight of each set $S$ by setting
$\bm{i}_{S}=\left\lfloor{M\log_{s}w_{S}+\bm{c}_{1}}\right\rfloor$, where
$\bm{c}_{1}$ is a constant determined by $K$, $M$, and $\bm{b}$, and the new
weight $\widehat{\bm{w}}_{S}$ is given by $\bm{c}_{2}\cdot
s^{\bm{i}_{S}/M}\approx w_{S}$, where $\bm{c}_{2}$ is a constant determined by
$K$, $M$, and $\bm{b}$.

At Lines 4 and 4, we extend the weight $\widehat{\bm{w}}_{S}$ onto
$\bm{\mathcal{F}}^{\downarrow}$ described above. Here, we prepare a triplet
$(x,A,S)$ for each $A\in\bm{\mathcal{F}}^{\downarrow}$, where $x$ is the
logarithm of the extended weight $\widehat{\bm{w}}^{\downarrow}_{A}$ and $S$
is the set in $\mathcal{F}$ corresponding to $A$. However, we do so only for
$A\in\bm{\mathcal{F}}^{\downarrow}$ with
$\left\lfloor{\frac{\bm{i}_{S}-M\log_{s}|A|}{KM}}\right\rfloor=\left\lfloor{\frac{\bm{i}_{S}}{KM}}\right\rfloor=:\bm{l}(S)$,
where the equality is guaranteed by Line 4. We call the value $\bm{l}(S)$ the
_level_ of $S$. We note that, for every $e\in S$, the tuple $(x,\\{e\\},S)$ is
always added to $\bm{Q}$ because $M\log_{s}|\\{e\\}|=0$. Finally, in the loop
starting at Line 4, we execute the classical greedy algorithm on these sets
and weights.

The approximation ratio is analyzed as follows. We know that the loop starting
at Line 4 demonstrates $H_{s}$-approximation algorithm for the instance
$(U,\bm{\mathcal{F}}^{\downarrow},\widehat{\bm{w}}^{\downarrow})$. To complete
the analysis, we bound
$\mathrm{OPT}_{U,\bm{\mathcal{F}}^{\downarrow},\widehat{\bm{w}}^{\downarrow}}$
by $\mathrm{OPT}_{U,\mathcal{F},w}$. First, we prove that the rounding process
of the weight $w$ into $\widehat{\bm{w}}$ multiplies the approximation ratio
by at most $s^{1/M}$. Let $\mathcal{C}^{*}$ be the solution that attains
$\mathrm{OPT}_{U,\mathcal{F},w}$. We construct a solution
$\widehat{\bm{\mathcal{C}}}^{*}$ for the instance
$(U,\bm{\mathcal{F}}^{\downarrow},\widehat{\bm{w}}^{\downarrow})$ as follows:
For each $S\in\mathcal{C}^{*}$, include it in $\widehat{\bm{\mathcal{C}}}^{*}$
if $(x,S,S)$ is added to $\bm{Q}$ in Line 4; otherwise, include all one-
element subsets of $S$ in $\widehat{\bm{\mathcal{C}}}^{*}$. The probability
that each $S\in\mathcal{C}^{*}$ is not included in
$\widehat{\bm{\mathcal{C}}}^{*}$ is at most $K^{-1}$ and in this case, at most
$s$ one-element subsets of $S$ is included in $\widehat{\bm{\mathcal{C}}}^{*}$
instead. Therefore,
$\mathrm{OPT}_{U,\mathcal{F}^{\downarrow},\widehat{\bm{w}}^{\downarrow}}$ is
bounded by $\left(1+\frac{s-1}{K}\right)$ times
$\mathrm{OPT}_{U,\mathcal{F},\widehat{\bm{w}}}$, that is,
$\left(1+\frac{s-1}{K}\right)\cdot s^{1/M}$ times
$\mathrm{OPT}_{U,\mathcal{F},w}$, in expectation. By taking sufficiently large
$K$ and $M$, we obtain an approximation guarantee of $H_{s}+\epsilon$.

Now we overview the analysis of the Lipschitz continuity. Let us introduce an
intuition to bound

$\displaystyle\mathrm{EM}_{\mathrm{w}}\left((\textsc{LipschitzGreedy}(U,\mathcal{F},w,K,M),w),(\textsc{LipschitzGreedy}(U,\mathcal{F},w+\delta\bm{1}_{T},K,M),w+\delta\bm{1}_{T})\right).$

For simplicity, consider the case where the level of $T$ is $l$ in both
LipschitzGreedy($U,\mathcal{F},w,K,M$) and
LipschitzGreedy($U,\mathcal{F},w+\delta\bm{1}_{T},K,M$). Before adding sets of
level $l$, the algorithm’s behavior is identical for both instances.
Similarly, after adding the sets of level $l$,
$\bm{R}=\bigcup_{S\in\mathcal{F},\bm{l}(S)\leq l}S$ is the same for both
instances. Therefore, the behavior remains the same when adding sets of level
$l+1$ or higher. Thus, only the sets with level $l$ affect the Lipschitz
constant of the whole algorithm.

Here, we review the results of the dynamic distributed independent set by
Censor-Hillel, Haramaty, and Karnin [3]. Although their original result is for
the independent set problem on graphs, it can be easily interpreted for the
set cover problem using a line graph. For a set system $(U,\mathcal{F})$, a
subfamily $\mathcal{P}\subseteq\mathcal{F}$ is called a _set packing_ if no
two sets in $\mathcal{P}$ intersects. For a permutation $\pi$ over
$\mathcal{F}$, we consider the following greedy algorithm
Packing($U,\mathcal{F},\pi$) for the set packing problem: It iterates through
the sets $S\in\mathcal{F}$ in order of $\pi(S)$ and includes a set $S$ in the
solution only if it has no intersection with any set included in the solution.
This process allows us to construct a maximal set packing. The result in
Censor-Hillel, Haramaty, and Karnin states the following.

######  Lemma 4.2 ([3]).

If $\pi$ is chosen uniformly at random, then for any $X\in\mathcal{F}$, we
have

$\displaystyle\mathop{\mathbf{E}}_{\pi}\left[\textsc{Packing}(U,\mathcal{F},\pi)\;\triangle\;\textsc{Packing}(U,\mathcal{F}\setminus\\{X\\},\pi)\right]\leq
2,$

where we abuse notation $\pi$ to represent the permutation obtained by
removing $\pi(X)$ from $\pi$, indicating the permutation on
$\mathcal{F}\setminus X$.

For a fixed level $l$, there are at most $sKM$ different weights
$\widehat{\bm{w}}^{\downarrow}(A)$ for sets
$A\in\bm{\mathcal{F}}^{\downarrow}$ with level $l$, because there are at most
$\log_{s^{1/M}}s^{K}=KM$ candidate values for $\bm{i}_{S}$ and $s$ values for
$|A|$ (this is why we rounded the weight $w$ into $\widehat{\bm{w}}$). Let
$y_{k}$ be the $k$-th smallest value among such values and
$\bm{\mathcal{C}}_{k}$ be the family of sets
$A\in\bm{\mathcal{F}}^{\downarrow}$ with
$\widehat{\bm{w}}^{\downarrow}_{A}=y_{k}$ that is added to $\bm{\mathcal{C}}$
in the loop starting at Line 4. Using Lemma 4.2, we can bound the quantity
$\mathop{\mathbf{E}}\left[\left|\bm{\mathcal{C}}_{k}\;\triangle\;\bm{\mathcal{C}}^{\prime}_{k}\right|\right]$
using
$\mathop{\mathbf{E}}\left[\left|\bm{\mathcal{C}}_{k^{\prime}}\;\triangle\;\bm{\mathcal{C}}^{\prime}_{k^{\prime}}\right|\right]$
for $k^{\prime}<k$ and the parameters $s$ and $f$. Consequently,
$\mathop{\mathbf{E}}\left[\left|\bm{\mathcal{C}}_{k}\;\triangle\;\bm{\mathcal{C}}^{\prime}_{k}\right|\right]$
can be bounded as a function of $s$, $f$ and $k$. Since at most $sKM$
different values are possible for $\widehat{\bm{w}}^{\downarrow}_{A})$ with
$l(A)=l$, we can bound the Lipschitz constant by a function of $s$, $f$, $K$
and $M$.

###  4.2 Approximation Ratio

Let us analyze the approximation ratio. We say that a set $S\in\mathcal{F}$ is
_hashed_ (with respect to $\bm{i}_{S}$) if $\bm{i}_{S}\bmod KM<M\log_{s}|S|$.
When a set $S$ is hashed, only singleton subsets of $S$ are added to the set
$\bm{Q}$.

######  Lemma 4.3.

_LipschitzGreedy($U,\mathcal{F},w,K,M$)_ has an approximation ratio
$H_{s}\cdot\left(1+\frac{s-1}{K}\right)\cdot s^{1/M}$.

###### Proof.

Let $\bm{\mathcal{F}}_{\mathrm{hash}}\subseteq\mathcal{F}$ be the set of
hashed sets. Let $\widehat{\bm{\mathcal{F}}}$ be the family of sets over $U$
defined by

$\displaystyle\widehat{\bm{\mathcal{F}}}=(\mathcal{F}\setminus\bm{\mathcal{F}}_{\mathrm{hash}})\cup\\{\\{e\\}:S\in\bm{\mathcal{F}}_{\mathrm{hash}},e\in
S\\}.$

The weight $\widehat{\bm{w}}_{S}$ of a set
$S\in\mathcal{F}\setminus\bm{\mathcal{F}}_{\mathrm{hash}}$ is defined as
$s^{K\bm{b}+(\bm{i}_{S}+1)/M}$, and the weight $\widehat{\bm{w}}_{\\{e\\}}$
for $e\in S\in\bm{\mathcal{F}}_{\mathrm{hash}}$ is defined as
$s^{K\bm{b}+(\bm{i}_{S}+1)/M}$.

Let $\mathcal{C}^{*}\subseteq\mathcal{F}$ be a minimum set cover of the
instance $(U,\mathcal{F},w)$. Let $\widehat{\bm{\mathcal{C}}}^{*}$ be the
family of sets in $\mathcal{F}$ defined by

$\displaystyle(\mathcal{C}^{*}\setminus\bm{\mathcal{F}}_{\mathrm{hash}})\cup\\{\\{e\\}:S\in\mathcal{C}^{*}\cap\bm{\mathcal{F}}_{\mathrm{hash}},e\in
S\\}.$

It is clear that $\widehat{\bm{\mathcal{C}}}^{*}$ is a set cover of
$(U,\widehat{\bm{\mathcal{F}}},\widehat{\bm{w}})$. Furthermore, we have

$\displaystyle\mathop{\mathbf{E}}\left[\mathrm{OPT}_{U,\widehat{\bm{\mathcal{F}}},\widehat{\bm{w}}}\right]\leq\mathop{\mathbf{E}}\left[\widehat{\bm{w}}\left(\widehat{\bm{\mathcal{C}}}^{*}\right)\right]\leq
s^{1/M}\mathop{\mathbf{E}}\left[w\left(\widehat{\bm{\mathcal{C}}}^{*}\right)\right]$
$\displaystyle=s^{1/M}\left(\mathop{\mathbf{E}}\left[w(\mathcal{C}^{*}\setminus\bm{\mathcal{F}}_{\mathrm{hash}})+s\cdot
w(\mathcal{C}^{*}\cap\bm{\mathcal{F}}_{\mathrm{hash}})\right]\right)$
$\displaystyle=s^{1/M}\left(w(\mathcal{C}^{*})+(s-1)\mathop{\mathbf{E}}\left[w(\mathcal{C}^{*}\cap\bm{\mathcal{F}}_{\mathrm{hash}})\right]\right)$
$\displaystyle=s^{1/M}\left(w(\mathcal{C}^{*})+(s-1)\int_{0}^{1}\left(\sum_{S\in\mathcal{C}^{*}\colon\text{hashed
w.r.t.\ }\bm{i}_{S}}w_{S}\right)\mathrm{d}b\right)$ $\displaystyle\leq
s^{1/M}\left(w(\mathcal{C}^{*})+(s-1)\int_{0}^{1}\left(\sum_{S\in\mathcal{C}^{*}\colon\text{hashed
w.r.t.\ }\bm{i}_{S}}w_{S}\right)\mathrm{d}b\right)$
$\displaystyle=s^{1/M}\left(w(\mathcal{C}^{*})+\frac{s-1}{K}w(\mathcal{C}^{*})\right)\leq
s^{1/M}\left(1+\frac{s-1}{K}\right)\mathrm{OPT}_{U,\mathcal{F},w}.$

Here, $\mathrm{OPT}_{U,\mathcal{F},w}$ and
$\mathrm{OPT}_{U,\widehat{\bm{\mathcal{F}}},\widehat{\bm{w}}}$ represent the
optimal values for $(U,\mathcal{F},w)$ and
$(U,\widehat{\bm{\mathcal{F}}},\widehat{\bm{w}})$, respectively.

Recalling that LipschitzGreedy simulates
ClassicalGreedy($U,\widehat{\bm{\mathcal{F}}},\widehat{\bm{w}}$), we have

$\displaystyle\mathop{\mathbf{E}}\left[w\left(\textsc{LipschitzGreedy}(U,\mathcal{F},w,K,M)\right)\right]\leq
H_{s}\mathop{\mathbf{E}}\left[\mathrm{OPT}_{U,\widehat{\bm{\mathcal{F}}},\widehat{\bm{w}}}\right]\leq
H_{s}\cdot s^{1/M}\left(1+\frac{s-1}{K}\right)\mathrm{OPT}_{U,\mathcal{F},w}.$

Therefore the lemma is proved. ∎

###  4.3 Lipschitz Continuity

Now we analyze the Lipschitz constant. By Lemma 1.3, it suffices to evaluate

$\displaystyle\mathrm{EM}_{\mathrm{w}}\left((\textsc{LipschitzGreedy}(U,\mathcal{F},w,K,M),w),(\textsc{LipschitzGreedy}(U,\mathcal{F},w+\delta\bm{1}_{T},K,M),w+\delta\bm{1}_{T})\right).$

Moreover, we can assume $0<\delta\leq w_{T}$ or $w_{T}=0$.

Let $\bm{b}$ and $\bm{b}^{\prime}$ be the parameter $\bm{b}$ sampled in
LipschitzGreedy on $w$ and that on $w+\bm{1}_{T}$, respectively. We use
similar notations for $\bm{\pi}$, $\bm{i}_{S}$, $\bm{Q}$, $\bm{R}$, and
$\bm{\mathcal{C}}$. To bound the earth mover’s distance, we consider the
coupling $\mathcal{W}$ between LipschitzGreedy on $w$ and that on
$w+\delta\bm{1}_{T}$ such that for each $b\in[0,1]$ and permutation $\pi$, the
probability mass for $\bm{b}=b$ and $\bm{\pi}=\pi$ are transported to that for
$\bm{b}^{\prime}=b$ and $\bm{\pi}^{\prime}=\pi$.

Firstly, we evaluate the probability that $\bm{i}_{T}$ is not equal to
$\bm{i}^{\prime}_{T}$.

######  Lemma 4.4.

If $w_{T}>0$, we have
$\Pr\left[\bm{i}_{T}\neq\bm{i}^{\prime}_{T}\right]\leq\frac{\delta
M}{w_{T}\log s}$.

###### Proof.

We have

$\displaystyle\Pr_{\mathcal{W}}\left[\bm{i}_{T}\neq\bm{i}^{\prime}_{T}\right]$
$\displaystyle=\Pr_{\bm{b}\sim\mathcal{U}[0,1]}\bigl{[}\left\lfloor{\left(\log_{s}w_{T}-K\bm{b}\right)M}\right\rfloor\neq\left\lfloor{\left(\log_{s}(w_{T}+\delta)-K\bm{b}\right)M}\right\rfloor\bigr{]}$
$\displaystyle=\left(\log_{s}(w_{T}+\delta)-\log_{s}w_{T}\right)M=\log_{s}\left(1+\frac{\delta}{w_{T}}\right)\cdot
M\leq\frac{\delta M}{w_{T}\log s},$

where the second equality is from $(K\bm{b}\bmod 1)\sim\mathcal{U}([0,1])$
because $K$ is an integer, and the inequality is from $\log(1+x)\leq x$. ∎

Consider the case $\bm{i}_{T}\neq\bm{i}^{\prime}_{T}$. For each
$S\in\mathcal{F}$, let the _level_ of $S$ be
$\bm{l}(S)=\left\lfloor{\frac{\bm{i}_{S}}{KM}}\right\rfloor$. The following is
easy but important.

######  Lemma 4.5.

For $(x_{1},A_{1},S_{1}),(x_{2},A_{2},S_{2})\in\bm{Q}$, if
$\bm{l}(S_{1})<\bm{l}(S_{2})$, then we have $x_{1}<x_{2}$.

###### Proof.

$\bm{l}(S_{2})>-\infty$ holds only if $w_{S_{2}}>0$. Therefore, the lemma is
trivial if $w_{S_{1}}=0$. Assume $w_{S_{1}}>0$. Then, we have

$\displaystyle x_{1}<\left(\bm{l}(S_{1})+1\right)KM\leq\bm{l}(S_{2})KM\leq
x_{2},$

where the last inequality is because in Line 4 of LipschitzGreedy,
$(\bm{i}_{S_{2}}-M\log_{s}|A_{2}|,A_{2},S_{2})$ is added only if
$\bm{i}_{S}\bmod KM\geq\bm{i}_{S_{2}}-M\log_{s}|A_{2}|$. ∎

From Lemma 4.5, it can be observed that the loop starting from Line 4 in
LipschitzGreedy determines whether to include the set $S$ in the output
$\bm{\mathcal{C}}$ in ascending order of their level $\bm{l}(S)$. Therefore,
when all sets $S$ with $\bm{l}(S)\leq k$ have been examined, the set of
elements covered by $\bm{\mathcal{C}}$ is equal to the set of elements
belonging to at least one set with its level at most $k$. Comparing the
behavior of the loops starting from Line 4 in
LipschitzGreedy($U,\mathcal{F},w,K,M$) and
LipschitzGreedy($U,\mathcal{F},w+\delta\bm{1}_{T},K,M$), we have:

  * •

Up until the point where sets with levels less than $\bm{l}(T)$ are being
examined, the behavior is exactly the same.

  * •

Since the sets of elements covered by $\bm{\mathcal{C}}$ and
$\bm{\mathcal{C}}^{\prime}$ are the same just after all sets with level
$\bm{l}^{\prime}(T)$ has been examined (because all one-element subsets of a
set $S\in\mathcal{F}$ with $\bm{l}(S)\leq\bm{l}^{\prime}(T)$ have the same
level as $S$), the algorithm behaves the same when examining sets with a level
greater than $\bm{l}^{\prime}(T)$.

We can assume without loss of generality that there exists no set
$S\in\mathcal{F}$ such that $\bm{l}(T)<\bm{l}(S)<\bm{l}^{\prime}(T)$. In
particular, any set that differs between $\bm{\mathcal{C}}$ and
$\bm{\mathcal{C}}^{\prime}$ has either level $\bm{l}(T)$ or
$\bm{l}^{\prime}(T)$. Let $\bm{X}$ be the set of all possible values taken by
the first component $x$ of the tuples $(x,A,S)$ in $\bm{Q}$ such that
$\bm{l}(S)=\bm{l}(T)$ or $\bm{l}(S)=\bm{l}^{\prime}(T)$. In other words, let

$\displaystyle\bm{X}=$
$\displaystyle\bigcup_{i=1}^{s}\bigcup_{x=\left\lceil{M\log_{s}i}\right\rceil}^{KM-1}\left\\{\bm{l}(T)KM+x-M\log_{s}i,\bm{l}^{\prime}(T)KM+x-M\log_{s}i\right\\}$

when $w_{T}>0$ and

$\displaystyle\bm{X}=\\{-\infty\\}\cup\bigcup_{i=1}^{s}\bigcup_{x=\left\lceil{M\log_{s}i}\right\rceil}^{KM-1}\left\\{\bm{l}^{\prime}(T)KM+x-M\log_{s}i\right\\}$

when $w_{T}=0$.

For $k=1,\dots,|\bm{X}|$, let $\bm{y}_{k}$ be the $k$-th smallest number in
$\bm{X}$ and let $\bm{\mathcal{C}}_{k}$ (resp.,
$\bm{\mathcal{C}}^{\prime}_{k}$) be the family of sets $S\in\mathcal{F}$ that
was added to $\bm{\mathcal{C}}$ when having examined a tuple
$(x,A,S)\in\bm{Q}$ with $x=\bm{y}_{k}$ in
LipschitzGreedy($U,\mathcal{F},w,K,M$) (resp.,
LipschitzGreedy($U,\mathcal{F},w+\delta\bm{1}_{T},K,M$)).

######  Lemma 4.6.

Let $k\in\\{1,\dots,|X|\\}$. Then, we have

$\displaystyle\mathop{\mathbf{E}}_{\mathcal{W}}\left[\left|\bm{\mathcal{C}}_{k}\;\triangle\;\bm{\mathcal{C}}^{\prime}_{k}\right|\right]\leq(2^{s}sf+1)^{k+3}.$

###### Proof.

We prove this by induction on $k$. Let $\bm{D}_{k}$ (resp.
$\bm{D}^{\prime}_{k}$) be the set of tuples $(x,A,S)$ in $\bm{Q}$ with
$x=y_{k}$ such that $A\subseteq\bm{R}$ holds when
LipschitzGreedy($U,\mathcal{F},w,K,M$) (resp.,
LipschitzGreedy($U,\mathcal{F},w+\delta\bm{1}_{T},K,M$)) starts to examine
tuples $(\tilde{x},\tilde{A},\tilde{S})$ in $\bm{Q}$ with $\tilde{x}=y_{k}$.
Furthermore, let $\bm{R}_{k}$ (resp. $\bm{R}^{\prime}_{k}$) be $\bm{R}$ at
that time. From Lemma 4.2, we have

$\displaystyle\mathop{\mathbf{E}}_{\mathcal{W}}\left[\left|\bm{\mathcal{C}}_{k}\;\triangle\;\bm{\mathcal{C}}^{\prime}_{k}\right|\right]\leq
2\cdot\mathop{\mathbf{E}}_{\mathcal{W}}\left[\left|\bm{D}_{k}\;\triangle\;\bm{D}^{\prime}_{k}\right|\right].$

Moreover,

$\displaystyle\mathop{\mathbf{E}}_{\mathcal{W}}\left[\left|\bm{R}_{k+1}\;\triangle\;\bm{R}^{\prime}_{k+1}\right|\right]\leq
s\cdot\mathop{\mathbf{E}}_{\mathcal{W}}\left[\sum_{i=1}^{k}\left|\bm{\mathcal{C}}_{k}\;\triangle\;\bm{\mathcal{C}}^{\prime}_{k}\right|\right].$

Since each $e\in\bm{R}_{k+1}\;\triangle\;\bm{R}^{\prime}_{k+1}$ belongs to $A$
for at most $2^{s}f$ tuples $(x,A,S)\in Q$, we have

$\displaystyle\mathop{\mathbf{E}}_{\mathcal{W}}\left[\left|\bm{D}_{k+1}\;\triangle\;\bm{D}^{\prime}_{k+1}\right|\right]\leq
f\cdot
2^{s}\cdot\mathop{\mathbf{E}}_{\mathcal{W}}\left[\left|\bm{R}_{k+1}\;\triangle\;\bm{R}^{\prime}_{k+1}\right|\right]+2\cdot
2^{s},$

where the last term counts the number of tuples $(x,A,S)$ with $S=T$. Thus, we
have

$\displaystyle\mathop{\mathbf{E}}_{\mathcal{W}}\left[\left|\bm{\mathcal{C}}_{k+1}\;\triangle\;\bm{\mathcal{C}}^{\prime}_{k+1}\right|\right]\leq
2\cdot\mathop{\mathbf{E}}_{\mathcal{W}}\left[\left|\bm{D}_{k+1}\;\triangle\;\bm{D}^{\prime}_{k+1}\right|\right]$
$\displaystyle\leq f\cdot
2^{s}\cdot\mathop{\mathbf{E}}_{\mathcal{W}}\left[\left|\bm{R}_{k+1}\;\triangle\;\bm{R}^{\prime}_{k+1}\right|\right]+2\cdot
2^{s}\leq f\cdot 2^{s}\cdot
s\cdot\mathop{\mathbf{E}}_{\mathcal{W}}\left[\sum_{i=1}^{k}\left|\bm{\mathcal{C}}_{k}\;\triangle\;\bm{\mathcal{C}}^{\prime}_{k}\right|\right]+2\cdot
2^{s}.$

Thus, we obtain

$\displaystyle\mathop{\mathbf{E}}_{\mathcal{W}}\left[\left|\bm{\mathcal{C}}_{k}\;\triangle\;\bm{\mathcal{C}}^{\prime}_{k}\right|\right]\leq\left(2^{s}sf+1\right)^{k+3}-2\cdot
2^{s}$

by induction. Therefore the lemma holds. ∎

Since there are at most $2sKM$ numbers in $X$, we have the following.

######  Lemma 4.7.

We have

$\displaystyle\mathop{\mathbf{E}}_{\mathcal{W}}\left[\left|\bm{\mathcal{C}}\;\triangle\;\bm{\mathcal{C}}^{\prime}\right|\right]\leq\left(2^{s}sf+1\right)^{2sKM+4}.$

###### Proof.

We have

$\mathop{\mathbf{E}}_{\mathcal{W}}\left[\left|\bm{\mathcal{C}}\;\triangle\;\bm{\mathcal{C}}^{\prime}\right|\right]=\sum_{k=1}^{|X|}\mathop{\mathbf{E}}_{\mathcal{W}}\left[\left|\bm{\mathcal{C}}_{k}\;\triangle\;\bm{\mathcal{C}}^{\prime}_{k}\right|\right]\leq\sum_{k=1}^{|X|}(2^{s}sf+1)^{k+3}\leq(2^{s}sf+1)^{|X|+4}\leq\left(2^{s}sf+1\right)^{2sKM+4}.\qed$

The following is straightforward.

######  Lemma 4.8.

Let $S\in\mathcal{F}$ and assume $S$ has level $\bm{l}(T)$ or
$\bm{l}^{\prime}(T)$. Then, $w_{S}\leq s^{K}(w_{T}+\delta)$.

###### Proof.

Since $\bm{l}(S)\leq\bm{l}^{\prime}(T)$, we have

$\displaystyle w_{S}$ $\displaystyle\leq s^{Kb+(i_{S}+1)/M}\leq
s^{Kb+(KM\cdot\bm{l}(S)+KM-1+1)/M}\leq s^{K}\cdot s^{Kb+(KM\cdot\bm{l}(S))/M}$
$\displaystyle\leq s^{K}\cdot s^{Kb+(KM\cdot\bm{l}^{\prime}(T))/M}\leq
s^{K}\cdot w^{\prime}(T)=s^{K}(w_{T}+\delta).\qed$

Therefore, the following holds.

######  Lemma 4.9.

We have

$\displaystyle\mathrm{EM}_{\mathrm{w}}\left(\left(\textsc{LipschitzGreedy}(U,\mathcal{F},w,K,M),w\right),\left(\textsc{LipschitzGreedy}(U,\mathcal{F},w+\delta\bm{1}_{T},K,M),w+\delta\bm{1}_{T}\right)\right)$
$\displaystyle\leq 3M\left(2^{s}sf+1\right)^{5sKM}\cdot\delta.$

###### Proof.

If $w_{T}=0$, we have

$\displaystyle\mathrm{EM}_{\mathrm{w}}\left(\left(\textsc{LipschitzGreedy}(U,\mathcal{F},w,K,M),w\right),\left(\textsc{LipschitzGreedy}(U,\mathcal{F},w+\delta\bm{1}_{T},K,M),w+\delta\bm{1}_{T}\right)\right)$
$\displaystyle\leq\mathop{\mathbf{E}}\left[\left|\bm{\mathcal{C}}\;\triangle\;\bm{\mathcal{C}}^{\prime}\right|\right]\cdot
s^{K}(0+\delta)\leq\left(2^{s}sf+1\right)^{2sKM+4}\cdot
s^{K}\cdot\delta\leq\left(2^{s}sf+1\right)^{2sKM+4+K}\cdot\delta\leq\left(2^{s}sf+1\right)^{5sKM}\cdot\delta,$

where the second inequality is from Lemmas 4.7 and 4.8, and the last
inequality is because $M\geq 1$. Otherwise, we have

$\displaystyle\mathrm{EM}_{\mathrm{w}}\left(\left(\textsc{LipschitzGreedy}(U,\mathcal{F},w,K,M),w\right),\left(\textsc{LipschitzGreedy}(U,\mathcal{F},w+\delta\bm{1}_{T},K,M),w+\delta\bm{1}_{T}\right)\right)$
$\displaystyle\leq\Pr\left[\bm{i}_{T}\neq\bm{i}^{\prime}_{T}\right]\cdot\mathop{\mathbf{E}}\left[\left|\bm{\mathcal{C}}\;\triangle\;\bm{\mathcal{C}}^{\prime}\right|\right]\cdot
s^{K}(w_{T}+\delta)$ $\displaystyle\leq\frac{\delta M}{w_{T}\log
s}\cdot\left(2^{s}sf+1\right)^{2sKM+4}\cdot s^{K}\cdot 2w_{T}\leq
3M\left(2^{s}sf+1\right)^{2sKM+4+K}\cdot\delta\leq
3M\left(2^{s}sf+1\right)^{5sKM}\cdot\delta,$

where the second inequality is from Lemmas 4.4, 4.7, 4.8 and $\delta\leq
w_{T}$, and the third inequality is from $\log s\geq\log 2\geq\frac{2}{3}$. ∎

Now we have the following.

######  Lemma 4.10.

LipschitzGreedy has Lipschitz constant $3M\left(2^{s}sf+1\right)^{5sKM}$.

Next, we prove the main theorem.

###### Proof of Theorem 4.1.

Let $K=\left\lceil{4\epsilon^{-1}H_{s}}\right\rceil(s-1)$ and
$M=\left\lceil{4\epsilon^{-1}H_{s}\log s}\right\rceil$. Then, from Lemma 4.3,
the approximation ratio is

$\displaystyle H_{s}\cdot\left(1+\frac{s-1}{K}\right)\cdot s^{1/M}\leq
H_{s}\cdot\left(1+\frac{\epsilon}{4H_{s}}\right)\cdot
2^{\frac{\epsilon}{4H_{s}}}$ $\displaystyle\leq
H_{s}\cdot\left(1+\frac{\epsilon}{4H_{s}}\right)\cdot\left(1+\frac{\epsilon}{4H_{s}}\right)\leq
H_{s}\cdot\left(1+\frac{\epsilon}{H_{s}}\right)=H_{s}+\epsilon,$

where the second inequality is from $2^{x}\leq 1+x$ holds for $0\leq x\leq 1$,
and the third inequality is from $\epsilon\leq 1$. In this setting of $K$ and
$M$, the Lipschitz constant of LipschitzGreedy is at most

$\displaystyle 3M\left(2^{s}sf+1\right)^{5sKM}\leq 3\cdot
5\epsilon^{-1}H_{s}\log
s\cdot\left(2^{s}sf+1\right)^{5s\cdot\left(5\epsilon^{-1}H_{s}\right)^{2}\cdot(s-1)\log
s}$ $\displaystyle\leq 2^{O\left(\log H_{s}+\log\epsilon^{-1}+\log\log
s+(s+\log s+\log f)\cdot s\cdot H_{s}^{2}\cdot\epsilon^{-2}\cdot s\log
s\right)}\leq 2^{O\left(\epsilon^{-2}\left(s+\log
f\right)s^{2}\log^{3}s\right)},$

where the first inequality is from $K,M\leq 5\epsilon^{-1}$ follows from
$\epsilon\leq 1$. ∎

##  5 LP-based Algorithm for Set Cover

In this section, we design a Lipschitz-continuous algorithm for the minimum
set cover problem that has a sublinear Lipschitz constant for any instance.
Specifically, we show the following:

######  Theorem 5.1.

There exists a polynomial-time randomized algorithm for the minimum set cover
problem that, given a set cover instance $(U,\mathcal{F})$ on $n$ elements and
$m$ sets, a weight vector $w\in\mathcal{R}_{\geq 0}^{\mathcal{F}}$, and
$\epsilon>0$, outputs a family of sets $\bm{\mathcal{S}}\subseteq\mathcal{F}$
with the following properties:

  * •

$\bm{\mathcal{S}}$ is a feasible solution with probability
$1-1/\mathrm{poly}(n)$,

  * •

the total weight of $\bm{\mathcal{S}}$ satisfies
$\mathop{\mathbf{E}}[\sum_{S\in\bm{\mathcal{S}}}w_{S}]=O(\log
n\cdot\mathrm{OPT})+\epsilon\|w\|_{1}$, and

  * •

the algorithm has a Lipschitz constant $O(\epsilon^{-1}\sqrt{m}\log^{2}n)$.

Our algorithm first solves an LP relaxation and then rounds the obtained LP
solution so that the whole process is Lipschitz continuous, and are explained
in Sections 5.1 and 5.2, respectively. Moreover, we provide the proof of
Theorem 5.1 in Section 5.3.

###  5.1 LP Relaxation

We consider the following natural LP relaxation for the set cover problem:

$\displaystyle\begin{array}[]{lll}\text{minimize}&\displaystyle\sum_{S\in\mathcal{F}}w_{S}x_{S},\\\
\text{subject to}&\displaystyle\sum_{S\in\mathcal{F}:e\in S}x_{S}\geq
1&\forall e\in U,\\\ &0\leq x_{S}\leq 1&\forall S\in\mathcal{F}.\end{array}$
(8)

However, the solution to this LP relaxation may not be Lipschitz continuous
with respect to the weight vector $w\in\mathbb{R}_{\geq 0}^{\mathcal{F}}$.
Hence, we consider the following regularized version.

$\displaystyle\begin{array}[]{lll}\mathrm{minimize}&\displaystyle\sum_{S\in\mathcal{F}}w_{S}x_{S}+\frac{\lambda}{2}\sum_{S\in\mathcal{F}}x_{S}^{2}+\frac{\kappa}{2}\sum_{S\in\mathcal{F}}w_{S}x_{S}^{2},\\\
\text{subject to}&\displaystyle\sum_{S\in\mathcal{F}:e\in S}x_{S}\geq
1&\forall e\in U,\\\ &0\leq x_{S}\leq 1&\forall S\in\mathcal{F},\end{array}$
(12)

where $\lambda,\kappa>0$ are parameters. The first and second regularizers
stabilize $x_{S}$ and $w_{S}x_{S}$, respectively. Let RegularizedLP denote the
algorithm that takes an instance $(U,\mathcal{F},w)$ of the set cover problem
and two parameters $\lambda$ and $\kappa$, and then outputs the solution to
(12). In the rest of this section, we show the following:

######  Lemma 5.2.

RegularizedLP returns a feasible solution $x\in\mathbb{R}_{\geq
0}^{\mathcal{F}}$ to LP (8) such that

$\sum_{S\in\mathcal{F}}w_{S}x_{S}\leq\mathrm{OPT}+\frac{\lambda
m}{2}+\frac{\kappa\|w\|_{1}}{2},$

where $\mathrm{OPT}$ is the optimal value of LP (8). For weight vectors
$w,w^{\prime}\in\mathbb{R}_{\geq 0}^{\mathcal{F}}$, let
$x=\textsc{RegularizedLP}(U,\mathcal{F},w)$ and
$x^{\prime}=\textsc{RegularizedLP}(U,\mathcal{F},w^{\prime})$. Then, we have

$\sum_{S\in\mathcal{F}}|w_{S}x_{S}-w^{\prime}_{S}x^{\prime}_{S}|=O\left((1+\kappa)\sqrt{\frac{\|w\|_{1}}{\lambda\kappa}}+1\right).$

As the approximation guarantee of RegularizedLP is evident, we analyze its
Lipschitz constant. Fix $\kappa,\lambda>0$, and let $f_{w}:\mathbb{R}_{\geq
0}^{\mathcal{F}}\to\mathbb{R}$ denote the objective function of (12),
parameterized by the weight vector $w\in\mathbb{R}_{\geq 0}^{\mathcal{F}}$. As
the first regularizer of (12) makes $f_{w}$ strongly convex with respect to
$\|\cdot\|_{2}$, we have the following:

######  Proposition 5.3.

For any $x,y\in\mathbb{R}^{\mathcal{F}}$, we have

$f_{w}(y)\geq f_{w}(x)+\langle\nabla
f_{w}(x),y-x\rangle+\frac{\lambda}{2}\sum_{S\in\mathcal{F}}(x_{S}-y_{S})^{2}.$

Although the following is straightforward, we include the proof for
completeness.

######  Proposition 5.4.

For any $x,y\in\mathbb{R}^{\mathcal{F}}$, we have

$f_{w}(y)\geq f_{w}(x)+\langle\nabla
f_{w}(x),y-x\rangle+\frac{\kappa}{2}\sum_{S\in\mathcal{F}}w_{S}(x_{S}-y_{S})^{2}.$

###### Proof.

Note that
$g_{w}(x):=f_{w}(x)-\frac{\kappa}{2}\sum_{S\in\mathcal{F}}w_{S}x_{S}^{2}$ is
convex. Then for any $x,y\in\mathbb{R}^{\mathcal{F}}$, we have

$\displaystyle g_{w}(y)\geq g_{w}(x)+\langle\nabla g_{w}(x),y-x\rangle$
$\displaystyle\Leftrightarrow$ $\displaystyle
f_{w}(y)-\frac{\kappa}{2}\sum_{S\in\mathcal{F}}w_{S}y_{S}^{2}\geq
f_{w}(x)-\frac{\kappa}{2}\sum_{S\in\mathcal{F}}w_{S}x_{S}^{2}+\langle\nabla
f_{w}(x)-\kappa\sum_{S\in\mathcal{F}}w_{S}x_{S}\bm{1}_{S},y-x\rangle$
$\displaystyle\Leftrightarrow$ $\displaystyle f_{w}(y)\geq
f_{w}(x)+\langle\nabla
f_{w}(x),y-x\rangle+\frac{\kappa}{2}\sum_{S\in\mathcal{F}}w_{S}y_{S}^{2}-\frac{\kappa}{2}\sum_{S\in\mathcal{F}}w_{S}x_{S}^{2}-\kappa\sum_{S\in\mathcal{F}}w_{S}x_{S}(y_{S}-x_{S}).$
$\displaystyle\Leftrightarrow$ $\displaystyle f_{w}(y)\geq
f_{w}(x)+\langle\nabla
f_{w}(x),y-x\rangle+\frac{\kappa}{2}\sum_{S\in\mathcal{F}}w_{S}(x_{S}-y_{S})^{2}.\qed$

###### Proof of the second part of Lemma 5.2.

Fix a weight vector $w\in\mathbb{R}_{\geq 0}^{\mathcal{F}}$ and a set
$S\in\mathcal{F}$. Let $w^{\prime}\in\mathbb{R}_{\geq 0}^{\mathcal{F}}$ be a
vector obtained from $w$ by increasing $w_{S}$ by $\delta>0$. By a similar
argument to the proof of Lemma 1.3, it suffices to show that the claim holds
for $w$ and $w^{\prime}$. Let $x$ and $x^{\prime}$ be the optimal solutions to
(12) for the instances $(U,\mathcal{F},w)$ and $(U,\mathcal{F},w^{\prime})$,
respectively.

We consider the quantity
$D:=f_{w}(x^{\prime})-f_{w}(x)+f_{w^{\prime}}(x)-f_{w^{\prime}}(x^{\prime})\geq
0$. First, we have

$\displaystyle
D=f_{w}(x^{\prime})-f_{w}(x)+f_{w^{\prime}}(x)-f_{w^{\prime}}(x^{\prime})$
$\displaystyle=w_{S}x^{\prime}_{S}-w_{S}x_{S}+w^{\prime}_{S}x_{S}-w^{\prime}_{S}x^{\prime}_{S}+\frac{\kappa}{2}\left(w_{S}(x^{\prime}_{S})^{2}-w_{S}x_{S}^{2}+w^{\prime}_{S}x_{S}^{2}-w^{\prime}_{S}(x^{\prime}_{S})^{2}\right)$
$\displaystyle=\delta(x_{S}-x^{\prime}_{S})+\frac{\kappa\delta}{2}(x_{S}^{2}-(x^{\prime}_{S})^{2})$
$\displaystyle\leq\delta(1+\kappa)(x_{S}-x^{\prime}_{S}),$ (13)

where the last inequality is by $x_{S}+x^{\prime}_{S}\leq 2$. The above
inequality also implies $x_{S}\geq x^{\prime}_{S}$ because $D\geq 0$.

We now consider showing lower bounds on $D$. By Proposition 5.3, we have

$\displaystyle f_{w}(x^{\prime})-f_{w}(x)$ $\displaystyle\geq\langle\nabla
f_{w}(x),x^{\prime}-x\rangle+\frac{\lambda}{2}\|x^{\prime}-x\|_{2}^{2}\geq\frac{\lambda}{2}\|x^{\prime}-x\|_{2}^{2},\text{
and}$ $\displaystyle f_{w^{\prime}}(x)-f_{w^{\prime}}(x^{\prime})$
$\displaystyle\geq\langle\nabla
f_{w^{\prime}}(x),x-x^{\prime}\rangle+\frac{\lambda}{2}\|x-x^{\prime}\|_{2}^{2}\geq\frac{\lambda}{2}\|x-x^{\prime}\|_{2}^{2}.$

Hence, we have

$\displaystyle D\geq\lambda\|x-x^{\prime}\|_{2}^{2}.$ (14)

Combining (13) and (14), we obtain

$\displaystyle\|x^{\prime}-x\|_{2}^{2}\leq\frac{\delta(1+\kappa)}{\lambda}(x_{S}-x^{\prime}_{S}).$

In particular, this implies

$\displaystyle x_{S}-x^{\prime}_{S}\leq\frac{\delta(1+\kappa)}{\lambda}.$ (15)

By Proposition 5.4, we have

$\displaystyle f_{w}(x^{\prime})-f_{w}(x)$ $\displaystyle\geq\langle\nabla
f_{w}(x),x^{\prime}-x\rangle+\frac{\kappa}{2}\sum_{T\in\mathcal{F}}w_{T}(x^{\prime}_{T}-x_{T})^{2}\geq\frac{\kappa}{2}\sum_{T\in\mathcal{F}}w_{T}(x^{\prime}_{T}-x_{T})^{2},\text{
and}$ $\displaystyle f_{w^{\prime}}(x)-f_{w^{\prime}}(x^{\prime})$
$\displaystyle\geq\langle\nabla
f_{w^{\prime}}(x),x-x^{\prime}\rangle+\frac{\kappa}{2}\sum_{T\in\mathcal{F}}w^{\prime}_{T}(x^{\prime}_{T}-x_{T})^{2}\geq\frac{\kappa}{2}\sum_{T\in\mathcal{F}}w^{\prime}_{T}(x^{\prime}_{T}-x_{T})^{2}.$

Hence, we have

$\displaystyle
D\geq\kappa\sum_{T\in\mathcal{F}}(w_{T}+w^{\prime}_{T})(x_{T}-x^{\prime}_{T})^{2}.$
(16)

Combining (13) and (16), and then applying (15), we have

$\displaystyle\sum_{T\in\mathcal{F}}(w_{T}+w^{\prime}_{T})(x_{T}-x^{\prime}_{T})^{2}\leq\frac{\delta(1+\kappa)}{\kappa}(x_{S}-x^{\prime}_{S})\leq\frac{\delta^{2}(1+\kappa)^{2}}{\lambda\kappa}.$
(17)

Then, we have

$\displaystyle\sum_{T\in\mathcal{F}}|w_{T}x_{T}-w^{\prime}_{T}x^{\prime}_{T}|=\sum_{T\in\mathcal{F}}w_{T}|x_{T}-x^{\prime}_{T}|+|w_{S}x_{S}-w^{\prime}_{S}x^{\prime}_{S}|-w_{S}|x_{S}-x^{\prime}_{S}|$
$\displaystyle\leq\sum_{T\in\mathcal{F}}w_{T}|x_{T}-x^{\prime}_{T}|+\delta
x^{\prime}_{S}$ (by $w^{\prime}_{S}=w_{S}+\delta$ and the triangle inequality)
$\displaystyle\leq\sqrt{\sum_{T\in\mathcal{F}}w_{T}(x_{T}-x^{\prime}_{T})^{2}}\sqrt{\sum_{T\in\mathcal{F}}w_{T}}+\delta
x^{\prime}_{S}$ (by Cauchy-Schwarz)
$\displaystyle\leq\sqrt{\frac{\delta^{2}(1+\kappa)^{2}}{\lambda\kappa}}\sqrt{\sum_{T\in\mathcal{F}}w_{T}}+\delta$
(by (17) and $x^{\prime}_{S}\leq 1$)
$\displaystyle\leq\delta(1+\kappa)\sqrt{\frac{\sum_{T\in\mathcal{F}}w_{T}}{\lambda\kappa}}+\delta.$

Hence, the claim holds. ∎

###  5.2 Rounding

1 Procedure  __RoundingSC($U,\mathcal{F},x$)__

Input: A set $U$, $\mathcal{F}\subseteq 2^{U}$, and a vector
$x\in[0,1]^{\mathcal{F}}$.

2 $\bm{\mathcal{S}}\leftarrow\emptyset$;

3 $K\leftarrow O(\log n)$;

4 for  _$K$ times_ do

5 for  _$S\in\mathcal{F}$_ do

6 Add $S$ to $\bm{\mathcal{S}}$ with probability $x_{S}$.

7

8 return $\bm{\mathcal{S}}$.

Algorithm 5 Rounding algorithm for the set cover problem

Next, we design a Lipschitz continuous rounding algorithm for LP (8). Our
rounding algorithm, RoundingSC, given in Algorithm 5 is standard, and our
focus is to show that it has a stability property that can help show the
Lipschitz continuity of our algorithm for the set cover problem.

######  Lemma 5.5.

Let $(U,\mathcal{F})$ be a set cover instance on $n$ elements and
$w\in\mathbb{R}_{\geq 0}^{\mathcal{F}}$ be a weight vector. Let
$\bm{\mathcal{S}}=\textsc{RoundingSC}(U,\mathcal{F},x)$, where and
$x\in\mathbb{R}^{\mathcal{F}}$ is a feasible solution to LP (8). Then,
$\bm{\mathcal{S}}$ is a feasible set cover with probability
$1-1/\mathrm{poly}(n)$, and

$\mathop{\mathbf{E}}\left[\sum_{S\in\bm{\mathcal{S}}}w_{S}\right]\leq
O\left(\sum_{S\in\mathcal{F}}w_{S}x_{S}\log n\right).$

Let $w,w^{\prime}\in\mathbb{R}_{\geq 0}^{\mathcal{F}}$ be weight vectors and
$x,x^{\prime}\in[0,1]^{\mathcal{F}}$ be feasible solutions to LP (8). For
$\bm{\mathcal{S}}=\textsc{RoundingSC}(U,\mathcal{F},x)$ and
$\bm{\mathcal{S}}^{\prime}=\textsc{RoundingSC}(U,\mathcal{F},x^{\prime})$, we
have

$\mathrm{EM}_{\mathrm{w}}((\bm{\mathcal{S}},w),(\bm{\mathcal{S}}^{\prime},w^{\prime}))\leq
O\left(\left(\|w-w^{\prime}\|_{1}+\sum_{S\in\mathcal{F}}|w_{S}x_{S}-w^{\prime}_{S}x^{\prime}_{S}|\right)\log
n\right).$

###### Proof.

We first show that $\bm{\mathcal{S}}$ is feasible with high probability. The
probability that an element $e\in U$ is not covered is

$\prod_{S\in\mathcal{F}:e\in S}(1-x_{S})^{K}\leq\prod_{S\in\mathcal{F}:e\in
S}\exp(-Kx_{S})=\exp\left(-K\sum_{S\in\mathcal{F}:e\in
S}x_{S}\right)\leq\exp(-K)\leq\frac{1}{\mathrm{poly}(n)}$

by setting the hidden constant in $K$ to be large enough. By a union bound
over elements in $U$, the probability that the output is infeasible is at most
$1/\mathrm{poly}(n)$.

It is clear that the expected total weight of $\bm{\mathcal{S}}$ is as stated.

Now, we consider the Lipschitz continuity. For $S\in\mathcal{F}$, let
$\delta_{S}=w^{\prime}_{S}-w_{S}$. For $k\in[K]$, let $\bm{\mathcal{S}}_{k}$
and $\bm{\mathcal{S}}^{\prime}_{k}$ be the family of sets added to
$\bm{\mathcal{S}}$ and $\bm{\mathcal{S}}^{\prime}$, respectively, at step $k$.
First, we note that

$\displaystyle\sum_{S\in\mathcal{F}}|w_{S}x_{S}-w^{\prime}_{S}x^{\prime}_{S}|=\sum_{S\in\mathcal{F}}|w_{S}x_{S}-(w_{S}+\delta_{S})x^{\prime}_{S}|\geq\sum_{S\in\mathcal{F}}\left(|x_{S}-x^{\prime}_{S}|w_{S}-|\delta_{S}|x^{\prime}_{S}\right).$
(18)

Then, we have

$\displaystyle\mathrm{EM}_{\mathrm{w}}((\bm{\mathcal{S}},w),(\bm{\mathcal{S}}^{\prime},w^{\prime}))\leq\sum_{k\in[K]}\mathrm{EM}_{\mathrm{w}}((\bm{\mathcal{S}}_{k},w),(\bm{\mathcal{S}}^{\prime}_{k},w^{\prime}))$
$\displaystyle\leq\sum_{k\in[K]}\sum_{S\in\mathcal{F}}\left(\min\\{x_{S},x^{\prime}_{S}\\}\cdot|w_{S}-w^{\prime}_{S}|+\max\\{x_{S}-x^{\prime}_{S},0\\}\cdot
w_{S}+\max\\{x^{\prime}_{S}-x_{S},0\\}\cdot w^{\prime}_{S}\right)$
$\displaystyle=K\sum_{S\in\mathcal{F}}\Bigl{(}\min\\{x_{S},x^{\prime}_{S}\\}|\delta_{S}|+\max\\{x_{S}-x^{\prime}_{S},0\\}w_{S}+\max\\{x^{\prime}_{S}-x_{S},0\\}(w_{S}+\delta_{S})\Bigr{)}$
$\displaystyle\leq
K\sum_{S\in\mathcal{F}}\Bigl{(}\max\\{x_{S},x^{\prime}_{S}\\}|\delta_{S}|+|x_{S}-x^{\prime}_{S}|w_{S}\Bigr{)}$
$\displaystyle\leq
K\sum_{S\in\mathcal{F}}\Bigl{(}\max\\{x_{S},x^{\prime}_{S}\\}|\delta_{S}|+\bigl{(}|w_{S}x_{S}-w^{\prime}_{S}x^{\prime}_{S}|+x^{\prime}_{S}|\delta_{S}|\bigr{)}\Bigr{)}$
(by (18)) $\displaystyle\leq
K\sum_{S\in\mathcal{F}}\Bigl{(}2|\delta_{S}|+|w_{S}x_{S}-w^{\prime}_{S}x^{\prime}_{S}|\Bigr{)}$
$\displaystyle=O\left(K\|w-w^{\prime}\|_{1}+K\sum_{S\in\mathcal{F}}|w_{S}x_{S}-w^{\prime}_{S}x^{\prime}_{S}|\right).\qed$

###  5.3 Putting things together

1 Procedure  __LPBasedSetCover($U,\mathcal{F},w,\epsilon$)__

Input: A set $U$, $\mathcal{F}\subseteq 2^{U}$, a weight vector
$w\in\mathbb{R}_{\geq 0}^{\mathcal{F}}$, and $\epsilon>0$.

2 $C\leftarrow$ a large enough constant;

3 $L\leftarrow\epsilon\|w\|_{1}/(Cm\log n)$, where $m=|\mathcal{F}|$ and
$n=|U|$;

4 $\bm{\lambda}\leftarrow$ uniformly at random from $[L,2L]$;

5 $\kappa\leftarrow\epsilon/(C\log n)$;

6
$\bm{x}\leftarrow\textsc{RegularizedLP}(U,\mathcal{F},w,\bm{\lambda},\kappa)$;

7 $\bm{\mathcal{S}}\leftarrow\textsc{RoundingSC}(U,\mathcal{F},\bm{x})$;

8 return $\bm{\mathcal{S}}$.

Algorithm 6 Lipschitz continuous algorithm for the set cover problem

Our algorithm, LPBasedSetCover, is given in Algorithm 6.

###### Proof of Theorem 5.1.

We first consider the approximation ratio. By Lemma 5.2, $\bm{x}$ satisfies

$\displaystyle\sum_{S\in\mathcal{F}}w_{S}\bm{x}_{S}\leq\mathrm{OPT}+\frac{\bm{\lambda}m}{2}+\frac{\kappa\|w\|_{1}}{2}\leq\mathrm{OPT}+\frac{\epsilon\|w\|_{1}}{2Cm\log
n}\cdot m+\frac{\epsilon}{2C\log
n}\|w\|_{1}\leq\mathrm{OPT}+\frac{\epsilon\|w\|_{1}}{C\log n}.$

Then by Lemma 5.5, we have

$\mathop{\mathbf{E}}\left[\sum_{S\in\bm{\mathcal{S}}}w_{S}\right]\leq
O\left(\left(\mathrm{OPT}+\frac{\epsilon\|w\|_{1}}{C\log n}\right)\log
n\right)=O(\mathrm{OPT}\cdot\log n)+\epsilon\|w\|_{1}$

by setting a sufficiently large constant $C$.

Next, we analyze the Lipschitz continuity. Fix a weight vector
$w\in\mathbb{R}_{\geq 0}^{\mathcal{F}}$ and a set $S\in\mathcal{F}$. Let
$w^{\prime}\in\mathbb{R}_{\geq 0}^{\mathcal{F}}$ be a vector obtained from $w$
by increasing $w_{S}$ by $\delta>0$. By Lemma 1.3, it suffices to show that
the claim holds for $w$ and $w^{\prime}$. We consider the joint distribution
$\mathcal{L}$ between $\bm{\lambda}$ and $\bm{\lambda}^{\prime}$ defined as
follows: For each $\lambda$, we transport the probability mass for
$\bm{\lambda}=\lambda$ to that for $\bm{\lambda}^{\prime}=\lambda$ as far as
possible. The remaining mass is transported arbitrarily. Then, we have

$\displaystyle\Pr_{(\bm{\lambda},\bm{\lambda}^{\prime})\sim\mathcal{L}}[\bm{\lambda}\neq\bm{\lambda}]\leq
1-\Pr[\bm{\lambda}^{\prime}\in[L,2L]]\leq\frac{2\epsilon\|w^{\prime}\|_{1}/(Cm\log
n)-2\epsilon\|w\|_{1}/(Cm\log n)}{2\epsilon\|w^{\prime}\|_{1}/(Cm\log
n)-\epsilon\|w^{\prime}\|_{1}/(Cm\log n)}$
$\displaystyle=\frac{2\|w^{\prime}\|_{1}-2\|w\|_{1}}{2\|w^{\prime}\|_{1}-\|w^{\prime}\|_{1}}=\frac{2\delta}{\|w^{\prime}\|_{1}}$
(19)

Then by Lemmas 5.2 and 5.5, the Lipschitz constant is bounded by

$\displaystyle
O\left(\left(1+(1+\kappa)\sqrt{\frac{\|w\|_{1}}{\lambda\kappa}}+1\right)\log
n\right)+\frac{2}{\|w^{\prime}\|_{1}}\cdot\|w^{\prime}\|_{1}=O\left(\left(1+\sqrt{\frac{m\log^{2}n}{\epsilon^{2}}}+1\right)\log
n\right)$
$\displaystyle=O\left(\frac{\sqrt{m}\log^{2}n}{\epsilon}\right).\qed$

##  6 Feedback Vertex Set

In this section, we show a Lipschitz continuous algorithm for the minimum
feedback vertex set problem.

######  Theorem 6.1.

There exists a polynomial-time randomized algorithm for the minimum feedback
vertex set that, given a graph $G=(V,E)$ on $n$ vertices, a weight vector
$w\in\mathbb{R}_{\geq 0}$, and $\epsilon>0$, outputs a set of vertices
$\bm{S}\subseteq V$ with the following properties:

  * •

$\bm{S}$ is a feedback vertex set with probability $1-1/\mathrm{poly}(n)$,

  * •

The total cost of $\bm{S}$ satisfies
$\mathop{\mathbf{E}}[\sum_{v\in\bm{S}}w_{v}]=O(\log
n\cdot\mathrm{OPT})+\epsilon\|w\|_{1}$, and

  * •

the algorithm has a Lipschitz constant $O(\epsilon^{-1}\sqrt{n}\log^{2}n)$.

As with the set cover problem, our algorithm first solves an LP relaxation and
then round the obtained LP solution so that the whole process is Lipschitz
continuous. We use the algorithm in Section 5.1 to solve the LP relaxation.
However, because there are exponentially many constraints in the LP, the
rounding algorithm in Section 5.2 gives a polynomial approximation ratio and
Lipschitz constant, which are vacuous. To address this issue, we round the LP
solution using a technique called cycle sparsification, which is explained in
Section 6.1. The rounding algorithm is explained in Section 6.2. The overall
algorithm and its analysis are given in Section 6.3.

###  6.1 Cycle Sparsification

Let $G=(V,E)$ be a graph and $z\in\mathbb{R}_{\geq 0}^{V}$ be a weight vector.
For a cycle $C$ in $G$, let $z(C)=\sum_{v\in C}z_{v}$ denote the total weight
of vertices in $C$. Let $z,\widetilde{z}\in\mathbb{R}_{\geq 0}^{V}$ be two
weight vectors on the same vertex set. For $\epsilon>0$, we say that
$(G,\widetilde{z})$ is an _$\epsilon$ -cycle sparsifier_ of $(G,z)$ if for any
cycle $C$ in $G$, we have

$(1-\epsilon)z(C)\leq\widetilde{z}(C)\leq(1+\epsilon)z(C)$

For a vertex $v\in V$, let $g_{v}$ denote the _(weighted) girth_ of $v$, that
is, the minimum weight of a cycle passing through $v$. We say that a vector
$\ell\in\mathbb{R}_{\geq 0}^{V}$ is a _girth lower bound_ if $\ell_{v}\leq
g_{v}$ for every $v\in V$.

To construct a cycle sparsifier, we consider an independent sampling algorithm
using a girth lower bound, described in Algorithm 7. In Section 6.1.1, we show
that CycleSparsification (Algorithm 7) applied on an integer weight vector
$z\in\mathbb{Z}_{\geq 0}^{V}$ outputs a weight vector
$\widetilde{\bm{z}}\in\mathbb{R}_{\geq 0}^{V}$ that sparsifies $z$ with a high
probability. For a vector $z\in\mathbb{R}_{\geq 0}^{V}$, let $S(z)\subseteq V$
denote the set $\\{v\in V:z_{v}>0\\}$ induced by vertices with positive
weights. In Section 6.1.2, we show several properties of
$S(\widetilde{\bm{z}})$ used in subsequent analyses.

####  6.1.1 Sparsification Guarantee

The goal of this section is to prove the following sparsification guarantee
for integer-weighted graphs:

######  Lemma 6.2.

Let $G=(V,E)$ be a graph on $n$ vertices, $z\in\mathbb{Z}_{\geq 1}^{V}$ be an
integer weight vector, $\ell\in\mathbb{R}_{\geq 0}^{V}$ be a girth lower
bound, and $\epsilon>0$. Then, _CycleSparsification($G,z,\ell,\epsilon$)_
outputs a weight vector $\widetilde{\bm{z}}\in\mathbb{R}_{\geq 0}^{V}$ such
that $(G,\widetilde{\bm{z}})$ is an $\epsilon$-cycle sparsifier of $(G,z)$
with probability $1-1/\mathrm{poly}(n)$.

1 Procedure  __CycleSparsification($G,z,\ell,\epsilon$)__

Input: A graph $G=(V,E)$, an integer vector $z\in\mathbb{Z}_{\geq 1}^{V}$, a
girth lower bound $\ell\in\mathbb{R}_{\geq 0}^{V}$, and $\epsilon>0$.

2 $t\leftarrow O(\epsilon^{-2}\log n)$;

3 for  _each $v\in V$_ do

4 $p_{v}\leftarrow\min\\{t/\ell_{v},1\\}$;

5 $\widetilde{\bm{z}}_{v}\leftarrow\mathcal{B}(z_{v},p_{v})/p_{v}$, where
$\mathcal{B}(n,p)$ denotes the binomial distribution with parameters
$n\in\mathbb{Z}_{\geq 1}$ and $p\in[0,1]$.

6 return $\widetilde{\bm{z}}$.

Algorithm 7 Cycle sparsification for integer-weighted graphs

We prove Lemma 6.2 by following the analysis of the cut sparsification
algorithm developed by Fung and Harvey (Theorem 1.15 of [6]). We briefly
explain their argument and then discuss modifications we need to prove Lemma
6.2.

Let $G=(V,E)$ be a graph and $z\in\mathbb{R}_{\geq 0}^{E}$ be a weight vector.
For a vertex set $S\subseteq V$, let $\delta(S)$ denote the set of edges
connecting a vertex in $S$ to $V\setminus S$. For an edge set $F\subseteq E$,
let $z(F)=\sum_{e\in F}z_{e}$ denote the total weight of edges in $F$. For two
edge weights $z,\widetilde{z}\in\mathbb{R}_{\geq 0}^{E}$ and $\epsilon>0$, we
say that $(G,\widetilde{z})$ is an _$\epsilon$ -cut sparsifier_ of $(G,z)$ if
for any vertex set $S\subseteq V$, we have

$(1-\epsilon)z(\delta(S))\leq\widetilde{z}(\delta(S))\leq(1+\epsilon)z(\delta(S)).$

For an edge $e=(s,t)\in E$, let $k_{e}$ denote the _(weighted) edge
connectivity_ of the end-points of $e$, that is, the minimum weight of a cut
that separates $s$ and $t$. To construct a cut sparsifier, Fung et al. [6]
considered an algorithm similar to Algorithm 7, which loops over edges instead
of vertices and uses the edge connectivity $k_{e}$ instead of the girth
$g_{v}$. They showed that this algorithm generates an $\epsilon$-cut
sparsifier with a high probability.

The key technical ingredient of their analysis is the cut counting lemma,
explained below. For a vertex set $F\subseteq V$, we say that an edge set
$F^{\prime}$ is a _cut-induced subset_ of $F$ if $F^{\prime}=F\cap\delta(S)$
for some $S\subseteq V$. Then, we can bound the number of small cut-induced
subsets as follows.

######  Lemma 6.3 (Theorem 1.6 of [6]).

Let $G=(V,E)$ be a graph on $n$ vertices, $z\in\mathbb{R}_{\geq 0}^{E}$ be a
weight vector, and $F\subseteq E$ be an edge set. Suppose that $k_{e}\geq K$
for every $e\in F$. Then, for every real $\alpha\geq 1$, we have

$|\\{\delta(S)\cap F:S\subseteq V\wedge w(\delta(S))\leq\alpha
K\\}|<n^{2\alpha}.$

To prove Lemma 6.2, we need a counterpart of Lemma 6.3 for cycles. For a graph
$G$, let $\mathcal{C}(G)$ denote the set of simple cycles in $G$. For a vertex
set $S\subseteq V$, we say that a vertex set $T$ is a _cycle-induced subset_
of $S$ if $T=S\cap C$ for some $C\in\mathcal{C}(G)$. We have the following:

######  Lemma 6.4.

Let $G=(V,E)$ be a graph on $m$ edges, $z\in\mathbb{R}_{\geq 0}^{V}$ be a
weight vector, and $S\subseteq V$ be an arbitrary set. Suppose that $g_{v}\geq
g$ for every $v\in S$. For any $\alpha\geq 1$, we have

$|\\{C\cap S:C\in\mathcal{C}(G)\wedge z(C)\leq\alpha
g\\}|<(2m)^{2\alpha+1/2}.$

(A slight variation of) this theorem for the case of $S=V$ was proved in [14].
Because the proof of Lemma 6.4 is quite similar, we defer it to Appendix B.

Once we obtained Lemma 6.4, we can easily prove Lemma 6.2 by following the
proof of Fung et al. [6].

####  6.1.2 Properties of the Induced Set

In this section, we show several properties of the set induced by a cycle-
sparsifying weight vector.

######  Lemma 6.5.

Let $G=(V,E)$ be a graph, $z\in\mathbb{Z}_{\geq 1}^{V}$ be an integer weight
vector, $\ell\in\mathbb{R}_{\geq 0}^{V}$ be a girth lower bound, and
$\epsilon>0$. Let
$\widetilde{\bm{z}}=\textsc{CycleSparsification}(G,z,\ell,\epsilon)$. Then for
every $v\in V$, we have

$\Pr[v\in S(\widetilde{\bm{z}})]=O\left(\frac{z_{v}\log
n}{\epsilon^{2}\ell_{v}}\right).$

###### Proof.

Let $q_{v}$ be the probability that $v\in S(\widetilde{\bm{z}})$. Because
$z_{v}\geq 1$, we have $q_{v}=1-(1-p_{v})^{z_{v}}\leq p_{v}z_{v}$, and the
claim holds. ∎

Next, we show a Lipschitz property of CycleSparsification.

######  Lemma 6.6.

Let $G=(V,E)$ be a graph, $z,z^{\prime}\in\mathbb{Z}_{\geq 1}^{E}$ be integer
weight vectors, $\ell\in\mathbb{R}_{\geq 0}^{V}$ be a girth lower bound (with
respect to $z$ and $z^{\prime}$), and $\epsilon>0$. Let
$\widetilde{\bm{z}}=\textsc{CycleSparsification}(G,z,\ell,\epsilon)$ and
$\widetilde{\bm{z}}^{\prime}=\textsc{CycleSparsification}(G^{\prime},z^{\prime},\ell,\epsilon)$.
Then for every $v\in V$, we have

$\Bigl{|}\Pr[v\in S(\widetilde{\bm{z}})]-\Pr[v\in
S(\widetilde{\bm{z}}^{\prime})]\Bigr{|}=O\left(\frac{|z_{v}-z^{\prime}_{v}|\log
n}{\epsilon^{2}\ell_{v}}\right).$

###### Proof.

Let $q_{v}$ be the probability that $v\in S(\widetilde{\bm{z}})$, and
$\delta_{v}=z^{\prime}_{v}-z_{v}$. When $\delta_{v}\geq 0$, we have

$\displaystyle|q_{v}-q^{\prime}_{v}|=q_{v}-q^{\prime}_{v}=q_{v}\left(1-(1-p_{v})^{\delta_{v}}\right)\leq
q_{v}p_{v}\delta_{v}\leq p_{v}\delta_{v},$

where the first inequality is by $\delta_{v}\in\mathbb{R}\setminus(0,1)$. A
similar calculation shows that $|q_{v}-q^{\prime}_{v}|\leq p_{v}\delta_{v}$
when $\delta_{v}\leq 0$, and hence the claim holds. ∎

###  6.2 Rounding

In this section, we design a rounding algorithm for the feedback vertex set
problem, as given in Algorithm 8. Given a graph $G=(V,E)$ and a weight vector
$x\in\mathbb{R}_{\geq 0}^{V}$, which is supposed to be a solution to LP (23),
we first compute another weight vector $\bm{z}\in\mathbb{Z}_{\geq 1}^{V}$ by
scaling up $x$ and rounding it up to an integer. Then, we apply
CycleSparsification to $G$ and $\bm{z}$ to obtain a weight vector
$\tilde{\bm{z}}\in\mathbb{R}_{\geq 0}^{V}$. Finally, we add every $v\in V$
with $\tilde{\bm{z}}_{v}>0$ to the output set $\bm{S}$.

1 Procedure  __RoundingFVS($G,x$)__

Input: A graph $G=(V,E)$ and a weight vector $x\in[0,1]^{V}$.

2 Sample $\bm{b}$ from $[0,1]$ uniformly at random;

3 for  _each $v\in V$_ do

4 $\bm{z}_{v}\leftarrow\lceil n^{2}x_{v}+\bm{b}\rceil$.

5
$\widetilde{\bm{z}}\leftarrow\textsc{CycleSparsification}(G,\bm{z},n^{2},1/2)$;

6 $\bm{S}=\\{v\in V:\widetilde{\bm{z}}_{v}>0\\}$;

7 return $\bm{S}$.

Algorithm 8 Rounding

We first analyze the feasibility of the output and its approximation
guarantee.

######  Lemma 6.7.

Let $G=(V,E)$ be a graph on $n$ vertices and $x\in[0,1]^{V}$ be a weight
vector such that $\sum_{v\in C}x_{v}\geq 1$ for every cycle $C$ in $G$. Let
$\bm{S}=\textsc{RoundingFVS}(G,x)$. Then $\bm{S}$ is a feedback vertex set
with probability $1-1/\mathrm{poly}(n)$. Moreover, for any vertex $v\in V$, we
have

$\Pr[v\in\bm{S}]=O\left(x_{v}\log n+\frac{\log n}{n^{2}}\right).$

###### Proof.

First, we check the feasibility of the output. Let $C$ be a cycle in $G$.
Because $C$ has weight at least one in $x$, we have

$\sum_{v\in C}\bm{z}_{v}=\sum_{v\in C}\lceil
n^{2}x_{v}+\bm{b}\rceil\geq\sum_{v\in C}n^{2}x_{v}\geq n^{2}.$

Then by Lemma 6.2, $(G,\widetilde{\bm{z}})$ is an $1/2$-cycle sparsifier of
$(G,z)$ with probability $1-1/\mathrm{poly}(n)$. When this happens, every
cycle $C$ has a positive weight in $\widetilde{\bm{z}}$, and hence the set
$\bm{S}$ forms a feedback vertex set.

Next, by Lemma 6.5, we have

$\Pr[v\in\bm{S}]=O\left(\mathop{\mathbf{E}}\left[\frac{\bm{z}_{v}\log
n}{n^{2}}\right]\right)=O\left(\mathop{\mathbf{E}}\left[\frac{\lceil
n^{2}x_{v}+\bm{b}\rceil\log n}{n^{2}}\right]\right)=O\left(x_{v}\log
n+\frac{\log n}{n^{2}}\right).\qed$

Next, we consider Lipschitz continuity of RoundingFVS.

######  Lemma 6.8.

Let $G=(V,E)$ be a graph and $x,x^{\prime}\in[0,1]^{V}$ be weight vectors with
$\sum_{v\in C}x_{v}\geq 1$ and $\sum_{v\in C}x^{\prime}_{v}\geq 1$ for every
cycle $C$ in $G$. Let $\bm{S}=\textsc{RoundFVS}(G,x)$ and
$\bm{S}^{\prime}=\textsc{RoundFVS}(G,x^{\prime})$. Then for any $v\in V$, we
have

$\Bigl{|}\Pr[v\in\bm{S}]-\Pr[v\in\bm{S}^{\prime}])\Bigr{|}=O\left(\frac{|x_{v}-x^{\prime}_{v}|\log
n}{\epsilon^{2}}\right).$

###### Proof.

To bound the probability difference, we transport the probability mass for
$\bm{b}_{v}=b$ to the mass for $\bm{b}^{\prime}_{v}=b$ for $b\in[0,1]$. Then
by Lemma 6.6, we have

$\displaystyle\Bigl{|}\Pr[v\in\bm{S}]-\Pr[v\in\bm{S}^{\prime}]\Bigr{|}=\int_{0}^{1}O\left(\frac{|\lceil
n^{2}x_{v}+b\rceil-\lceil n^{2}x^{\prime}_{v}+b\rceil|\log
n}{\epsilon^{2}n^{2}}\right)\mathrm{d}b$
$\displaystyle=O\left(\frac{|n^{2}(x_{v}-x^{\prime}_{v})|\log
n}{\epsilon^{2}n^{2}}\right)=O\left(\frac{|x_{v}-x^{\prime}_{v}|\log
n}{\epsilon^{2}}\right).\qed$

###  6.3 Algorithm and Proof of Theorem 6.1

Let $\mathcal{C}$ be the set of all simple cycles in $G$. We consider the
following LP relaxation.

$\displaystyle\begin{array}[]{lll}\text{minimize}&\displaystyle\sum_{v\in
V}w_{v}x_{v}\\\ \text{subject to}&\displaystyle\sum_{v\in C}x_{v}\geq
1&\forall C\in\mathcal{C}\\\ &0\leq x_{v}\leq 1&\forall v\in V\end{array}$
(23)

This LP can be seen as the LP relaxation of a set cover instance with
exponentially many elements.

1 Procedure  __FeedbackVertexSet($G,w,\epsilon$)__

Input: A graph $G=(V,E)$, a weight vector $w\in\mathbb{R}_{\geq 0}^{V}$, and
$\epsilon>0$.

2 $C\leftarrow$ a large enough constant;

3 $L\leftarrow\epsilon\|w\|_{1}/(Cn\log n)$, where $n=|V|$;

4 $\bm{\lambda}\leftarrow$ uniformly at random from $[L,2L]$;

5 $\kappa\leftarrow\epsilon/(C\log n)$;

6 Solve LP 23 using the algorithm of Lemma 5.2 with $\kappa$ and $\lambda$,
and let $x\in\mathbb{R}^{V}$ be the returned solution;

7 $\bm{S}\leftarrow\textsc{RoundFVS}(G,x)$;

8 return $\bm{S}$.

Algorithm 9 Feedback Vertex Set

Let $x\in\mathbb{R}_{\geq 0}^{V}$ be the LP solution obtained by using the
algorithm in Section 5.1. Then, we round $x$ to an integral solution using
RoundFVS.

###### Proof of Theorem 6.1.

We first note that $\bm{S}$ is a feasible solution with a high probability by
Lemma 6.7.

Next, we analyze the solution quality. By Lemma 5.2, we have

$\sum_{v\in
V}w_{v}x_{v}\leq\mathrm{OPT}+\frac{\epsilon\|w\|_{1}}{C^{\prime}\log n},$

where $C^{\prime}$ is a linear function of $C$. Additionally, by Lemma 6.7,
for a sufficiently large $C$, the expected total weight of $\bm{S}$ is

$\displaystyle\sum_{v\in V}w_{v}\Pr[v\in\bm{S}]=O\left(\sum_{v\in
V}w_{v}\left(x_{v}\log n+\frac{\log n}{n^{2}}\right)\right)$
$\displaystyle=\mathrm{OPT}\log
n+\frac{\epsilon\|w\|_{1}}{2}+\frac{\|w\|_{1}\log
n}{n^{2}}\leq\mathrm{OPT}\log n+\epsilon\|w\|_{1}.$

Finally, we consider Lipschitz continuity. Let
$w,w^{\prime}\in\mathbb{R}_{\geq 0}^{V}$ be two weight vectors with
$\|w-w^{\prime}\|_{1}\leq\delta$. Let $x$ and $x^{\prime}$ be LP solutions for
$G$ and $G^{\prime}$. By Lemma 5.2, we have

$\displaystyle\sum_{v\in
V}|w_{v}x_{v}-w^{\prime}_{v}x^{\prime}_{v}|=O\left(\frac{\sqrt{n}\log
n}{\epsilon}\cdot\|w-w^{\prime}\|_{1}\right).$ (24)

Let $\delta_{v}=w^{\prime}_{v}-w_{v}$. Then, we have

$\displaystyle\sum_{v\in
V}|w_{v}x_{v}-w^{\prime}_{v}x^{\prime}_{v}|=\sum_{v\in
V}|w_{v}x_{v}-(w_{v}+\delta_{v})x^{\prime}_{v}|\geq\sum_{v\in
V}\Bigl{(}|x_{v}-x^{\prime}_{v}|w_{v}-|\delta_{v}|x^{\prime}_{v}\Bigr{)}.$
(25)

Let $\mathcal{D}$ be the probability distribution over pairs of sets that
achieves
$\mathrm{EM}_{\mathrm{w}}((1[v\in\bm{S}],w),(1[v\in\bm{S}^{\prime}],w^{\prime}))$.
Then, we have

$\displaystyle\mathrm{EM}_{\mathrm{w}}((1[v\in\bm{S}],w),(1[v\in\bm{S}^{\prime}],w^{\prime}))=\mathop{\mathbf{E}}_{(S,S^{\prime})\sim\mathcal{D}}\left[\sum_{v\in
V}\Bigl{|}w_{v}1[v\in S]-w^{\prime}_{v}1[v\in S^{\prime}]\Bigr{|}\right]$
$\displaystyle=\mathop{\mathbf{E}}_{(S,S^{\prime})\sim\mathcal{D}}\left[\sum_{v\in
V}\Bigl{|}w_{v}1[v\in S]-(w_{v}+\delta_{v})1[v\in S^{\prime}]\Bigr{|}\right]$
$\displaystyle\leq\mathop{\mathbf{E}}_{(S,S^{\prime})\sim\mathcal{D}}\left[\sum_{v\in
V}w_{v}\Bigl{|}1[v\in S]-1[v\in
S^{\prime}]\Bigr{|}\right]+\mathop{\mathbf{E}}_{(S,S^{\prime})\sim\mathcal{D}}\left[\sum_{v\in
V}|\delta_{v}|\cdot 1[v\in S^{\prime}]\right]$ $\displaystyle\leq\sum_{v\in
V}O\left(w_{v}|x_{v}-x^{\prime}_{v}|\log n\right)+\|w-w^{\prime}\|_{1}$ (by
Lemma 6.8) $\displaystyle\leq\sum_{v\in
V}O\Bigl{(}(|w_{v}x_{v}-w^{\prime}_{v}x^{\prime}_{v}|+|\delta_{v}|x^{\prime}_{v})\log
n\Bigr{)}+\|w-w^{\prime}\|_{1}$ (by (25)) $\displaystyle\leq\sum_{v\in
V}O\left(|w_{v}x_{v}-w^{\prime}_{v}x^{\prime}_{v}|\cdot\log
n\right)+O\left(\|w-w^{\prime}\|_{1}\log n\right)$
$\displaystyle=O\left(\frac{\sqrt{n}\log^{2}n}{\epsilon}\cdot\|w-w^{\prime}\|_{1}\right),$
(by (24))

and the claim holds. ∎

##  7 Lipschitz Continuity under Shared Randomness

In this section, we show that the Lipschitz continuous algorithms we provided
in the previous sections can be made Lipschitz continuous under shared
randomness. We begin by reviewing the techniques by Kumabe and Yoshida [11] to
obtain such algorithms.

Let $V$ be a finite set and let Sample be a sampling process that takes two
real values $a,b\in\mathbb{R}$ and a vector $p\in[0,1]^{\mathbb{Z}_{\geq 0}}$
and outputs a real value. For $c\geq 1$, we say that Sample is $c$-_stable_
for a pair of functions $(l,r)$ with $l,r:\mathbb{R}_{\geq
0}^{V}\to\mathbb{R}$ if (i) for any $w\in\mathbb{R}_{\geq 0}^{V}$,
$\textsc{Sample}(l(w),r(w),p)$ is uniformly distributed over $[l(w),r(w)]$
when $p$ follows the uniform distribution over $[0,1]^{\mathbb{Z}_{\geq 0}}$,
and (ii) for any $w,w^{\prime}\in\mathbb{R}_{\geq 0}^{V}$, we have

$\displaystyle\mathop{\mathbf{E}}_{\bm{p}\sim\mathcal{U}\left([0,1]^{\mathbb{Z}_{\geq
0}}\right)}\left[\mathrm{TV}\left(\textsc{Sample}(l(w),r(w),\bm{p}),\textsc{Sample}(l(w^{\prime}),r(w^{\prime}),\bm{p})\right)\right]$
$\displaystyle\leq
c\cdot\mathrm{TV}\left(\mathcal{U}([l(w),r(w)]),\mathcal{U}([l(w^{\prime}),r(w^{\prime})])\right)$

holds. They gave the following lemmas.

######  Lemma 7.1 ([11]).

Let $l$ and $r$ be constant functions. Then, there is a $1$-stable sampling
process for $(l,r)$.

######  Lemma 7.2 ([11]).

Let $c>1$ and suppose $r(w)=cl(w)$ holds for all $w$. Then, there is a
$(1+c)$-stable sampling process for $(l,r)$.

Now we explain how to modify each of our algorithms to ensure Lipschitz
continuity under the shared randomness setting.

###  7.1 Algorithm 1

Algorithm 1 can be straightforwardly converted into a Lipschitz continuous
algorithm in the shared randomness setting using the process in Lemma 7.1 to
sample $\bm{z}(e)$, without loss of Lipschitz constant.

###  7.2 Algorithm 2

Algorithm 2 can also be straightforwardly converted into a Lipschitz
continuous algorithm in the shared randomness setting using the process in
Lemma 7.1 to sample $\bm{b}$, without loss of Lipschitz constant.

###  7.3 Algorithm 4

Algorithm 4 can also be converted into a Lipschitz continuous algorithm in the
shared randomness setting without loss of Lipschitz constant as follows. We
use the process in Lemma 7.1 to sample $\bm{b}$. To sample $\bm{\pi}$, we
first sample a parameter $\bm{x}$ from the uniform distribution over $[0,1]$
using the process in Lemma 7.1, and then set $\bm{\pi}=f(\bm{x})$ using a
fixed function $f:[0,1]\to\mathcal{P}_{U,s}$, where $\mathcal{P}_{U,s}$ is the
set of all permutations over the family $\\{A\in U\colon|A|\leq s\\}$, such
that $\Pr_{\bm{x}\sim\mathcal{U}([0,1])}\left[f(\bm{x})=A\right]$ is equal for
all $A\subseteq U$ with $|A|\leq s$.

###  7.4 Algorithm 6

The randomness in Algorithm 6 arises from two parts: the sampling of parameter
$\bm{\lambda}$ and RoundingSC. The sampling of $\bm{\lambda}$ can be rewritten
using the procedure from Lemma 7.2 (note that the range $[L,2L]$ is dependent
on the quantity $\|w\|_{1}$). This modification makes the right-hand side of
Equation 19 three times larger, but it does not affect the overall analysis.

RoundingSC can be regarded as a process that determines whether to include
each $S\in\mathcal{F}$ in the output. We can regard this algorithm as a
procedure to sample $S$ with some probability $q_{S}$ determined by $x_{S}$
and $K$. It can be implemented as follows: for each $S\in\mathcal{F}$, a value
$\bm{x}\in[0,1]$ is uniformly sampled. If $\bm{x}\leq q_{S}$, $x$ is included
in the solution; otherwise, it is not. This operation can be rephrased using
Lemma 7.1, without affecting the overall Lipschitz constant.

###  7.5 Algorithm 9

The randomness in Algorithm 9 arises from three parts: the sampling of
parameter $\bm{\lambda}$, the sampling of parameter $\bm{b}$ in RoundingFVS,
and CycleSparsification. As with the sampling of $\bm{\lambda}$ in Section
7.4, the sampling of $\bm{\lambda}$ can be rewritten using the procedure from
Lemma 7.2. As with the sampling of $\bm{b}$ in Section 7.2, the sampling of
$\bm{b}$ can be rewritten using the procedure from Lemma 7.1.

Let us consider the randomness of Algorithm 9. In Algorithm 9, only whether
$\widetilde{\bm{z}}_{v}>0$ for each $v\in V$ matters in the output of
CycleSparsification. By modifying CycleSparsification to reassign
$\widetilde{\bm{z}}\leftarrow 1$ for all $v\in V$ where
$\widetilde{\bm{z}}_{v}>0$, the sampling of $\widetilde{\bm{z}}_{v}$ can be
regarded as a procedure to set $\widetilde{\bm{z}}=1$ with some probability
$\bm{q}_{v}$ determined by $\bm{z}_{v}$ and $p_{v}$. It can be implemented as
follows: for each $v\in V$, a value $\bm{x}\in[0,1]$ is uniformly sampled. If
$\bm{x}\leq\bm{q}_{v}$, $\widetilde{\bm{z}}_{v}$ is set to be $1$; otherwise,
it is set to be $0$. This operation can be rephrased using Lemma 7.1, without
affecting the overall Lipschitz constant.

## References

  * [1] V. Bafna, P. Berman, and T. Fujito.  A 2-approximation algorithm for the undirected feedback vertex set problem.  SIAM Journal on Discrete Mathematics, 12(3):289–297, 1999.
  * [2] A. A. Benczúr and D. R. Karger.  Randomized approximation schemes for cuts and flows in capacitated graphs.  SIAM Journal on Computing, 44(2):290–319, 2015.
  * [3] K. Censor-Hillel, E. Haramaty, and Z. Karnin.  Optimal dynamic distributed MIS.  In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing (PODC), pages 217–226, 2016.
  * [4] V. Chvátal.  A greedy heuristic for the set-covering problem.  Mathematics of Operations Research, 4(3):233–235, 1979.
  * [5] I. Dinur and D. Steurer.  Analytical approach to parallel repetition.  In Proceedings of the 46th annual ACM Symposium on Theory of Computing (STOC), pages 624–633, 2014.
  * [6] W.-S. Fung, R. Hariharan, N. J. Harvey, and D. Panigrahi.  A general framework for graph sparsification.  SIAM Journal on Computing, 48(4):1196–1223, 2019.
  * [7] S. Hara and Y. Yoshida.  Average sensitivity of decision tree learning.  In The 11th International Conference on Learning Representations (ICLR), 2023.
  * [8] R. Impagliazzo, R. Lei, T. Pitassi, and J. Sorrell.  Reproducibility in learning.  In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pages 818–831, 2022.
  * [9] D. S. Johnson.  Approximation algorithms for combinatorial problems.  In Proceedings of the 5th Annual ACM Symposium on Theory of computing (STOC), pages 38–49, 1973.
  * [10] S. Khot and O. Regev.  Vertex cover might be hard to approximate to within $2-\varepsilon$.  Journal of Computer and System Sciences, 74(3):335–349, 2008.
  * [11] S. Kumabe and Y. Yoshida.  Lipschitz continuous algorithms for graph problems.  In Proceedings of the 64th IEEE Symposium on Foundations of Computer Science (FOCS), 2023.  to appear.
  * [12] L. Lovász.  On the ratio of optimal integral and fractional covers.  Discrete Mathematics, 13(4):383–390, 1975.
  * [13] P. Peng and Y. Yoshida.  Average sensitivity of spectral clustering.  In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (KDD), pages 1132–1140, 2020.
  * [14] A. Subramanian.  A polynomial bound on the number of light cycles in an undirected graph.  Information Processing Letters, 53(4):173–176, 1995.
  * [15] N. Varma and Y. Yoshida.  Average sensitivity of graph algorithms.  In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 684–703, 2021.
  * [16] D. P. Williamson and D. B. Shmoys.  The design of approximation algorithms.  Cambridge university press, 2011.
  * [17] Y. Yoshida and S. Ito.  Average sensitivity of Euclidean $k$-clustering.  In Advances in Neural Information Processing Systems (NeurIPS), 2022\.
  * [18] Y. Yoshida and S. Zhou.  Sensitivity analysis of the maximum matching problem.  In Innovations in Theoretical Computer Science (ITCS), pages 58:1–58:20, 2021.

##  Appendix A Naive Bound on Lipschitz Constant

In this section, we give a proof sketch of the fact that, if there exists an
$\alpha$-approximation algorithm $\mathcal{A}$ for a minimization problem on
graphs, then for any $\epsilon>0$, there exists a
$(1+\epsilon)\alpha$-approximation algorithm $\widehat{\mathcal{A}}$ with
Lipschitz constant $O(\epsilon^{-1}|V|)$.

The algorithm $\widehat{\mathcal{A}}$ works as follows. Given a graph
$G=(V,E)$ and a weight vector $w\in\mathbb{R}_{\geq 0}^{V}$, we first
construct a vector $\widehat{\bm{w}}\in\mathbb{R}_{\geq 0}^{V}$ by rounding
values of $w$ to multiples of $c=\Theta(\epsilon\cdot\mathrm{OPT}/|V|)$ (in a
randomized way so that this process has a small Lipschitz constant). Then, we
apply the algorithm $\mathcal{A}$ on the weighted graph
$(G,\widehat{\bm{w}})$. The approximation ratio is $(1+\epsilon)\alpha$ by
choosing the hidden constant in $c$ to be small enough.

Now, we analyze the Lipschitz constant of $\widehat{\mathcal{A}}$. Let
$w,w^{\prime}\in\mathbb{R}_{\geq 0}^{V}$ be weight vectors and
$\widehat{\bm{w}}$ and $\widehat{\bm{w}}^{\prime}$ be the vectors obtained by
rounding $w$ and $w^{\prime}$, respectively. By taking an appropriate coupling
$\mathcal{D}$ between $\widehat{\bm{w}}$ and $\widehat{\bm{w}}^{\prime}$, we
have
$\mathop{\mathbf{E}}_{\mathcal{D}}\left[\widehat{\bm{w}}\neq\widehat{\bm{w}}^{\prime}\right]\leq
O(\epsilon^{-1}\|w-w^{\prime}\|_{1}\cdot|V|/\mathrm{OPT})$. By bounding
$d_{\mathrm{w}}((S,w),(S,w^{\prime}))$ by the trivial bound of
$O(\mathrm{OPT})$, the Lipschitz constant is bounded by

$\displaystyle\frac{\mathrm{EM}_{\mathrm{w}}((\widehat{\mathcal{A}}(G,w),w),(\widehat{\mathcal{A}}(G,w^{\prime}),w^{\prime}))}{\|w-w^{\prime}\|_{1}}\leq\frac{\mathop{\mathbf{E}}_{\mathcal{D}}\left[\widehat{\bm{w}}\neq\widehat{\bm{w}}^{\prime}\right]\cdot
O(\mathrm{OPT})}{\|w-w^{\prime}\|_{1}}$
$\displaystyle\leq\frac{O(\epsilon^{-1}\|w-w^{\prime}\|_{1}\cdot|V|/\mathrm{OPT})\cdot
O(\mathrm{OPT})}{\|w-w^{\prime}\|_{1}}=O\left(\frac{|V|}{\epsilon}\right).$

##  Appendix B Proof of Lemma 6.4

Lemma 6.4 is an immediate corollary of the following.

######  Lemma B.1.

Let $G=(V,E)$ be a graph, $w\in\mathbb{R}_{\geq 0}^{V}$ be a weight vector,
and $S\subseteq V$ be an arbitrary set. Suppose that $g_{v}\geq g$ for every
$v\in S$. Then for an integer or a half-integer $k\geq 1$, we have

$|\\{C\cap S\mid C\in\mathcal{C}(G)\wedge w(C)\leq kg\\}|<(2m)^{2k},$

where $m=|E|$.

###### Proof.

The proof is almost identical to that of the main result of [14].

We say that a cycle $C$ is _light_ if $w(C)\leq kg$. Pretend that each edge is
a road that covers a distance equal to its weight. Imagine that a
nondeterministic robot enters the road network at a vertex in $S$ at time $0$
and then goes around a light cycle at a constant speed of one unit. More
specifically, imagine that $\sum_{v\in S}d_{v}$ robots enter the network at
time $0$, where $d_{v}$ is the degree of the vertex $v\in V$ (one robot for
each out-going edge of each vertex; thus, there are $d_{v}$ robots at each
vertex at time 0). These robots then move through the network at a speed of
one unit. Whenever a robot reaches a vertex of the graph, it splits
instantaneously into several copies, leaving the vertex in different
directions. The effect of repeated splitting is to increase the number of
robots in the network; however, distinct robots traverse distinct
trajectories. We require that (i) the trajectory of any given robot be a light
cycle and (ii) if a robot reaches a point in the trajectory of another robot
and the set of nodes in $S$ that the former robot had passed through is
different from that of the latter robot (when it was at that point); any robot
that cannot meet these conditions immediately destroys itself. A robot that
completes its cycle waits there; clearly, each robot completes its cycle by
time $kg$ and passes through a different set of nodes in $S$. It follows that
the quantity to count equals the number of robots that are alive at time $kg$.

Let $g^{-}$ denote a quantity that is infinitesimally smaller than $g$. Let
$j$ be any nonnegative integer. We prove the following claim by induction on
$j$: there are at most $(2m)^{j+1}$ robots alive at time $jg^{-}/2$. The case
$j$ = 0 is clear because $\sum_{v\in S}d_{v}\leq 2m$. We now assume that the
claim is true for $j-1$ and establish it for $j$.

The idea is to focus on any one robot alive at time $(j-1)g^{-}/2$, and to
show that at time $jg^{-}/2$ this robot has split into at most $2m$ copies.
Consider the trajectories of all the above copies during the interval
$[(j-1)g^{-}/2,jg^{-}/2]$. Once the trajectories of two copies separate and
meet again, only one survives, for otherwise, either of the following holds:
(i) we have a cycle including a vertex in $S$ with a weight less than $g$, or
(ii) one of the two copies destroys itself because the sets of nodes in $S$ in
these trajectories are the same at the meeting point. We may assume that each
robot copy is on some edge of the network at time $jg^{-}/2$. This is because
our robots traverse vertices instantly; if a robot happens to be exactly on a
vertex at time $jg^{-}/2$, we retrace its step by an infinitesimal amount. Now
observe that the structure of the trajectories forbids two copies heading the
same way on any edge of the network at time $jg^{-}/2$. It follows that there
are at most $2m$ copies, thus establishing the correctness of the inductive
step and hence the claim.

The claim implies that there are at most $(2m)^{2k}$ robots alive at time
$(2k-1)g^{-}/2$. Let us focus on any one of these robots. We claim that this
robot will not split during the interval $[(2k-1)g^{-}/2,kg^{-}]$. This is
because at time $kg^{-}$, the robot must be back at its starting vertex. Using
the same trajectory argument as before, it follows that at most one robot
survives during the interval $[(2k-1)g^{-}/2,kg^{-}]$. Therefore the total
number of successful robots alive at time $kg^{-}$ is at most $(2m)^{2k}$.
These robots remain at their respective edges until time $kg$. ∎