A Lottery Model for Center-type Problems With Outliers ∗
David G. Harris†

Thomas Pensyl‡

Aravind Srinivasan§

Khoa Trinh¶

arXiv:1710.00287v1 [] 1 Oct 2017

Abstract
In this paper, we give tight approximation algorithms for the k-center and matroid center problems with outliers. Unfairness arises naturally in this setting: certain clients could always be considered as outliers. To address this issue, we introduce a lottery model in which each client j is allowed
to submit a parameter pj ∈ [0, 1] and we look for a random solution that covers every client j with
probability at least pj . Our techniques include a randomized rounding procedure to round a point
inside a matroid intersection polytope to a basis plus at most one extra item such that all marginal
probabilities are preserved and such that a certain linear function of the variables does not decrease
in the process with probability one.

1

Introduction

The classic k-center and Knapsack Center problems are known to be approximable to within factors
of 2 and 3 respectively [7]. These results are best possible unless P=NP [7, 8]. In these problems, we
are given a metric graph G and want to find a subset S of vertices of G subject to either a cardinality
constraint or a knapsack constraint such that the maximum distance from any vertex to the nearest vertex
in S is as small as possible. We shall refer to vertices in G as clients. Vertices in S are also called centers.
It is not difficult to see that a few outliers (i.e., very distant clients) may result in a very large optimal
radius in the center-type problems. This issue was raised by Charikar et. al. [4], who proposed a robust
model in which we are given a parameter t and only need to serve t out of given n clients (i.e. n − t
outliers may be ignored in the solution). Here we consider three robust center-type problems: the Robust
k-Center (RkCenter) problem, the Robust Knapsack Center (RKnapCenter) problem, and the Robust
Matroid Center (RMatCenter) problem.
Formally, an instance I of the RkCenter problem consists of a set V of vertices, a metric distance
d on V , an integer k, and an integer t. Let n = |V | denote the number of vertices (clients). The goal is
to choose a set S ⊆ V of centers (facilities) such that (i) |S| ≤ k, (ii) there is a set of covered vertices
(clients) C ⊆ V of size at least t, and (iii) the objective function
R := max min d(i, j)
j∈C i∈S

is minimized.
In the RKnapCenter problem, each vertex i ∈ VPhas a weight wi ∈ [0, 1], and the cardinality
constraint (i) is replaced by the knapsack constraint:
i∈S wi ≤ 1. Similarly, in the RMatCenter
problem, the constraint (i) is replaced by a matroid constraint: S must be an independent set of a given
matroid M. Here we assume that we have access to the rank oracle of M.
∗

Research supported in part by NSF Awards CNS-1010789 and CCF-1422569, and by a research award from Adobe,
Inc. A preliminary version of this work appeared in the Proc. International Workshop on Approximation Algorithms for
Combinatorial Optimization Problems (APPROX), 2017.
†
Department of Computer Science, University of Maryland, College Park, MD 20742.
Email:
davidgharris29@gmail.com
‡
Department of Computer Science, University of Maryland, College Park, MD 20742. Email: tpensyl@cs.umd.edu
§
Department of Computer Science and Institute for Advanced Computer Studies, University of Maryland, College Park,
MD 20742. Email: srin@cs.umd.edu
¶
Department of Computer Science, University of Maryland, College Park, MD 20742. Email: khoa@cs.umd.edu

1

In [4], Charikar et. al. introduced a greedy algorithm for the RkCenter problem that achieves
an approximation ratio of 3. Recently, Chakrabarty et. al. [3] give a 2-approximation algorithm for
this problem. Since the k-center problem is a special case of the RkCenter problem, this ratio is best
possible unless P=NP.
The RKnapCenter problem was first studied by Chen et. al. [5], which showed that one can achieve
an approximation ratio of 3 if allowed to slightly violate the knapsack constraint by a factor of (1 + ).
It is still unknown whether there exists a true approximation algorithm for this problem. The current
inapproximability bound is still 3 due to the hardness of the Knapsack Center problem. The current best
approximation guarantee for the RMatCenter problem is 7 by Chen et. al. [5]. This problem has a
hardness of (3 − ) via a reduction from the k-supplier problem.
From a practical viewpoint, unfairness arises inevitably in the robust model: some clients might
always be considered as outliers and hence not covered within the guaranteed radius. To address this
issue, we introduce a lottery model for these problems. The idea is to randomly pick a solution from a
public list such that each client j ∈ V is guaranteed to be covered with probability at least pj , where
pj ∈ [0, 1] is the success rate requested by j. This is also motivated by the fact that different clients may
have different tolerances of getting connected to their closest facility. One possible way of determining
the pj values is to let each client j pay for the chance of being served. Note that the robust model is a
special case when pj = 0 for all j ∈ V . Similarly, when all pj ’s are equal to 1, it becomes the standard
model where all clients must be connected.
The lottery model might also be useful in the context of clustering. Recall that clustering is a
fundamental task in unsupervised machine learning. Basically, we want to partition a set of data points
to clusters in such a way that the points in the same cluster are “similar” to each other. The k-center
clustering is one of the popular approaches to this task. (See also k-means clustering [1,9] and k-median
clustering [2, 12, 15].) Naturally, the robust model can be applied to get rid of some “bad data points”
or “noise” and hence improve the overall quality of all clusters. Here over-fitting may occur when
this model misclassifies some good points as outliers. The lottery model offers the flexibility to decide
whether a point should be included in the solution via the pj values.
In this paper, we introduce new approximation algorithms for these robust center problems under
the lottery model. (Note that this model has been used recently for the Knapsack Center problems [6],
although the techniques and problems in that paper are different from ours.) We also propose improved
approximation algorithms for the RkCenter problem and the RMatCenter problem.

1.1

The Lottery Model

In this section, we formally define our lottery model for the above-mentioned problems. First, the Fair
Robust k-Center (FRkCenter) problem is formulated as follows. Besides the parameters V, d, k and t,
each vertex j ∈ V has a “target” probability pj ∈ [0, 1]. We are interested in the minimum radius R for
which there exists a distribution D on subsets of V such that a set S drawn from D satisfies the following
constraints:
Coverage constraint: |C| ≥ t with probability one, where C is the set of all clients in V that are within
radius R from some center S,
Fairness constraint: Pr[j ∈ C] ≥ pj for all j ∈ V , where C is as in the coverage constraint,
Cardinality constraint: |S| ≤ k with probability one.
Here we aim for a polynomial-time, randomized algorithm that can sample from D. Note that the
RkCenter is a special of this variant in which all pj ’s are set to be zero.
The Fair Robust Knapsack Center (FRKnapCenter) problem and Fair Robust Matroid Center
(FRMatCenter) problem are defined similarly except that we replace the cardinality constraint by a
knapsack constraint and a matroid constraint, respectively. More formally, in the FRKnapCenter problem, each vertex i has a weight wi ∈ [0, 1], and we require the total weight of centers in S to be at most
2

1 with probability one. Similarly, in the FRMatCenter problem, we are given a matroid M and we
require the solution S to be an independent set of M with probability one.

1.2

Our contributions and techniques

First of all, we give tight approximation algorithms for the RkCenter and RMatCenter problems.
Theorem 1.1. There exist a 2-approximation algorithm for the RkCenter problem 1 and a 3-approximation
algorithm for the RMatCenter problem.
Our main results for the lottery model are summarized in the following theorems.
Theorem 1.2. For any given constant  > 0 and any instance I = (V, d, k, t, p~) of the FRkCenter
problem, there is a randomized polynomial-time algorithm A which can compute a random solution S
such that
• |S| ≤ k with probability one,
• |C| ≥ (1 − )t, where C is the set of all clients within radius 2R from some center in S and R is
the optimal radius,
• Pr[j ∈ C] ≥ (1 − )pj for all j ∈ V .
Theorem 1.3. For any  > 0 and any instance I = (V, d, w, B, t, p~) of the FRKnapCenter problem,
there is a randomized polynomial-time algorithm A which can return random solution S such that
P
•
i∈S wi ≤ (1 + )B with probability one,
• |C| ≥ t, where C is the set of vertices within distance 3R of S.
• Pr[j ∈ C] ≥ pj for all j ∈ V .
Finally, the FRMatCenter can be reduced to (randomly) rounding a point in a matroid intersection
polytope. We design a randomized rounding algorithm which can output a pseudo solution, which
consists of a basis plus one extra center. By using a preprocessing step and a configuration LP, we
can satisfy the matroid constraint exactly (respectively, knapsack constraint) while slightly violating the
coverage and fairness constraints in the FRMatCenter (respectively, FRKnapCenter) problem. We
believe these techniques could be useful in other facility-location problems (e.g., the matroid median
problem [10, 14]) as well.
Theorem 1.4. For any given constant γ > 0 and any instance I = (V, d, M, t, p~) of the FRMatCenter
(respectively, FRKnapCenter) problem, there is a randomized polynomial-time algorithm A which can
return a random solution S such that
• S is a basis of M with probability one, (respectively, w(S) ≤ B with probability one)
• |C| ≥ t − γ 2 n, where C is the set of vertices within distance 3R of S.
• there exists a set T ⊆ V of size at least (1 − γ)n, which is deterministic, such that Pr[j ∈ C] ≥
pj − γ for all j ∈ T .
1

A 2-approximation algorithm has also been found independently by Chakrabarty et. al. [3], and in a private discussion
between Marek Cygan and Samir Khuller. Our algorithm here is different from the algorithm in [3].

3

1.3

Organization

The rest of this paper is organized as follows. In Section 2, we review some basic properties of matroids
and discuss a filtering algorithm which is used in later algorithms. Then we develop approximation
algorithms for the FRkCenter, FRKnapCenter, and FRMatCenter problems in the next three sections.

2
2.1

Preliminaries
Matroid polytopes

We first review
a few basic facts about matroid polytopes. For any vector z and set S, we let z(S) denote
P
the sum i∈S zi . Let M be any matroid on the ground set Ω and rM be its rank function. The matroid
base polytope of M is defined by

PM := x ∈ RΩ : x(S) ≤ rM (S) ∀S ⊆ Ω; x(Ω) = rM (Ω); xi ≥ 0 ∀i ∈ Ω .
Definition 2.1. Suppose Ax ≤ b is a valid inequality of PM . A face D of PM (corresponding to this
valid inequality) is the set D := {x ∈ PM : Ax = b} .
The following theorem gives a characterization for any face of PM (See, e.g., [11, 13]).
Theorem 2.2. Let D be any face of PM . Then it can be characterized by

D = x ∈ RΩ : x(S) = rM (S) ∀S ∈ L; xi = 0 ∀i ∈ J; x ∈ PM ,
where J ⊆ Ω and L is a chain family of sets: L1 ⊂ L2 ⊂ . . . ⊂ Lm . Moreover, it is sufficient to choose
L as any maximal chain L1 ⊂ L2 ⊂ . . . ⊂ Lm such that x(Li ) = rM (Li ) for all i = 1, 2, . . . , m.
Proposition 2.3. Let x ∈ PM be any point and I be the set of all tight constraints of PM on x. Suppose
D is the face with respect to I. Then one can compute a chain family L for D as in Theorem 2.2 in
polynomial time.
0 (S) = r (S) − x(S) for S ⊆ Ω
Proof. Recall that rM is a submodular function. Thus the function rM
M
is also submodular. It is well-known that submodular minimization can be done in polynomial time. We
0 (S) : S ⊆ Ω}. If there are multiple solutions, we
solve the following optimization problem: min {rM
let S0 be any solution of minimal size. (This can be done easily, say, by trying to drop each item from
the current solution and resolving the program.) We add S0 to our chain. Then we find some minimal
0 (S ) = 0, add S to our chain, and repeat the process.
superset S1 of S0 such that rM
1
1

Corollary 2.4. Let D be any face of PM . Then it can be characterized by

D = x ∈ RΩ : x(S) = bS ∀S ∈ O; xi = 0 ∀i ∈ J; x ∈ PM ,
where J ⊆ Ω and O is a family of pairwise disjoint sets: O1 , O2 , . . . , Om , and bO1 , . . . , bOm are some
integer constants.
Proof. By Theorem 2.2, we have

D = x ∈ RΩ : x(S) = rM (S) ∀S ∈ L; xi = 0 ∀i ∈ J; x ∈ PM ,
where J ⊆ Ω and L is the chain: L1 ⊂ L2 ⊂ . . . ⊂ Lm . Now let us define O1 := L1 , O2 := L2 \
L1 , O3 := L3 \L2 , . . . , Om := Lm \Lm−1 , and bO1 := rM (L1 ), bO2 := rM (L2 )−rM (L1 ), . . . , bOm :=
rM (Lm ) − rM (Lm−1 ). It is not difficult to verify that

D = x ∈ RΩ : x(S) = bS ∀S ∈ O; xi = 0 ∀i ∈ J; x ∈ PM .

4

2.2

Filtering algorithm

All algorithms in this paper are based on rounding an LP solution. In general, for each vertex i ∈ V , we
have a variable yi ∈ [0, 1] which represents the probability that we want to pick i in our solution. (In
the standard model, yi is the “extent” that i is opened.) In addition, for each pair of i, j ∈ V , we have a
variable xij ∈ [0, 1] which represents the probability that j is connected to i.
Note that in all center-type problems, the optimal radius R is always the distance between two
vertices. Therefore, we can always “guess” the value of R in O(log n) by a binary search on the sorted
entries of the matrix d. WLOG, we may assume that we know the correct value of R. For any j ∈ V ,
we define
P Bj := {i ∈ V : d(i, j) ≤ R} and we let Fj := {i ∈ V : d(i, j) ≤ R ∧ xij > 0} and
sj :=
i∈Bj xij . We shall refer to Fj as a cluster with cluster center j. Depending on a specific
problem, we may have different constraints on xij ’s and yi ’s. In general, the following constraints are
valid in most of the problems here:
XX
xij ≥ t,
(1)
j∈V i∈Bj

X
i∈Bj

xij ≤ 1,
xij ≤ yi ,

yi , xij ≥ 0,
For the fair variants, we may also require that
X
xij ≥ pj ,
i∈Bj

∀j ∈ V,
∀i, j ∈ V,

(2)
(3)

∀i, j ∈ V.

(4)

∀j ∈ V.

(5)

Constraint (1) says that at least t vertices should be covered. Constraint (2) ensures that each vertex
is only connected to at most one center. Constraint (3) means vertex j can only connect to center i if
it is open. Constraint (5) says that the total probability of j being connected should be at least pj . By
constraints (2) and (3), we have y(Fj ) ≤ 1.
The first step of all algorithms in this paper is to use the following filtering algorithm to obtain a
maximal collection of disjoint clusters. The algorithm will return the set V 0 of cluster centers of the
chosen clusters. In the process, we also keep track of the number cj of other clusters removed by Fj for
each j ∈ V 0 .
Algorithm 1 RF ILTERING (x, y)
1:
2:
3:
4:
5:
6:
7:

3

V0 ←∅
for each unmarked cluster Fj in decreasing order of sj do
V 0 ← V 0 ∪ {j}
Set all unmarked clusters Fk (including Fj itself) s.t. Fk ∩ Fj 6= ∅ as marked.
Let cj be the number of marked clusters in this step.
~c ← (cj : j ∈ V 0 )
return (V 0 , ~c)

The k-center problems with outliers

In this section, we first give a simple 2-approximation algorithm for the RkCenter problem. Then, we
give an approximation algorithm for the FRkCenter problem, proving Theorem 1.2.

5

3.1

The robust k-center problem

Suppose I = (V, d, k, t) is an instance the RkCenter problem with the optimal radius R. Consider the
polytope PRkCenter containing points (x, y) satisfying constraints (1)–(4), and the cardinality constraint:
X
yi ≤ k.
(6)
i∈V

Since R is the optimal radius, it is not difficult to check that PRkCenter 6= ∅. Let us pick any fractional
solution (x, y) ∈ PRkCenter . The next step is to round (x, y) into an integral solution using the following
simple algorithm.
Algorithm 2 R K C ENTER ROUND (x, y)
(V 0 , ~c) ← RF ILTERING (x, y) .
2: S ← the top k vertices i ∈ V 0 with highest value of ci .
3: return S
1:

Analysis. By construction, the algorithm returns a set S of k open centers. Note that, for
Peach i ∈ S,
ci is the number of distinct clients within radius 2R from i. Thus, it suffices to show that i∈S ci ≥ t.
By inequality (2), we have sj ≤ 1 for all j ∈ V 0 . Thus,
X
X
ci si ≥
si ≥ t,
i∈V 0

i∈V

where the first inequality is due to the greedy choice of vertices in V 0 and the second inequality follows
from (1). Now recall that the clusters whose centers in V 0 are pairwise disjoint. By constraint (6),
X
X
X
si ≤
y(Fi ) ≤
yi ≤ k.
i∈V 0

It follows by the choice of S that

3.2

P

i∈S ci

i∈V 0

i∈V

≥ t. This concludes the first part of Theorem 1.1.

The fair robust k-center problem

Assume I = (V, d, k, t, p~) be an instance of the FRkCenter problem
 with the optimal radius R. Fix
any  > 0. If k ≤ 2/, then we can generate all possible O n1/ solutions and then solve an LP to
obtain the corresponding marginal probabilities. So the problem can be solved easily in this case. We
will assume that k ≥ 2/ for the rest of this section. Consider the polytope PFRkCenter containing points
(x, y) satisfying constraints (1)–(4), the fairness constraint (5), and the cardinality constraint (6). We
now show that PFRkCenter is actually a valid relaxation polytope.
Proposition 3.1. The polytope PFRkCenter is non-empty.
Proof. It suffices to point out a solution (x, y) ∈ PFRkCenter . Since R is the optimal radius, there exists
a distribution D satisfying the coverage, fairness, and cardinality constraints. Suppose S is sampled
from D and C is the set of all clients in V that are within radius R from some
P center S. We now set
yi := Pr[i ∈ S] for all i ∈ V . Since |S| ≤ k with probability one, we have i∈V yi = E[|S|] ≤ k, and
hence constraint (6) is valid.
We construct the assignment variable x as follows. For each j ∈ V , set zj := 0. Then for each
i ∈ Bj , set xij := min{yi , 1 − zj } and update zj := zj + xij . It is not hard to see that inequalities (2)
and (3) hold by this construction. Now let us fix any j ∈ V . By fairness guarantee of D and the union
bound, we have
X
pj ≤ Pr[j ∈ C] ≤
yi .
i∈Bj

6

Thus, by construction of x, we have
X
i∈Bj

xij ≥ Pr[j ∈ C] ≥ pj ,

and hence inequality (5) is satisfied. Finally, we have
X
XX
E[|C|] =
Pr[j ∈ C] ≤
xij .
j∈V

j∈V i∈Bj

Since |C| ≥ t with probability one, E[|C|] ≥ t, implying that inequality (1) holds.
Our algorithm is as follows.
Algorithm 3 FR K C ENTER ROUND (, x, y)
(V 0 , ~c) ← RF ILTERING (x, y) .
2: Form vector y 0 by setting
1:

yj0 ← (1 − )

3:
4:
5:

6:
7:

X

xij

i∈Fj

for each j ∈ V 0 .
while at least three entries of y 0 are in the range (0, 1) do
0
Let δ ∈ RV , δ 6= 0 be such that δi = 0 ∀i ∈ V 0 : yi0 ∈ {0, 1}, δ(V 0 ) = 0, and ~c · δ = 0.
Choose scaling factors a, b > 0 such that
0
0
• y 0 + aδ ∈ [0, 1]V and y 0 − bδ ∈ [0, 1]V
• there is at least one new entry of y 0 + aδ which is equal to zero or one
• there is at least one new entry of y 0 − bδ which is equal to zero or one
b
With probability a+b
, update y 0 ← y 0 + aδ; else, update y 0 ← y 0 − bδ.
return S = {i ∈ V : yi0 > 0}.

Analysis. First, note that one can find such a vector δ in line 4 as the system of δ(V 0 ) = 0 and
~c · δ = 0 consists of two constraints and at least three variables (and hence is underdetermined.) Thus,
the algorithm rounds at least one fractional variable per iteration, and terminates after O(n) rounds. Let
S denote the (random) solution returned by FR K C ENTER ROUND and C be the set of all clients within
radius 3R from some center in S. Theorem 1.2 can be verified by the following propositions.
Proposition 3.2. |S| ≤ k with probability one.
Proof. By definition of y 0 at line 2 of FR K C ENTER ROUND, we have
X X
X X
y 0 (V 0 ) = (1 − )
xij ≤ (1 − )
yi ≤ (1 − )k ≤ k − 2,
j∈V 0 i∈Fj

j∈V 0 i∈Fj

since k ≥ 2/. Note that the sum y 0 (V 0 ) is never changed in the while loop (lines 4 . . . 7) because
δ(V 0 ) = 0. Then the final vector y 0 contains at most two fractional values at the end of the while loop.
By rounding these two values to one, the size of S is indeed at most k.
Proposition 3.3. |C| ≥ (1 − )t with probability one.
Proof. At the beginning of the while loop, we have
X
X
X
cj sj ≥ (1 − )
sj ≥ (1 − )t.
~c · y 0 =
cj yj0 (Fj ) = (1 − )
j∈V 0

j∈V 0

7

j∈V

Again, the quantity ~c · y 0 is unchanged in the while loop because ~c · δ = 0 implies that ~c · (y 0 + aδ) = ~c · y 0
0
and ~c · (y 0 − bδ) = ~c · y 0 in each iteration. Note that if y 0 ∈ {0, 1}V , then ~c · y 0 is the number of clients
within radius 2R from some center i such that yi0 = 1. Basically, we round the two remaining fractional
values of y 0 to one in line 8; and hence, the dot product should be still at least (1 − )t.
Proposition 3.4. Pr[j ∈ C] ≥ (1 − )pj for all j ∈ V .
Proof. Fix any j ∈ V . The algorithm RF ILTERING guarantees that there exists k ∈ V 0 such that
Fj ∩ Fk 6= ∅ and sk ≥ sj . Now we claim that E[yk0 ] = yk0 . This is because the expected value of yk0 does
not change after any single iteration:
E[yk0 ] = (yk0 + aδ)

b
a
+ (yk0 − bδ)
= yk0 .
a+b
a+b

Then
Pr[k ∈ S] = Pr[yk0 > 0] ≥ Pr[yk0 = 1] = E[yk0 ] = yk0 = (1 − )sk .
Therefore,
Pr[j ∈ C] ≥ Pr[k ∈ S] ≥ (1 − )sk ≥ (1 − )sj ≥ (1 − )pj ,
by constraint (5).

4

The Knapsack Center problems with outliers

We study the RKnapCenter and FRKnapCenter problems in this section. Recall that in these problems, each vertex has a weight and we want to make sure that the total weight of the chosen centers does
not exceed 1. We first give a 3-approximation algorithm for the RKnapCenter problem that slightly
violates the knapsack constraint. Although this is not better than the known result by [5], both our algorithm and analysis here are more natural and simpler. It serves as a starting point for the next results.
For the FRKnapCenter, we show that it is possible to satisfy the knapsack constraint exactly with small
violations in the coverage and fairness constraints.

4.1

The robust knapsack center problem

Suppose I = (V, d, w, t) is an instance the RKnapCenter problem with the optimal radius R. Consider the polytope PRKnapCenter containing points (x, y) satisfying constraints (1)–(4), and the knapsack
constraint:
X
wi yi ≤ 1.
(7)
i∈V

Again, it is not difficult to check that PRKnapCenter 6= ∅. Let us pick any fractional solution (x, y) ∈
PRKnapCenter . Our pseudo-approximation algorithm to round (x, y) is as follows.
Algorithm 4 RK NAP C ENTER ROUND (x, y)
(V 0 , ~c) ← RF ILTERING (x, y) .
2: For each i ∈ V 0 , let vi = arg minj∈Fi {wj } be the vertex with smallest weight in Fi
n
o
P
P
0
3: Let P 0 := z ∈ [0, 1]V :
c
z
≥
t
∧
w
z
≤
1
0
0
i
i
v
i
i
i∈V
i∈V
1:

Compute an extreme point Y of P 0
5: return S = {vi : i ∈ V, Yi > 0}
4:

8

Analysis. We first claim that P 0 6= ∅ which implies that the extreme point Y of P 0 (in line 4) does exist.
To see this, we claim that the vector s lies in P 0 . For, we have:
X
X
ci si ≥
si ≥ t.
i∈V 0

i∈V

Also,
X
i∈V

0

wvi si =

X
i∈V

0

wvi

X
j∈Fi

xji ≤

X
i∈V

0

wv i

X
j∈Fi

yj ≤

XX
0

i∈V j∈Fi

wj yj ≤

X
i∈V

wi yi ≤ 1.

All the inequalities follow from LP constraints and definitions of si , ci , and vi .
Proposition 4.1. The solution S returned by RK NAP C ENTER ROUND satisfies w(S) ≤ 1 + 2wmax and
|C| ≥ t, where C is the set of vertices within distance 3R of S and wmax is the maximum weight of any
vertex in V .
Proof. First, observe that any extreme point of P 0 has at most two fractional values. (In the worst case,
0
an
i = 1,
P extreme point z is
Pfully determined by |V | − 2 tight constraints of the form zi = 0 or∗ z∗∗
c
z
=
t,
and
w
z
=
1.)
By
construction
of
S,
there
are
at
most
two
vertices
i
,
i
such
i∈V 0 i i
i∈V 0 vi i
that Yi∗ , Yi∗∗ are fractional. Thus,
X
wvi Yi + wi∗ + wi∗∗ ≤ 1 + 2wmax .
w(S) =
i∈S\{i∗ ,i∗∗ }

Recall that each i ∈ V 0 has ci clients within distance 2R (and each client is counted only one time).
By the triangle inequality, these clients are within distance 3R from vi . Thus, S covers at least
X
X
ci Yi + ci∗ + ci∗∗ ≥
ci Yi ≥ t,
i∈S\{i∗ ,i∗∗ }

i∈S

clients within radius 3R.

4.2

The fair robust knapsack center problem

In this section, we will first consider a simple algorithm that only violates the knapsack constraint by
two times the maximum weight of any vertex. Then using a configuration polytope to “condition” on
the set of “big” vertices, we show that it is possible to either violate the budget by (1 + ) or to preserve
the knapsack constraint while slightly violating the coverage and fairness constraints.
4.2.1

Basic algorithm

Suppose I = (V, d, w, t, p~) is an instance the FRKnapCenter problem with the optimal radius R.
Consider the polytope PFRKnapCenter containing points (x, y) satisfying constraints (1)–(4), the fairness
constraint (5), and the knapsack constraint (7). The proof that PFRKnapCenter 6= ∅ is very similar to that
of Proposition 3.1 and is omitted here.
The following algorithm is a randomized version of RK NAP C ENTER ROUND.
Note that P 0 6= ∅, and so the decomposition at line 4 is well-defined (see the analysis in Section 4.1).
Proposition 4.2. The algorithm BASIC FRK NAP C ENTER ROUND returns a random solution S such that
w(S) ≤ 1 + 2wmax , |C| ≥ t, and Pr[j ∈ C] ≥ pj for all j ∈ V , where C is the set of vertices within
distance 3R of S and wmax is the maximum weight of any vertex in V .
Proof. By similar arguments to the proof of Proposition 4.1, we have w(S) ≤ 1 + 2wmax and |C| ≥ t.
To obtain the fairness guarantee, observe that vi ∈ S with probability at least zi = si . For any j ∈ V ,
let k ∈ V 0 be the vertex that removed j in the filtering step. We have
Pr[j ∈ C] ≥ Pr[vk ∈ S] ≥ sk ≥ sj ≥ pj ,
where the penultimate inequality is due to our greedy choice of k in RF ILTERING.
9

Algorithm 5 BASIC FRK NAP C ENTER ROUND (x, y)
(V 0 , ~c) ← RF ILTERING (x, y) .
2: For each i ∈ V 0 let vi := arg minj∈Fi {wj } be the vertex with smallest weight in Fi
n
o
P
P
0
3: Let P 0 := z ∈ [0, 1]V :
c
z
≥
t
∧
w
z
≤
1
i∈V 0 i i
i∈V 0 vi i
1:

4:

Decompose the vector s as a convex combination of extreme points z (1) , . . . , z (n+1) of P 0 :
s = p1 z (1) + . . . + pn+1 z (n+1) ,

P
where ` p` = 1 and p` ≥ 0 for all ` ∈ [n + 1].
5: Randomly choose Y ← z (`) with probability p` .
6: return S = {vi : i ∈ V, Yi > 0}
4.2.2

An algorithm slightly violating the budget constraint

Fix a small parameter  > 0. A vertex i is said to be big iff wi > . Let U denote the collection of all
possible sets of big vertices. Since a solution can contain at most 1/ big vertices, we have |U| ≤ nO(1/) .
Consider the configuration polytope Pconfig1 containing points (x, y, q) with the following constraints:
P
qU = 1



PU ∈U U


∀j ∈ V, U ∈ U
 i∈Bj xij ≤ qU


P
P

U

∀j ∈ V

 U ∈U i∈Bj xij ≥ pj


U
U


≤ yi
∀i, j ∈ V, U ∈ U
x
Pij
U
w y ≤ qU B
∀U ∈ U
Pi∈V Pi i

U


x ≥ qU t

 j∈V i∈Bj ij


U

yi = 1
∀U ∈ U, i ∈ U




U

yi = 0
∀U ∈ U, i ∈ V \ U, wi > 1/


 U U
xij , yi , qU ≥ 0
∀i, j ∈ V, U ∈ U
We first claim that Pconfig1 is a valid relaxation polytope for the problem.
Proposition 4.3. The polytope Pconfig1 is non-empty.
Proof. Fix any optimal distribution D. Suppose S is sampled from D. For any U ∈ U, let
P E(U ) be the
event that U ⊆ S and S \U contains no big vertex, and let qU = Pr[E(U )]. It is clear that U ∈U qU = 1.
U
Let xU
ij = Pr[E(U ) ∧ j is connected to i] and let yi = Pr[E(U ) ∧ i ∈ S].
Now observe that
X
X
qU = Pr[E(U )] =
Pr[j is connected to i ∧ E(U )] =
xU
ij .
i∈Bj

i∈Bj

Similarly,
pj ≤ Pr[j is connected] =
=

X X
U ∈U i∈Bj

X
U ∈U

Pr[j is connected ∧ E(U )]

Pr[j is connected to i ∧ E(U )] =

X X

xU
ij .

U ∈U i∈Bj

U
Note that xU
ij /qU and yi /qU are the probabilities that j is connected to i and i ∈ S conditioned on
E(U ), respectively. Since the number of connected clients is at least t with probability one, we have
XX
XX
t ≥ E[# connected clients|E(U )] =
Pr[j is connected to i|E(U )] =
xU
ij /qU .
j∈V i∈Bj

j∈V i∈Bj

10

Similarly, w(S) ≤ 1 with probability one and so
X

1 ≥ E[w(S)|U ] =

wi (yiU /qU ).

i∈V

The other constraints can be verified easily. We conclude that (x, y, q) ∈ Pconfig1 .
We use the following Algorithm 6 to round any (x, y, q) ∈ Pconfig1 :
Algorithm 6 FRK NAP C ENTER ROUND 1 (x, y, q)
Randomly pick a set U ∈ U with probability qU
0
U
Let x0ij ← xU
ij /qU and yi ← min{yi /qU , 1}
3: return S = BASIC RFK NAP C ENTER ROUND (x0 , y 0 )

1:

2:

We are now ready to prove Theorem 1.3.
Proof of Theorem 1.3. We will show that solution S returned by FRK NAP C ENTER ROUND 1 satisfies
the requirements of Theorem 1.3. Let E(U ) denote the event that it select U ∈ U. Note that (x0 , y 0 )
satisfies the following constraints:
XX
x0ij ≥ t,
j∈V i∈Bj

X
i∈Bj

X

x0ij ≤ 1,
x0ij =

i∈Bj

X
i∈V

∀j ∈ V,

X

xij /qU ,

i∈Bj

x0ij ≤ yi0 ,

wi yi0

∀j ∈ V,

∀i, j ∈ V,

≤ 1.

Moreover, yi0 = 1 for all i ∈ U , and yi0 = 0 for all big vertices i ∈ V \ U . Thus, the two extra
fractional vertices opened by BASIC FRK NAP C ENTER ROUND have weight at most . By Proposition
4.2, we have w(S) ≤ 1 + 2. Moreover, conditioned on U , we have
X
X
x0ij =
xij /qU .
Pr[j ∈ C|E(U )] ≥
i∈Bj

i∈Bj

Thus, by definition of Pconfig1 and our construction of S, we get
Pr[j ∈ C] =

4.2.3

X
U ∈U

Pr[j ∈ C|E(U )] Pr[E(U )] ≥

X X
U ∈U i∈Bj

xij ≥ pj .

An algorithm that satisfies the knapsack constraint exactly

Let  > 0 a small parameter to be determined. Let U denote the collection of all possible vertex sets of
at most d1/e; note that |U| ≤ nO(1/) . Suppose R is the optimal radius to our instance. Given a set
U ∈ U, we say that vertex j ∈ V is blue if d(j, U ) ≤ 3R; otherwise, vertex i is red. For any i ∈ V , let
RBall(i, U, R) denote the set of red vertices within radius 3R from i:
RBall(i, U, R) := {j ∈ V : d(i, j) ≤ 3R ∧ d(j, U ) > 3R}
11

Consider the configuration polytope Pconfig2 containing points (x, y, q) with the following constraints:
P
qU = 1



PU ∈U U


∀j ∈ V, U ∈ U

i∈B xij ≤ qU


P jP

U

∀j ∈ V

 U ∈U i∈Bj xij ≥ pj


U
U


≤ yi
∀i, j ∈ V, U ∈ U
x
Pij
U
wi y ≤ qU B
∀U ∈ U

Pi∈V P i

U



j∈V
i∈Bj xij ≥ qU t



U

yi = 1
∀U ∈ U, i ∈ U




U

yi = 0
∀U ∈ U, i ∈ V \ U, |RBall(i, U, R)| ≥ n


 U U
xij , yi , qU ≥ 0
∀i, j ∈ V, U ∈ U
We first claim that Pconfig2 is a valid relaxation polytope for the problem.
Proposition 4.4. The polytope Pconfig2 is non-empty.
Proof. Suppose S is a solution drawn from the optimal distribution D. Consider the following randomized procedure to generate a random subset US of S:
Algorithm 7 Generate random US :
Set US ← ∅.
while there exists ∈ S such that |RBall(i, US , R)| ≥ n do
3:
Select the vertex i of smallest index such that |RBall(i, US , R)| ≥ n
4:
Update US ← US ∪ {i}
5:
Mark all vertices within radius 3R of i as blue
1:

2:

Note that for all i ∈ S \ US , we have |RBall(i, US , R)| < n by the condition of the while-loop.
Moreover, we claim that |US | ≤ d1/e, so that US ∈ U. For, suppose |US | > 1/; for each i ∈ US ,
there are at least n red vertices turned into blue by i in the procedure. This implies that there are more
than (1/) × n = n vertices, which is a contradiction.
Now for any U ∈ U, we set qU := Pr[US = U ]. Let xU
= Pr[US = U ∧ j is connected to i], and
ij
P
finally let yiU = Pr[US = U ∧ i ∈ S]. Then it is clear that U ∈U qU = 1. Using similar arguments as
in the proof of Proposition 4.3, we have the following inequalities:
X
xU
ij ≤ qU , ∀j ∈ V, U ∈ U
i∈Bj

X X
U ∈U i∈Bj

X
i∈V

xU
ij ≥ pj ,

wi yiU ≤ qU ,

XX
j∈V i∈Bj

∀j ∈ V
∀U ∈ U

xU
ij ≥ qU t.

As mentioned before, if |RBall(i, US , R)| ≥ n then i ∈
/ S. Therefore,
yiU = Pr[US = U ∧ i ∈ S] = 0,

∀U ∈ U, i ∈ V \ U, |RBall(i, U, R)| ≥ n.

The other constraints can be verified easily. We conclude that (x, y, q) ∈ Pconfig2 .

12

Algorithm 8 FRK NAP C ENTER ROUND 2 (x, y, q)
1:
2:
3:
4:
5:

Randomly pick a set U ∈ U with probability qU
0
U
Let x0ij ← xU
ij /qU and yi ← min{yi /qU , 1}
0
S ← BASIC RFK NAP C ENTER ROUND (x0 , y 0 )
Let i1 , i2 be vertices in S 0 \ U having largest weights.
return S = S 0 \ {i1 , i2 }
Next, let us pick any (x, y, q) ∈ Pconfig2 and use the following algorithm to round it.
2

Analysis. Let us fix any γ > 0 and set  := γ2 . Also, let E(U ) denote the event that U ∈ U is picked in
the algorithm. Again, observe that (x0 , y 0 ) satisfies the following inequalities:
XX
j∈V i∈Bj

X
i∈Bj

X

x0ij ≥ t,
x0ij ≤ 1,
x0ij =

i∈Bj

X
i∈V

∀j ∈ V,

X

xij /qU ,

i∈Bj

x0ij ≤ yi0 ,

wi yi0

∀j ∈ V,

∀i, j ∈ V,

≤ 1.

Recall that the algorithm BASIC FRK NAP C ENTER ROUND will return a solution S 0 consisting of a
set S 00 with w(S 00 ) ≤ 1 plus (at most) two extra “fractional” centers i∗ and i∗∗ . Since yi0∗∗ , yi0∗ are
fractional, we have that i∗ , i∗∗ ∈
/ U . Thus, by removing the two centers having highest weights in
S 0 \ U , we ensure that w(S) ≤ 1 with probability one.
Now we shall prove the coverage guarantee. By Proposition 4.2, S 0 covers at least t vertices within
radius 3R. If a vertex is blue, it can always be connected to some center in U and so it is not affected by
the removal of i1 , i2 . Because each of i1 and i2 can cover at most n other red vertices, we have
|C| ≥ t − 2n = 1 − γ 2 n.

For any j ∈ V , let Xj be the indicator random variable for the event that d(j, S 0 ) ≤ 3R but
d(j,
P S \ {i1 , i2 }) > 3R. We say that j is a bad vertex iff E[Xj ] ≥ γ, other, vertex j is good. Note that
j∈V Xj ≤ 2n with probability one. Thus, there can be at most 2n/γ bad vertices. Letting T denote
the set of good vertices, we have
|T | ≥ n − 2n/γ = (1 − γ)n.

By Proposition 4.2, Pr[j is covered by S 0 ] ≥ pj . For any j ∈ T , we have
Pr[j ∈ C] = Pr[j is covered by S 0 ∧ Xj = 0]

= Pr[j is covered by S 0 ] − Pr[j is covered by S 0 ∧ Xj = 1]

≥ Pr[j is covered by S 0 ] − Pr[Xj = 1] ≥ pj − γ.

This concludes the first part of Theorem 1.4 for the FRKnapCenter problem.

5

The Matroid Center problems with outliers

In this section, we will first give a tight 3-approximation algorithm for the RMatCenter problem, improving upon the 7-approximation algorithm by Chen et. al. [5]. Then we study the FRMatCenter
problem and prove the second part of Theorem 1.4.
13

5.1

The robust matroid center problem

Suppose I = (V, d, M, t) is an instance of the RMatCenter problem with optimal radius R. Let rM
denote the rank function of M. Consider the polytope PRMatCenter containing points (x, y) satisfying
constraints (1)–(4), and the matroid rank constraints:
y(U ) ≤ rM (U ),

∀U ⊆ V.

(8)

Since R is the optimal radius, it is not difficult to check that PRMatCenter 6= ∅. Let us pick any
fractional solution (x, y) ∈ PRMatCenter . The next step is to round (x, y) into an integral solution. Our
3-approximation algorithm is as follows.
Algorithm 9 RM AT C ENTER ROUND (x, y)
(V 0 , ~c) ← 
RF ILTERING (x, y) .
0
2: Let P := z ∈ [0, 1]V : z(U ) ≤ rM (U ) ∀U ⊆ V ∧ z(Fi ) ≤ 1 ∀i ∈ V 0
3: Find a basic solution Y ∈ P 0 which maximizes the linear function f : [0, 1]V → R defined as
X X
f (z) :=
cj
zi for z ∈ [0, 1]V .
1:

j∈V 0

4:

i∈Fj

return S = {i ∈ V : Yi = 1}.

Analysis. Again, by construction, the clusters Fi are pairwise disjoint for i ∈ V 0 . Note that P 0 is the
matroid intersection polytope between M and another partition matroid polytope saying that at most
one item per set Fi for i ∈ V 0 can be chosen. Moreover, y ∈ P 0 implies that P 0 6= ∅. Thus, P 0 has
integral extreme points and optimizing over P 0 can be done in polynomial time. Note that the solution
S is feasible as it satisfies the matroid constraint. The correctness of RM AT C ENTER ROUND follows
immediately by the following two propositions.
Proposition 5.1. There are at least f (Y ) vertices in V that are at distance at most 3R from some open
center in S.
Proof. Recall that S is the set of vertices i ∈ V such that Yi = 1. Moreover, since Y (Fj ) ≤ 1, there can
be at most one open center in Fj (i.e., |S ∩ Fj | ≤ 1) for each j ∈ V 0 . For any j ∈ V 0 ,
• if Y (Fj ) = 0, then there is no open center in Fj and its contribution in f (Y ) is zero,
• if Y (Fj ) = 1, then we open some center i ∈ Fj and the contribution of j to f (Y ) is equal
to cj . (Recall that cj is the number of clusters Fk with Fj ∩ Fk 6= ∅.) By triangle inequality,
d(k, i) ≤ d(k, j) + d(j, i) ≤ 2R + R = 3R.
Proposition 5.2. We have f (Y ) ≥ t.
Proof. For each j ∈ V 0 and i ∈ Fj , define yi0 := xij (this is well-defined as all clusters Fj for j ∈ V 0
are pairwise disjoint). Also, set yi0 := 0 for other vertices i not belonging to any marked cluster. Then,
by greedy choice and constraint (1), we have
X
X
X
f (y 0 ) =
cj y 0 (Fj ) =
cj sj ≥
sj ≥ t.
j∈V 0

j∈V 0

By the choice of Y , we have f (Y ) ≥ f (y 0 ) ≥ t.
This analysis proves the second part of Theorem 1.1.
14

j∈V

5.2

The fair robust matroid center problem

In this section, we consider the FRMatCenter problem. It is not difficult to modify and randomize
algorithm RMC ENTER ROUND so that it would return a random solution satisfying both the fairness
guarantee and matroid constraint, and preserving the coverage constraint in expectation. This can be
done by randomly picking Y inside P 0 . However, if we want to obtain some concrete guarantee on
the coverage constraint, we may have to (slightly) violate either the matroid constraint or the fairness
guarantee. We leave it as an open question whether there exists a true approximation algorithm for this
problem.
We will start with a pseudo-approximation algorithm which always returns a basis of M plus at most
one extra center. Our algorithm is quite involved. We first carefully round a fractional solution inside
a matroid intersection polytope into a (random) point with a special property: the unrounded variables
form a single path connecting some clusters and tight matroid rank constraints. Next, rounding this
point will ensure that all but one cluster has an open center. Then opening one extra center is sufficient
to cover at least t clients.
Finally, using a similar preprocessing step similar to the one in Section 4.2.3, we correct the solution
by removing the extra center without affecting the fairness and coverage guarantees by too much. This
algorithm concludes Theorem 1.4.
5.2.1

A pseudo-approximation algorithm

Suppose I = (V, d, M, t, p~) is an instance the robust matroid center problem with the optimal radius
R. Let rM denote the rank function of M and PM be the matroid base polytope of M. Consider the
polytope PFRMatCenter containing points (x, y) satisfying constraints (1)–(4), the fairness constraint (5),
and the matroid constraints (8). We note that PFRMatCenter is a valid relaxation.
The main algorithm is summarized in Algorithm 10, which can round any vertex point (x, y) ∈
PFRMatCenter . Basically, we will round y iteratively. In each round, we construct a (multi)-bipartite
graph where vertices on the left side are the disjoint sets O1 , O2 , . . . in Corollary 2.4. Vertices on the
right side are corresponding to the disjoint sets F1 , F2 , . . . returned by RF ILTERING. Now each edge of
the bipartite graph, connecting Oi and Fj , represents some unrounded variable yv ∈ (0, 1) where v ∈ Oi
and v ∈ Fj . See Figure 1.
L

v
Oi

R

yv 2 (0, 1)

v

Fj

Figure 1: Construction of the multi-bipartite graph H = (L, R, EH ) in the main algorithm.
Then we carefully pick a cycle (path) on this graph and round variables on the edges of this cycle
(path). This is done by subroutines ROUND C YCLE, ROUND S INGLE PATH, and ROUND T WO PATHS.
See Figures 2, 3, and 4. Basically, these procedures will first choose a direction ~r which alternatively

15

increases and decreases the variables on the cycle (path) so that (i) all tight matroid constraints are
preserved and (ii) the number of (fractionally) covered clients is also preserved. Now we randomly
move y along ~r or −~r to ensure that all the marginal probabilities are preserved.
Finally, all the remaining, fractional variables will form one path on the bipartite graph. We round
these variables by the procedure ROUND F INAL PATH which exploits the integrality of any face of a
matroid intersection polytope. Then, to cover at least t clients, we may need to open one extra facility.
Algorithm 10 P SEUDO FRMC ENTER ROUND (x, y)
1:
2:
3:
4:
5:
6:
7:

8:

9:

(V 0 , ~c) ← RF ILTERING (x, y) and let F ← {Fj : j ∈ V 0 }
Set yi0 ← xij for all j ∈ V 0S
, i ∈ Fj
Set yi0 ← 0 for all i ∈ V \ j∈V 0 Fj
while y 0 still contains some fractional values do
Note that y 0 ∈ PM . Compute the disjoint sets O1 , . . . , Ot and constants bO1 , . . . , bOt as in
Corollary 2.4. S
S
Let O0 ← V \ ti=1 Oi and F0 ← V \ j∈V 0 Fj
Construct a multi-bipartite graph H = (L, R, EH ) where
• each vertex i ∈ L, where L = {0, . . . , t}, is corresponding to the set Oi
• each vertex j ∈ R, where R = {0} ∪ {k : Fk ∈ F}, is corresponding to the set Fj
• for each vertex v ∈ V such that yv ∈ (0, 1): if v belongs to some set Oi and Fj , add an
edge e with label v connecting i ∈ L and j ∈ R.
Check the following cases (in order):
• Case 1: H contains a cycle. Let ~v = (v1 , v2 , . . . , v2` ) be the sequence of edge labels on
this cycle. Update y 0 ← ROUND C YCLE(y 0 , ~v ) and go to line 4.
• Case 2: H contains a maximal path with one endpoint in L and the other in R. Let
~v = (v1 , v2 , . . . , v2`+1 ) be the sequence of edge labels on this path. Update y 0 ←
ROUND S INGLE PATH(y 0 , ~v ) and go to line 4.
• Case 3: There are at least 2 distinct maximal paths (not necessarily disjoint) having both
endpoints in R. Let ~v1 , ~v2 be the sequences of edge labels on these two paths. Update
y 0 ← ROUND T WO PATHS(y 0 , ~v1 , ~v2 , ~c) and go to line 4.
• The remaining case: all edges in H form a single path with both endpoints in
R. Let (v1 , v2 , . . . , v2` ) be the sequence of edge labels on this path. Let Y ←
ROUND F INAL PATH(y 0 , ~v ) and exit the loop.
return S = {i ∈ V : Yi = 1}.

Proposition 5.3. The polytyope PFRMatCenter is non-empty.
Proof. The proof is similar to Proposition 3.1, and is omitted.
We now explain how to implement the rounding steps in this algorithm. These are all based on the
subroutine ROUND S INGLE P OINT, which moves the vector y as far as possible along the direction of
vector ~r until it a new face of the polytope begins tight. We define it formally as Algorithm 11; note that
it can be implemented efficiently by solving an appropriate LP.
Algorithm 11 ROUND S INGLE P OINT (y, ~r)
Select δ ∗ ≥ 0 to be maximal such that the vector z + δ ∗ r is in PM .
2: return (y + δ ∗~
r, δ ∗ ).

1:

16

Algorithm 12 ROUND C YCLE (y 0 , ~v )
Initialize ~r = ~0, then set rvj = (−1)j for j = 1, 2, . . . , |~v |
2: (y1 , δ1 ) ←ROUND S INGLE P OINT(y 0 , ~
r)
3: return y1
1:

+

yv1

1

yv2

1

1

yv6
yv3

+

yv4

1

1

yv5

+

1

Figure 2: The left part shows a cycle. The right part shows how the variables on the cycle are being
changed by ROUND C YCLE.
Algorithm 13 ROUND S INGLE PATH (y 0 , ~v )
Initialize ~r = ~0, then set rvj = (−1)j+1 for j = 1, 2, . . . , |~v |
2: (y1 , δ1 ) ←ROUND S INGLE P OINT(y 0 , ~
r)
3: return y1
1:

+

yv1

1

yv2
1

yv3

+

yv4

1

+

yv5
O0

1

1

O0

Figure 3: The left part shows a single path. The right part shows how the variables on the path are being
changed by ROUND S INGLE PATH.
17

Algorithm 14 ROUND T WO PATHS (y 0 , ~v , ~v 0 , ~c)
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:

WLOG, suppose j1 , j2 ∈ R are endpoints of v1 , v2` of the path ~v respectively and cj1 ≥ cj2
0 of the path ~
WLOG, suppose j10 , j20 ∈ R are endpoints of v10 , v2`
v 0 respectively and cj10 ≥ cj20
0
∆1 ← cj1 − cj2 ; ∆2 ← cj10 − cj20 ; ~r ← ~0
V1+ ← {v1 , v3 , . . . , v2`−1 }; V1− ← {v2 , v4 , . . . , v2` }
0 }; V − ← {v 0 , v 0 , . . . , v 0
V2+ ← {v20 , v40 , . . . , v2`
0
1 3
2
2`0 −1 }
+
for each v ∈ V1 : rv ← rv + 1; for each v ∈ V1− : rv ← rv − 1
for each v ∈ V2+ : rv ← rv + ∆1 /∆2 ; for each v ∈ V2− : rv ← rv − ∆1 /∆2
(y1 , δ1 ) ←ROUND S INGLE P OINT(y 0 , ~r)
(y2 , δ2 ) ←ROUND S INGLE P OINT(y 0 , −~r)
With probability δ1 /(δ1 + δ2 ): return y2
With remaining probability δ2 /(δ1 + δ2 ): return y1

j1

yv1

yv2

y

+

j1
2

1
v10

+

1

+

+

1

1

j10

yv3 , yv20

2

j2

1

j20

+

+

1

1

2

2

+

yv30

2

j10

1

yv4

j1

1

1

j2

2

2

2

1
2

j10

1
2

2

+

2

1
2

j2

yv40
1

1
2

j20

2

1

j20

2

Figure 4: The left part shows an example of two distinct maximal paths chosen in Case 3. The black
edge is common in both paths. The middle and right parts are two possibilities of rounding y. With
probability δ1 /(δ1 + δ2 ), the strategy in the right part is adopted. Otherwise, the strategy in the middle
part is chosen.

Algorithm 15 ROUND F INAL PATH (y, ~v )

1: P1 ← z ∈ [0, 1]V : z(U ) ≤ rM (U ) ∀U ⊆ V ∧ z(Oi ) = bOi ∀i ∈ L \ {0} ∧ zi = 0 ∀i : yi = 0
2: P2 ← {z ∈ [0, 1]V : z(Fj ) = y(Fj ) ∀j ∈ V 0 \ J ∧ z(Fj ) ≤ 1 ∀j ∈ J}, where J ⊆ R is the set of
vertices in R on the path ~v .
3: Pick an arbitrary extreme point ŷ of P 0 = P1 ∩ P2
4: for each j ∈ R and j is on the path ~
v : if ŷ(Fj ) = 0, pick an arbitrary u ∈ Fj and set ŷu ← 1.
5: return ŷ

18

5.2.2

Analysis of P SEUDO FRMC ENTER ROUND

Proposition 5.4. In all but the last iteration, the while-loop (lines 4 to 8) of P SEUDO FRMC ENTER ROUND preserves the following invariant: if y 0 lies in the face D of PM (w.r.t all tight matroid rank
constraints) at the beginning of the iteration, then y 0 ∈ D at the end of this iteration.
Proof. Observe that y 0 ∈ PM at the beginning of the first iteration due to the definition of y 0 . Fix any
iteration. Let y 00 be the updated y 0 at the end of the iteration. By Corollary 2.4, it suffices to show that
y 00 ∈ {x ∈ Rn : x(S) = bS ∀S ∈ O; xi = 0 ∀i ∈ J; x ∈ PM } ,
where J ⊆ V is the set of all vertices i with yi0 = 0. Note that y 00 is the output of one of the three subroutines ROUND C YCLE, ROUND S INGLE PATH, and ROUND T WO PATHS. Since we only round floating
variables strictly greater than zero, we have yi00 = 0 for all i ∈ J. Also, the procedure ROUND S INGLE P OINT guarantees that y 00 ∈ PM .
• When calling the procedure ROUND C YCLE, observe that each vertex j ∈ L on the cycle is adjacent to exactly two edges. By construction, we always increase the variable on one edge and
decrease the variable on the other edge at the same rate. See Figure 2. Therefore, y 00 (Oj ) =
y 0 (Oj ) = bOj for all j ∈ O.
• When calling the procedure ROUND S INGLE PATH, recall that our path is maximal and has one
endpoint in L and the other in R. We claim that the left endpoint of this path should be corresponding to the set O0 . Otherwise, suppose it is some set Oj with j > 0. We have the tight
constraint y 0 (Oj ) = bOj ∈ Z+ . Then the degree of the vertex j must be at least 2 as there must be
at least two fractional variables in this set. This contradicts to the fact that our path is maximal.
See Figure 3. By the same argument as before, we have y 00 (Oj ) = y 0 (Oj ) = bOj for all j ∈ O.
• In the procedure ROUND T WO PATHS, we round the variables on two paths which have both endpoints in R. Thus, any vertex j should be adjacent to either 2 or 4 edges. Again, by construction,
the net change in y 0 (Oj ) is equal to zero. See Figure 4.
Finally, the claim follows by induction.
Proposition 5.5. P SEUDO FRMC ENTER ROUND terminates in polynomial time.
Proof. Note that, in each iteration, each floating variable yv0 ∈ (0, 1) corresponds to exactly one edge in
the bipartite graph. This is because, by construction, the sets O0 , . . . , Ot form a partition of V and the
sets in F and F0 also form a partition of V . Thus, as long as there are fractional values in y 0 , our graph
will have some cycle or path.
Now we will show that the while-loop (lines 4 to 8) terminates after O(|V |) iterations. For any set
S, let χ(S) denote the characteristic vector of S. That is, χ(v) = 1 for v ∈ S and χ(v) = 0 otherwise.
Let us fix any iteration and let T = {χ(S) : S ⊆ V ∧ y 0 (S) = rM (S)} be the set of all tight
constraints. In this iteration, we will move y 0 along some direction ~r as far as possible (by procedure
ROUND S INGLE P OINT). It means that the new point y 00 = y 0 + δ ∗~r will either have at least one more
rounded variable or hit a new tight constraint y 00 (S0 ) = rM (S0 ) (while y 0 (S0 ) < rM (S0 )) for some
S0 ⊆ V . Indeed χ(S0 ) is linearly independent of all vectors in T .
Proposition 5.4 says that all the tight constraints are preserved in the rounding process. Therefore,
in the next iteration, we either have at least one more rounded variable or the rank of T is increased by
at least 1. This implies the algorithm terminates after at most |V | iterations.
Proposition 5.6. In all iterations, the while-loop (lines 4 to 8) of P SEUDO FRMC ENTER ROUND satisfies the invariant that y 0 (Fj ) ≤ 1 for all Fj ∈ F.

19

Proof. By constraints 2 and 3, this property is true at the beginning of the first iteration. By a very
similar argument as in the proof of Proposition 5.4, this is also true during all but the last iteration. (Note
that if j is an endpoint of a path, then j must be adjacent to exactly one fractional value yv0 , which could
be rounded to one, while other variables {yv0 0 : v 0 ∈ Fj , v 0 6= v} are already rounded to zero as our path
is maximal.) Finally, it is not hard to check that procedure ROUND F INAL PATH also does not violate this
invariant.
Proposition 5.7. P SEUDO FRMC ENTER ROUND returns a solution S which is some independent set of
M plus (at most) one extra vertex in V .
Proof. Let us focus on the procedure ROUND F INAL PATH. Recall that the polytope P 0 in ROUND F I NAL PATH is the intersection of the following two polytopes:

P1 = z ∈ [0, 1]V : z(U ) ≤ rM (U ) ∀U ⊆ V ∧ z(Oi ) = bOi ∀i ∈ L \ {0} ∧ zi = 0 ∀i : yi = 0 ,
and
P2 = {z ∈ [0, 1]V : z(Fj ) = y(Fj ) ∀j ∈ V 0 \ J ∧ z(Fj ) ≤ 1 ∀j ∈ J},
where J ⊆ R is the set of vertices in R on the path ~v .
By construction, P1 is the face of the matroid base polytope PM corresponding to all tight constraints of y. It is well-known that P1 itself is also a matroid base polytope. By Propositions 5.4 and
5.6, we have y ∈ P1 and y ∈ P2 . Thus, y ∈ P which implies that P 6= ∅. Moreover, P2 is a partition
matroid polytope. (Observe that z(Fj ) = y(Fj ) ∈ {0, 1} ∀j ∈ V 0 \ J since all fractional variables are
on the path ~v .) Therefore, P = P1 ∩ P2 has integral extreme points and the point ŷ chosen in line 3 is
integral.
Finally, recall that ~v = (v1 , v2 , . . . , v2` ) is a simple path with both endpoints in R. The constraints
of P1 and integrality of bOi ’s ensure that ŷv1 + ŷv2 = 1, ŷv3 + ŷv4 = 1, . . . , ŷv2`−1 + ŷv2` = 1. In other
words, every vertex i ∈ L on the path will be “matched” with exactly one vertex in R. Thus, there can
be at most one vertex j ∈ R on the path such that ŷ(Fj ) = 0 in line 4. Opening u ∈ Fj adds one extra
facility to our solution.
Recall that C is the (random) set of all clients within radius 3R from some center in S, where R is
the optimal radius. The following two propositions will conclude our analysis.
Proposition 5.8. |C| ≥ t with probability one.
P
P
Proof. Let f denote the function defined in Algorithm RMC ENTER ROUND (i.e., f (z) = j∈V 0 i∈Fi zi
for any z ∈ [0, 1]V .) Using a similar argument as in the proof of Proposition 5.1, one can easily verify
that there are at least f (Y ) vertices in V that are within radius 3R from some open center in S. Next, it
suffices to show that f (Y ) ≥ t.
By definition of y 0 in lines 2 and 3, we have f (y 0 ) ≥ t (see the proof of Proposition 5.2.) We now
claim that f (y 0 ) is not decreasing after each iteration of the rounding scheme. We check the following
cases:
• Case y 0 is rounded by ROUND C YCLE: observe that y 0 (Fj ) is preserved for all j ∈ R since j is
adjacent to two edges and we increase/decrease the corresponding variables by the same amount.
Thus, f (y 0 ) is unchanged.
• Case y 0 is rounded by ROUND S INGLE PATH: if j ∈ R is not the endpoint of the path then j is
adjacent to two edges on the path and y 0 (Fj ) is unchanged. If j is the endpoint, then we increase
the variable on the adjacent edge; and hence, y 0 (Fj ) will increase. See Figure 3.
• Case y 0 is rounded by ROUND T WO PATHS: again, for any j ∈ R \ {j1 , j2 , j10 , j20 }, the value of
y 0 (Fj ) remains unchanged in the process. We now verify the change in f caused by the four

20

endpoints j1 , j2 , j10 , and j20 . Suppose y1 is returned, the contribution of these points in f (y1 ) is
cj1 y1 (Fj1 ) + cj2 y1 (Fj2 ) + cj10 y1 (Fj10 ) + cj20 y1 (Fj20 )




∆1
∆1
0
0
0
0
0
0
= cj1 (y (Fj1 ) + δ1 ) + cj2 (y (Fj2 ) − δ1 ) + cj1 y(Fj1 ) − δ1
+ cj2 y(Fj2 ) + δ1
∆2
∆2
∆1
= cj1 y 0 (Fj1 ) + cj2 y 0 (Fj2 ) + cj10 y 0 (Fj10 ) + cj20 y 0 (Fj20 ) + δ1 (cj1 − cj2 ) + δ1
(c 0 − cj10 )
∆ 2 j2
= cj1 y 0 (Fj1 ) + cj2 y 0 (Fj2 ) + cj10 y 0 (Fj10 ) + cj20 y 0 (Fj20 ).
Hence, f (y1 ) = f (y 0 ). Similarly, one can verify that f (y2 ) = f (y 0 ).
• Case y 0 is rounded by ROUND F INAL PATH: we have shown in the proof of Proposition 5.7 that
y 0 (Fj ) = 1 for all j ∈ J where J is the set of vertices in R on the path ~v . This fact and the other
constraints of P2 ensure that y 0 (Fj ) is not decreasing for all j ∈ V 0 .
Proposition 5.9. Pr[j ∈ C] ≥ pj for all j ∈ V .

Proof. Let y 0 be the vector defined as in lines 2 and 3 of P SEUDO FRMC ENTER ROUND. It suffices to
show that, for all j ∈ V 0 , Pr[Y (Fj ) = 1] ≥ y 0 (Fj ). (Note that y 0 (Fj ) ≥ pj by constraint (5).) This
is because, for any vertex k ∈ V \ V 0P
, the algorithmPRF ILTERING guarantees that there exists j ∈ V 0
0
such that Fk ∩ Fj 6= ∅, and y (Fj ) = i∈Bj xij ≥ i∈V :d(i,k)≤R xik = y 0 (Fk ). Notice that the event
Y (Fj ) = 1 means there is some open center Fj and the distance from k to this center should be at most
3R. Thus,
Pr[k ∈ C] ≥ Pr[Y (Fj ) = 1] ≥ y 0 (Fj ) ≥ y 0 (Fk ) ≥ pk ,
by constraint (5).
Fix any j ∈ V 0 . Recall that Y is obtained by rounding y 0 and, by Proposition 5.6 and the proof of
5.7, we have Y (Fj ) ∈ {0, 1} and Pr[Y (Fj ) = 1] = E[Y (Fj )]. We now show that the expected value of
y 0 (Fj ) does not decrease after each iteration of the while-loop.
• Case y 0 is rounded by ROUND C YCLE: y 0 (Fj ) is unchanged as before.
• Case y 0 is rounded by ROUND S INGLE PATH: if j is not the endpoint of ~v then y 0 (Fj ) is unchanged.
Otherwise, y 0 (Fj ) is increase by some δ1 > 0 with probability one.
• Case y 0 is rounded by ROUND T WO PATHS: again, if j ∈
/ {j1 , j2 , j10 , j20 } then y 0 (Fj ) is unchanged.
Now suppose j = j1 . With probability δ1 /(δ1 + δ2 ), y 0 (Fj1 ) is increase by δ2 , and, with the
remaining probability, it is decreased by δ1 . Thus, the expected change in y 0 (Fj1 ) is
δ1
δ2
(δ2 ) +
(−δ1 ) = 0.
δ1 + δ2
δ1 + δ2
Similarly, one can verify that the expected values of y 0 (Fj2 ), y 0 (Fj10 ), and y 0 (Fj20 ) remain the same.
• Case y 0 is rounded by ROUND F INAL PATH: we have showed in the proof of Proposition 5.7 that if
j is on the path ~v , then Y (Fj ) = 1. Otherwise, the constraints of P2 ensure that Y (Fj ) = y 0 (Fj ).
So far we have proved the following theorem.
Theorem 5.10. P SEUDO FRMC ENTER ROUND will return a random solution S such that
• S is the union of some basis of M with (at most) one extra vertex,
• |C| ≥ t with probability one,
• Pr[j ∈ C] ≥ pj for all j ∈ V .
21

5.2.3

An algorithm satisfying the matroid constraint exactly

Using a similar technique as in Section 4.2.3, we will develop an approximation algorithm for the FRMatCenter problem which always returns a feasible solution. Let  > 0 a small parameter to be
determined. Let U denote the collection of all possible sets of verticies with size at most d1/e such that
U is an independent set of M. Again, we have |U| ≤ nO(1/) . Suppose R is the optimal radius to our
instance. For any i ∈ V , recall that RBall(i, U, R) is the set of red vertices within radius 3R from i.
Consider the configuration polytope Pconfig3 containing points (x, y, q) with the following constraints:
P
qU = 1



PU ∈U U


x ≤ qU
∀j ∈ V, U ∈ U


Pi∈Bj Pij

U

∀j ∈ V

U ∈U
i∈Bj xij ≥ pj



U
U


≤ yi
∀i, j ∈ V, U ∈ U
x
Pij
U
y ≤ qU rM (W )
∀U ∈ U, W ⊆ V

Pi∈W Pi

U



j∈V
i∈Bj xij ≥ qU t




yiU = 1
∀U ∈ U, i ∈ U




U

yi = 0
∀U ∈ U, i ∈ V \ U, |RBall(i, U, R)| ≥ n


 U U
xij , yi , qU ≥ 0
∀i, j ∈ V, U ∈ U
We first claim that Pconfig3 is a valid relaxation for the problem.
Proposition 5.11. The polytope Pconfig3 is non-empty.
Proof. Suppose S is a solution drawn from the optimal distribution D. We compute a subset US of S
using a similar procedure as in the proof of Proposition 4.4. Recall that |RBall(i, US , R)| < n for all
i ∈ S \ US and |US | ≤ d1/e. Since US ⊆ S, US is also an independent set of M, implying that
US ∈ U.
Now for any U ∈ U, we set qU := Pr[US = U ]. Let xU
ij be probability of the joint event: US = U
U be the probability of the joint event: U = U and i ∈ S. Then it
and j is connected
to
i.
Finally,
let
y
S
i
P
is clear that U ∈U qU = 1. Using similar arguments to the proofs of Propositions 4.4 and 4.3, we have
the following inequalities:
X
xU
∀j ∈ V, U ∈ U
(9)
ij ≤ qU ,
i∈Bj

X X
U ∈U i∈Bj

XX
j∈V i∈Bj

xU
ij ≥ pj ,

∀j ∈ V

(10)

xU
ij ≥ qU t,

(11)

yiU = 0 ∀U ∈ U, i ∈ V \ U, |RBall(i, U, R)| ≥ n.

(12)

Recall that yiU /qU is the Pr[i ∈ S | U = US ]. Since S is independent with probability one, we have
|S ∩ W | ≤ rM (W ) for all W ⊆ V . Therefore,
X
X
rM (W ) ≥ E[|S ∩ W | | U = US ] =
Pr[i ∈ S | U = US ] =
yiU /qU ,
i∈W

i∈W

for all W ⊆ V .
The other constraints can be verified easily. We conclude that (x, y, q) ∈ Pconfig3 .
Next, let us pick any (x, y, q) ∈ Pconfig3 and use the following algorithm to round it.
22

Algorithm 16 FRMC ENTER ROUND (x, y, q)
1:
2:
3:
4:
5:

Randomly pick a set U ∈ U with probability qU
0
U
Let x0ij ← xU
ij /qU and yi ← min{yi /qU , 1}
0
S ← P SEUDO FRMC ENTER ROUND (x0 , y 0 )
Let i∗ be the “extra” vertex in S 0 .
return S = S 0 \ {i}

Analysis. We are now ready to prove the second part of Theorem 1.4. Let us fix any γ > 0 and set
 := γ 2 . Also, let E(U ) be the event that Algorithm 16 selects U ∈ U. Note that (x0 , y 0 ) satisfies the
following inequalities:
XX
x0ij ≥ t,
j∈V i∈Bj

X
i∈Bj

X

x0ij ≤ 1,
x0ij =

i∈Bj

∀j ∈ V,

X

xij /qU ,

i∈Bj

∀j ∈ V,

x0ij ≤ yi0 , ∀i, j ∈ V,
X
yi0 ≤ rM (W ), ∀W ⊆ V.

i∈W

Moreover, every i ∈ U satisfies yi0 = 1; every i ∈ V \ U with RBall(i, U, R) ≥ n satisfies yi0 = 0.
Recall that the algorithm P SEUDO FRMC ENTER ROUND will return a solution S 0 , which is the union
of a basis of M with an extra center i∗ . The vertex i∗ has yi∗ ∈ (0, 1), and in particular i∗ ∈
/ U . By
removing i∗ from S 0 , we ensure that the resulting set is a basis of M with probability one.
Now we shall prove the coverage guarantee. By Theorem 5.10, S 0 covers at least t vertices within
radius 3R. Any blue vertex can be connected to some center in U and hence is not affected by the
removal of i∗ . Because i∗ covers at most n other red vertices, we have
|C| ≥ t − n = 1 − γ 2 n.
For any j ∈ V , let Xj be the indicator random variable for the event that d(j, S 0 ) ≤ 3R but
0
∗
d(j,
P S \ {i }) > 3R. We say that j is a bad vertex iff E[Xj ] ≥ γ, otherwise, j is good. Again,
j∈V Xj ≤ n with probability one. Thus, there can be at most n/γ bad vertices. Letting T be the set
of good vertices, we have
|T | ≥ n − n/γ = (1 − γ)n.
By Theorem 5.10, Pr[j is covered by S 0 ] ≥ pj . So, for any j ∈ T , we have

Pr[j ∈ C] ≥ Pr[j is covered by S 0 ] − Pr[Xj = 1] ≥ pj − γ.

23

References
[1] Sara Ahmadian, Ashkan Norouzi-Fard, Ola Svensson, and Justin Ward. Better guarantees for
k-means and euclidean k-median by primal-dual algorithms. CoRR, abs/1612.07925, 2016.
[2] Jaroslaw Byrka, Thomas Pensyl, Bartosz Rybicki, Aravind Srinivasan, and Khoa Trinh. An improved approximation for k-median, and positive correlation in budgeted optimization. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, (SODA), pages 737–756,
2015.
[3] Deeparnab Chakrabarty, Prachi Goyal, and Ravishankar Krishnaswamy. The non-uniform k-center
problem. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP
2016), volume 55, pages 67:1–67:15, 2016.
[4] Moses Charikar, Samir Khuller, David M. Mount, and Giri Narasimhan. Algorithms for facility
location problems with outliers. In Proceedings of the Twelfth Annual ACM-SIAM Symposium
on Discrete Algorithms, SODA ’01, pages 642–651, Philadelphia, PA, USA, 2001. Society for
Industrial and Applied Mathematics.
[5] Danny Z. Chen, Jian Li, Hongyu Liang, and Haitao Wang. Matroid and knapsack center problems. Integer Programming and Combinatorial Optimization: 16th International Conference,
IPCO 2013, Valparaı́so, Chile, March 18-20, 2013. Proceedings, pages 110–122, 2013.
[6] David G. Harris, Thomas Pensyl, Aravind Srinivasan, and Khoa Trinh. Symmetric randomized
dependent rounding. CoRR, abs/1709.06995, 2017.
[7] Dorit S. Hochbaum and David B. Shmoys. A unified approach to approximation algorithms for
bottleneck problems. J. ACM, 33(3):533–550, May 1986.
[8] Wen-Lian Hsu and George L. Nemhauser. Easy and hard bottleneck location problems. Discrete
Applied Mathematics, 1(3):209 – 215, 1979.
[9] Tapas Kanungo, David M. Mount, Nathan S. Netanyahu, Christine D. Piatko, Ruth Silverman, and
Angela Y. Wu. A local search approximation algorithm for k-means clustering. Comput. Geom.,
28(2-3):89–112, 2004.
[10] Ravishankar Krishnaswamy, Amit Kumar, Viswanath Nagarajan, Yogish Sabharwal, and Barna
Saha. The matroid median problem. In Proceedings of the annual ACM-SIAM Symposium on
Discrete Algorithms (SODA), pages 1117–1130. SIAM, 2011.
[11] Lap-Chi Lau, R. Ravi, and Mohit Singh. Iterative Methods in Combinatorial Optimization. Cambridge University Press, New York, NY, USA, 1st edition, 2011.
[12] Shi Li and Ola Svensson. Approximating k-median via pseudo-approximation. In STOC, pages
901–910, 2013.
[13] Alexander Schrijver. Combinatorial optimization: polyhedra and efficiency, volume 24. Springer
Science & Business Media, 2003.
[14] Chaitanya Swamy. Improved approximation algorithms for matroid and knapsack median problems and applications. In APPROX/RANDOM 2014, volume 28, pages 403–418, 2014.
[15] David P. Williamson and David B. Shmoys. The Design of Approximation Algorithms. Cambridge
University Press, 2011.

24

