# Robust $k$-Center with Two Types of Radii

Deeparnab Chakrabarty Partially supported by NSF grant #1813053 Maryam
Negahbani

###### Abstract

In the non-uniform $k$-center problem, the objective is to cover points in a
metric space with specified number of balls of different radii. Chakrabarty,
Goyal, and Krishnaswamy [ICALP 2016, Trans. on Algs. 2020] (CGK, henceforth)
give a constant factor approximation when there are two types of radii. In
this paper, we give a constant factor approximation for the two radii case in
the presence of outliers. To achieve this, we need to bypass the technical
barrier of bad integrality gaps in the CGK approach. We do so using “the
ellipsoid method inside the ellipsoid method”: use an outer layer of the
ellipsoid method to reduce to stylized instances and use an inner layer of the
ellipsoid method to solve these specialized instances. This idea is of
independent interest and could be applicable to other problems.

##  1 Introduction

In the non-uniform $k$-center (NU$k$C) problem, one is given a metric space
$(X,d)$ and balls of different radii $r_{1}>\cdots>r_{t}$, with $k_{i}$ balls
of radius type $r_{i}$. The objective is to find a placement $C\subseteq X$ of
centers of these $\sum_{i}k_{i}$ balls, such that they cover $X$ with as
little dilation as possible. More precisely, for every point $x\in X$ there
must exist a center $c\in C$ of some radius type $r_{i}$ such that
$d(x,c)\leq\alpha\cdot r_{i}$ and the objective is to find $C$ with $\alpha$
as small as possible.

Chakrabarty, Goyal, and Krishnaswamy [CGK16] introduced this problem as a
generalization to the vanilla $k$-center problem [Gon85, HS85, HS86] which one
obtains with only one type of radius. One motivation arises from source
location and vehicle routing: imagine you have a fleet of $t$-types of
vehicles of different speeds and your objective is to find depot locations so
that any client point can be served as fast as possible. This can be modeled
as an NU$k$C problem. The second motivation arises in clustering data. The
$k$-center objective forces one towards clustering with equal sized balls,
while the NU$k$C objective gives a more nuanced way to model the problem.
Indeed, NU$k$C generalizes the robust $k$-center problem [CKMN01] which allows
the algorithm to throw away $z$ points as outliers. This is precisely the
NU$k$C problem with two types of radii, $r_{1}=1$, $k_{1}=k$, $r_{2}=0$, and
$k_{2}=z$.

Chakrabarty et al. [CGK16] give a $2$-approximation for the special case of
robust $k$-center which is the best possible [HS85, Gon85]. Furthermore, they
give a $(1+\sqrt{5})$-factor approximation algorithm for the NU$k$C problem
with two types of radii (henceforth, the $2$-NU$k$C problem). [CGK16] also
prove that when $t$, the number of types of radii, is part of the input, there
is no constant factor approximation algorithms unless P=NP. They explicitly
leave open the case when the number of different radii types is a constant,
conjecturing that constant-factor approximations should be possible. We take
the first step towards this by looking at the robust $2$-NU$k$C problem. That
is, the NU$k$C problem with two kinds of radii when we can throw away $z$
outliers. This is the case of $3$-radii with $r_{3}=0$.

######  Theorem 1.

There is a $10$-approximation for the Robust $2$-NU$k$C problem.

Although the above theorem seems a modest step towards the CGK conjecture, it
is in fact a non-trivial one which bypasses multiple technical barriers in the
[CGK16] approach. To do so, our algorithm applies a two-layered round-or-cut
framework, and it is foreseeable that this idea will form a key ingredient for
the constantly many radii case as well. In the rest of this section, we
briefly describe the [CGK16] approach, the technical bottlenecks one faces to
move beyond $2$ types of radii, and our approach to bypass them. A more
detailed description appears in Section 2.

One key observation of [CGK16] connects NU$k$C with the firefighter problem on
trees [FKMR07, CC10, ABZ16]. In the latter problem, one is given a tree where
there is a fire at the root. The objective is to figure out if a specified
number of firefighters can be placed in each layer of the tree, so that the
leaves can be saved. To be precise, the objective is to select $k_{i}$ nodes
from layer $i$ of the tree so that every leaf-to-root path contains at least
one of these selected nodes.

Chakrabarty et al. [CGK16] use the integrality of a natural LP relaxation for
the firefighter problem on height-$2$ trees to obtain their constant factor
approximation for $2$-NU$k$C. In particular, they show how to convert a
fractional solution of the standard LP relaxation of the $2$-NU$k$C problem to
a feasible fractional solution for the firefighter LP. Since the latter LP is
integral for height-2 trees, they obtain an integral firefighting solution
from which they construct an $O(1)$-approximate solution for the $2$-NU$k$C
problem. Unfortunately, this idea breaks down in the presence of outliers as
the firefighter LP on height-2 trees when certain leaves can be burnt (outlier
leaves, so to speak) is not integral anymore. In fact, the standard LP-
relaxation for Robust $2$-NU$k$C has unbounded integrality gap. This is the
first bottleneck in the CGK approach.

Although the LP relaxation for the firefighter problem on height-2 trees is
not integral when some leaves can be burnt, the problem itself (in fact for
any constant height) is solvable in polynomial time using dynamic programming
(DP). Using the DP, one can then obtain (see, for instance, [Kaibel11]) a
polynomial sized integral LP formulation for the firefighting problem. This
suggests the following enhancement of the CGK approach using the ellipsoid
method. Given a fractional solution $\mathbf{x}$ to Robust $2$-NU$k$C, use the
CGK approach to obtain a fractional solution $\mathbf{y}$ to the firefighting
problem. If $\mathbf{y}$ is feasible for the integral LP formulation, then we
get an integral solution to the firefighting problem which in turn gives an
$O(1)$-approximation for the Robust $2$-NU$k$C instance via the CGK approach.
Otherwise, we would get a separating hyperplane for $\mathbf{y}$ and the poly-
sized integral formulation for firefighting. If we could only use this to
separate the fractional solution $\mathbf{x}$ from the integer hull of the
Robust $2$-NU$k$C problem, then we could use the ellipsoid method to
approximate Robust $2$-NU$k$C. This is the so-called “round-or-cut” technique
in approximation algorithms.

Unfortunately, this method also fails and indicates a much more serious
bottleneck in the CGK approach. Specifically, there is an instance of Robust
$2$-NU$k$C and an $\mathbf{x}$ in the integer hull of its solutions, such that
the firefighting instance output by the CGK has no integral solution! Thus,
one needs to enhance the CGK approach in order to obtain $O(1)$-approximations
even for the Robust $2$-NU$k$C problem. The main contribution of this paper is
to provide such an approach. We show that if the firefighting instance does
not have an integral solution, then we can tease out many stylized Robust
$2$-NU$k$C instances on which the round-or-cut method provably succeeds, and
an $O(1)$-approximation to any one of them gives an $O(1)$-approximation to
the original Robust $2$-NU$k$C instance.

Our Approach. Any solution $\mathbf{x}$ in the integer hull of NU$k$C
solutions gives an indication of where different radii centers are opened. As
it turns out, the key factor towards obtaining algorithms for the Robust
$2$-NU$k$C problem is observing where the large radii (that is, radius
$r_{1}$) balls are opened. Our first step is showing that if the fractional
solution $\mathbf{x}$ tends to open the $r_{1}$-centers only on “well-
separated” locations then in fact, the round-or-cut approach described above
works. More precisely, if the Robust $2$-NU$k$C instance is for some reason
forced to open its $r_{1}$ centers on points which are at least $cr_{1}$ apart
from each other for some constant $c>4$, then the CGK approach plus round-or-
cut leads to an $O(1)$-approximation for the Robust $2$-NU$k$C problem. We
stress that this is far from trivial and the natural LP relaxations have bad
gaps even in this case. We use our approach from a previous paper [CN18] to
handle these well-separated instances.

But how and why would such well-separated instances arise? This is where we
use ideas from recent papers on fair colorful clustering [BIPV19, JSS20,
AAKZ20]. If $\mathbf{x}$ suggested that the $r_{1}$-radii centers are not
well-separated, then one does not need that many balls if one allows dilation.
In particular, if $p$ and $q$ are two $r_{1}$-centers of a feasible integral
solution, and $d(p,q)\leq cr_{1}$, then just opening one ball at either $p$ or
$q$ with radius $(c+1)r_{1}$ would cover every point that they each cover with
radius $r_{1}$-balls. Thus, in this case, the approximation algorithm gets a
“saving” in the budget of how many balls it can open. We exploit this savings
in the budget by utilizing yet another observation from Adjiashvili, Baggio,
and Zenklusen [ABZ16] on the natural LP relaxation for the firefighter problem
on trees. This asserts that although the natural LP relaxation for constant
height trees is not integral, one can get integral solutions by violating the
constraints additively by a constant. The aforementioned savings allow us to
get a solution without violating the budget constraints.

In summary, given an instance of the Robust $2$-NU$k$C problem, we run an
outer round-or-cut framework and use it to check whether an instance is well-
separated or not. If not, we straightaway get an approximate solution via the
CGK approach and the ABZ observation. Otherwise, we use enumeration (similar
to [AAKZ20]) to obtain $O(n)$ many different well-separated instances and for
each, run an inner round-or-cut framework. If any of these well-separated
instances are feasible, we get an approximate solution for the initial Robust
$2$-NU$k$C instance. Otherwise, we can assert a separating hyperplane for the
outer round-or-cut framework.

Related Work. NU$k$C was introduced in [CGK16] as a generalization to the
$k$-center problem [Gon85, HS85, HS86] and the robust $k$-center problem
[CKMN01]. In particular CGK reduce NU$k$C to the firefighter problem on trees
which has constant approximations [FKMR07, CC10, ABZ16] and recently, a quasi-
PTAS [RS20]. NU$k$C has also been studied in the _perturbation resilient_
[ABS12, AMM17, CG18] settings. An instance is $\rho$-perturbation resilient if
the optimal clustering does not change even when the metric is perturbed up to
factor $\rho$. Bandapadhyay [B20] gives an exact polynomial time algorithm for
$2$-perturbation resilient instances with constant number of radii.

As mentioned above, part of our approach is inspired by ideas from fair
colorful $k$-center clustering [BIPV19, JSS20, AAKZ20] problems studied
recently. In this problem, the points are divided into $t$ color classes and
we are asked to cover $m_{i}$, $i\in\\{1,\dots,t\\}$ many points from each
color by opening $k$-centers. The idea of moving to well-separated instances
are present in these papers. We should mention, however, that the problems are
different, and their results do not imply ours.

The round-or-cut framework is a powerful approximation algorithm technique
first used in a paper by Carr et al. [CFLP00] for the minimum knapsack
problem, and since then has found use in other areas such as network design
[CCKK15] and clustering [ASS17, L15, L16, CN18, AAKZ20]. Our multi-layered
round-or-cut approach may find uses in other optimization problems as well.

##  2 Detailed Description of Our Approach

In this section, we provide the necessary technical preliminaries required for
proving Theorem 1 and give a more detailed description of the CGK bottleneck
and our approach. We start with notations. Let $(X,d)$ be a metric space on a
set of points $X$ with distance function $d:X\times
X\longrightarrow\mathbb{R}_{\geq 0}$ satisfying the triangle inequality. For
any $u\in X$ we let $B(u,r)$ denote the set of points in a ball of radius $r$
around $u$, that is, $B(u,r)=\\{v\in X:d(u,v)\leq r\\}$. For any set
$U\subseteq X$ and function $f:U\rightarrow\mathbb{R}$, we use the shorthand
notation $f(U):=\sum_{u\in U}f(u)$. For a set $U\subseteq X$ and any $v\in X$
we use $d(v,U)$ to denote $\min_{u\in U}d(v,u)$.

The $2$-radii NU$k$C problem and the robust version are formally defined as
follows.

######  Definition 1 ($2$-NU$k$C and Robust $2$-NU$k$C).

The input to $2$-NU$k$C is a metric space $(X,d)$ along with two radii
$r_{1}>r_{2}\geq 0$ with respective budgets $k_{1},k_{2}\in\mathbb{N}$. The
objective of $2$-NU$k$C is to find the minimum ${\rho}\geq 1$ for which there
exists subsets $S_{1},S_{2}\subseteq X$ such that (a) $|S_{i}|\leq k_{i}$ for
$i\in\\{1,2\\}$, and (b) $\bigcup_{i}\bigcup_{u\in S_{i}}B(u,{\rho}r_{i})=X$.
The input to Robust $2$-NU$k$C contains an extra parameter
$\mathsf{m}\in\mathbb{N}$, and the objective is the same, except that
condition (b) is changed to $|\bigcup_{i}\bigcup_{u\in
S_{i}}B(u,{\rho}r_{i})|\geq\mathsf{m}$.

An instance $\mathcal{I}$ of Robust $2$-NU$k$C is denoted as
$((X,d),(r_{1},r_{2}),(k_{1},k_{2}),\mathsf{m})$. As is standard, we will
focus on the approximate feasibility version of the problem. An algorithm for
this problem takes input an instance $\mathcal{I}$ of Robust $2$-NU$k$C, and
either asserts that $\mathcal{I}$ is infeasible, that is, there is no solution
with $\rho=1$, or provides a solution with $\rho\leq\alpha$. Using binary
search, such an algorithm implies an $\alpha$-approximation for Robust
$2$-NU$k$C.

Linear Programming Relaxations. The following is the natural LP relaxation for
the feasibility version of Robust $2$-NU$k$C. For every point $v\in X$,
$\mathsf{cov}_{i}(v)$ denotes its coverage by balls of radius $r_{i}$.
Variable $x_{i,u}$ denotes the extent to which a ball of radius $r_{i}$ is
open at point $u$. If instance $\mathcal{I}$ is feasible, then the following
polynomial sized system of inequalities has a feasible solution.

$\displaystyle\\{(\mathsf{cov}_{i}(v):v\in
X,i\in\\{1,2\\}):~{}~{}~{}\sum_{v\in X}\mathsf{cov}(v)$
$\displaystyle\geq\mathsf{m}$ (Robust $2$-NU$k$C LP) $\displaystyle\sum_{u\in
X}x_{i,u}$ $\displaystyle\leq k_{i}$ $\displaystyle\forall i\in\\{1,2\\}$
$\displaystyle\mathsf{cov}_{1}(v)=\sum_{u\in
B(v,r_{1})}x_{1,u},~{}~{}\mathsf{cov}_{2}(v)=\sum_{u\in B(v,r_{2})}$
$\displaystyle x_{2,u}$ $\displaystyle\forall v\in X$
$\displaystyle\mathsf{cov}(v)=\mathsf{cov}_{1}(v)+\mathsf{cov}_{2}(v)$
$\displaystyle\leq 1$ $\displaystyle\forall v\in X$ $\displaystyle x_{i,u}$
$\displaystyle\geq 0$ $\displaystyle\forall i\in\\{1,2\\},\forall u\in X\\}$

For our algorithm, we will work with the following integer hull of all
possible fractional coverages. Fix a Robust $2$-NU$k$C instance
$\mathcal{I}=\text{$((X,d),(r_{1},r_{2}),(k_{1},k_{2}),\mathsf{m})$}$ and let
$\mathscr{F}$ be the set of all tuples of subsets $(S_{1},S_{2})$ with
$|S_{i}|\leq k_{i}$. For $v\in X$ and $i\in\\{1,2\\}$, we say $\mathscr{F}$
covers $v$ with radius $r_{i}$ if $d(v,S_{i})\leq r_{i}$. Let
$\mathscr{F}_{i}(v)\subseteq\mathscr{F}$ be the subset of solutions that cover
$v$ with radius $r_{i}$. Moreover, we would like $\mathscr{F}_{1}(v)$ and
$\mathscr{F}_{2}(v)$ to be disjoint, so if $S\in\mathscr{F}_{1}(v)$, we do not
include it in $\mathscr{F}_{2}(v)$. The following is the integer hull of the
coverages. If $\mathcal{I}$ is feasible, there must exist a solution in
$\mathscr{P}^{\mathcal{I}}_{\mathsf{cov}}$.

$\displaystyle\\{(\mathsf{cov}_{i}(v):v\in X,i\in\\{1,2\\}):$
$\displaystyle\sum_{v\in
X}\left(\mathsf{cov}_{1}(v)+\mathsf{cov}_{2}(v)\right)$ $\displaystyle\geq$
$\displaystyle~{}~{}\mathsf{m}$ ($\mathscr{P}^{\mathcal{I}}_{\mathsf{cov}}$)
$\displaystyle\forall v\in X,i\in\\{1,2\\}$
$\displaystyle~{}~{}\mathsf{cov}_{i}(v)-\sum\limits_{S\in\mathscr{F}_{i}(v)}z_{S}$
$\displaystyle=$ $\displaystyle~{}~{}0$
($\mathscr{P}^{\mathcal{I}}_{\mathsf{cov}}$.1)
$\displaystyle\sum\limits_{S\in\mathscr{F}}z_{S}$ $\displaystyle=$
$\displaystyle~{}~{}1$ ($\mathscr{P}^{\mathcal{I}}_{\mathsf{cov}}$.2)
$\displaystyle\forall S\in\mathscr{F}$ $\displaystyle z_{S}$
$\displaystyle\geq$ $\displaystyle 0\\}$
($\mathscr{P}^{\mathcal{I}}_{\mathsf{cov}}$.3)

######  Fact 1.

$\mathscr{P}^{\mathcal{I}}_{\mathsf{cov}}$ lies inside Robust $2$-NU$k$C LP.

Firefighting on Trees. As described in Section 1, the CGK approach [CGK16] is
via the firefighter problem on trees. Since we only focus on Robust
$2$-NU$k$C, the relevant problem is the weighted $2$-level fire fighter
problem. The input includes a set of height-2 trees (stars) with root nodes
$L_{1}$ and leaf nodes $L_{2}$. Each leaf $v\in L_{2}$ has a parent $p(v)\in
L_{1}$ and an integer weight $\mathsf{w}(v)\in\mathbb{N}$. We use
${\mathsf{Leaf}}(u)$ to denote the leaves connected to a $u\in L_{1}$ (that
is, $\\{v\in L_{2}:p(v)=u\\}$). Observe that $\\{{\mathsf{Leaf}}(u):u\in
L_{1}\\}$ partitions $L_{2}$. So we could represent the edges of the trees by
this ${\mathsf{Leaf}}$ partition. Hence the structure is identified as
$(L_{1},L_{2},{\mathsf{Leaf}},\mathsf{w})$.

######  Definition 2 (2-Level Fire Fighter (2-FF) Problem).

Given height-2 trees $(L_{1},L_{2},{\mathsf{Leaf}},\mathsf{w})$ along with
budgets $k_{1},k_{2}\in\mathbb{N}$, a feasible solution is a pair
$T=(T_{1},T_{2})$, $T_{i}\subseteq L_{i}$, such that $|T_{i}|\leq k_{i}$ for
$i\in\\{1,2\\}$. Let $\mathcal{C}(T):=\\{v\in L_{2}:v\in T_{2}\lor p(v)\in
T_{1}\\}$ be the set of leaves covered by $T$. The objective is to maximize
$\mathsf{w}(\mathcal{C}(T))$. Hence a 2-FF instance is represented by
$((L_{1},L_{2},{\mathsf{Leaf}},\mathsf{w}),k_{1},k_{2})$.

The standard LP relaxation for this problem is quite similar to the Robust
$2$-NU$k$C LP. For each vertex $u\in L_{1}\cup L_{2}$ there is a variable
$0\leq y_{u}\leq 1$ that shows the extent to which $u$ is included in the
solution. For a leaf $v$, $Y(v)$ is the fractional amount by which $v$ is
covered through both itself and its parent.

$\displaystyle\max\sum_{v\in L_{2}}\mathsf{w}(v)Y(v):~{}~{}$
$\displaystyle\sum_{u\in L_{i}}y_{u}\leq k_{i},~{}~{}\forall
i\in\\{1,2\\};~{}~{}~{}$ (2-FF LP) $\displaystyle Y(v):=y_{p(v)}+y_{v}\leq
1,~{}\forall v\in L_{2};~{}~{}~{}y_{u}\geq 0,~{}~{}\forall u\in L_{1}\cup
L_{2}$

######  Remark 1.

The following figure shows an example where the above LP relaxation has an
integrality gap. However, 2-FF can be solved via dynamic programming in
$O(n^{3})$ time and has similar sized integral LP relaxations.

Figure 1: A 2-FF instance with budgets $k_{1}=k_{2}=1$. Multiplicity
$\mathsf{w}$ is 1 for the circle leaves and 3 for the triangles. The
highlighted nodes have $y=1/2$ and the rest of the nodes have $y=0$. The
objective value for this $y$ is $4\times 1/2+6=8$ but no integral solution can
get an objective value of more than 7.

###  2.1 CGK’s Approach and its Shortcomings

Given fractional coverages
$(\mathsf{cov}_{1}(v),\mathsf{cov}_{2}(v)~{}:~{}v\in X)$, the CGK algorithm
[CGK16] runs the classic clustering subroutine by Hochbaum and Shmoys [HS85]
in a greedy fashion. In English, the Hochbaum-Shmoys (HS) routine partitions a
metric space such that the representatives of each part are well-separated
with respect to an input parameter. The CGK algorithm obtains a 2-FF instance
by applying the HS routine twice. Once on the whole metric space in decreasing
order of $\mathsf{cov}(v)=\mathsf{cov}_{1}(v)+\mathsf{cov}_{2}(v)$, and the
set of representatives forms the leaf layer $L_{2}$ with weights being the
size of the parts. The next time on $L_{2}$ itself in decreasing order of
$\mathsf{cov}_{1}$ and the representatives form the parent layer $L_{1}$.
These subroutines and the subsequent facts form a part of our algorithm and
analysis.

Algorithm 1 HS

1:Metric $(U,d)$, parameter $r\geq 0$, and assignment
$\\{\mathsf{cov}(v)\in\mathbb{R}_{\geq 0}:v\in U\\}$

2:$R\leftarrow\emptyset$ $\triangleright$ The set of representatives

3:while $U\neq\emptyset$ do

4: $u\leftarrow\arg\max_{v\in U}\mathsf{cov}(v)$ $\triangleright$ The first
client in $U$ in non-increasing $\mathsf{cov}$ order

5: $R\leftarrow R\cup u$

6: ${\mathsf{Child}}(u)\leftarrow\\{v\in U:d(u,v)\leq r\\}$$\triangleright$
Points in $U$ at distance $r$ from $u$ (including $u$ itself)

7: $U\leftarrow U\backslash{\mathsf{Child}}(u)$

8:end while

9:$R$, $\\{{\mathsf{Child}}(u):u\in R\\}$

Algorithm 2 CGK

1:Robust $2$-NU$k$C instance $((X,d),(r_{1},r_{2}),(k_{1},k_{2}),\mathsf{m})$,
dilation factors $\alpha_{1},\alpha_{2}>0$, and assignments
$\mathsf{cov}_{1}(v),\mathsf{cov}_{2}(v)\in\mathbb{R}_{\geq 0}$ for all $v\in
X$

2:$(L_{2},\\{{\mathsf{Child}}_{2}(v),v\in
L_{2}\\})\leftarrow\textsf{HS}((X,d),\alpha_{2}r_{2},\mathsf{cov}=\mathsf{cov}_{1}+\mathsf{cov}_{2})$

3:$(L_{1},\\{{\mathsf{Child}}_{1}(v),v\in
L_{1}\\})\leftarrow\textsf{HS}((L_{2},d),\alpha_{1}r_{1},\mathsf{cov}_{1})$

4:$\mathsf{w}(v)\leftarrow|{\mathsf{Child}}_{2}(v)|$ for all $v\in L_{2}$

5:${\mathsf{Leaf}}(u)\leftarrow{\mathsf{Child}}_{1}(u)$ for all $u\in L_{1}$

6:2-FF instance
$(\text{$(L_{1},L_{2},{\mathsf{Leaf}},\mathsf{w})$},(k_{1},k_{2}))$

######  Definition 3 (Valuable 2-FF instances).

We call an instance $\mathcal{T}$ returned by the CGK algorithm valuable if it
has an integral solution of total weight at least $\mathsf{m}$. Using dynamic
programming, there is a polynomial time algorithm to check whether
$\mathcal{T}$ is valuable.

######  Fact 2.

The following are true regarding the output of HS: (a) $\forall u\in R,\forall
v\in{\mathsf{Child}}(u):d(u,v)\leq r$, (b) $\forall u,v\in R:d(u,v)>r$, (c)
The set $\\{{\mathsf{Child}}(u):u\in R\\}$ partitions $U$, and (d)
$\forall{u\in
R},\forall{v\in{\mathsf{Child}}(u)}:\mathsf{cov}(u)\geq\mathsf{cov}(v)$.

######  Lemma 1 (rewording of Lemma 3.4. in [CGK16]).

Let $\mathcal{I}$ be a Robust $2$-NU$k$C instance. If for any fractional
coverages $(\mathsf{cov}_{1}(v),\mathsf{cov}_{2}(v))$ the instance 2-FF
created by Algorithm 2 is valuable, then one obtains an
$(\alpha_{1}+\alpha_{2})$-approximation for $\mathcal{I}$.

Lemma 1 suggests that if we can find fractional coverages so that the
corresponding 2-FF instance $\mathcal{T}$ is valuable, then we are done.
Unfortunately, the example illustrated in Figure 2 shows that for any
$(\alpha_{1},\alpha_{2})$ there exists Robust $2$-NU$k$C instances and
fractional coverages
$(\mathsf{cov}_{1}(v),\mathsf{cov}_{2}(v))\in\mathscr{P}^{\mathcal{I}}_{\mathsf{cov}}$
in the integer hull, for which the CGK algorithm returns 2-FF instances that
are not valuable.

Figure 2: At the top, there is a feasible Robust $2$-NU$k$C instance with
$k_{1}=2$, $k_{2}=3$, and $\mathsf{m}=24$. There are 6 triangles representing
3 collocated points each, along with 12 circles, each representing one point.
The black edges are distance $r_{1}>\alpha_{2}r_{2}$ and the grey edges are
distance $\alpha_{1}r_{1}$. There are two integral solutions $S$ and
$S^{\prime}$ each covering exactly 24 points. $S_{1}=\\{u_{1},u_{4}\\}$,
$S_{2}=\\{u_{2},v_{2},u_{3}\\}$, $S^{\prime}_{1}=\\{u_{2},u_{3}\\}$, and
$S^{\prime}_{2}=\\{u_{1},v_{1},u_{4}\\}$. Having $z_{S}=z_{S^{\prime}}=1/2$ in
$\mathscr{P}^{\mathcal{I}}_{\mathsf{cov}}$, gives $\mathsf{cov}_{1}$ of $1/2$
for all the points and $\mathsf{cov}_{2}$ of $1/2$ for the triangles. The
output of Algorithm 2 is the 2-FF instance at the bottom. According to
Proposition 1 the highlighted nodes have $y=1/2$ and the rest of the nodes
have $y=0$ with objective value $12\times 1/2+18=24$ but no integral solution
can get an objective value of more than 23.

###  2.2 Our Idea

Although the 2-FF instance obtained by Algorithm 2 from fractional coverages
$(\mathsf{cov}_{1}(v),\mathsf{cov}_{2}(v):v\in X)$ may not be valuable,
[CGK16] proved that if these coverages come from (Robust $2$-NU$k$C LP), then
there is always a fractional solution to (2-FF LP) for this instance which has
value at least$\mathsf{m}$.

######  Proposition 1 (rewording of Lemma 3.1. in [CGK16]).

Let $(\mathsf{cov}_{1}(v),\mathsf{cov}_{2}(v):v\in X)$ be any feasible
solution to Robust $2$-NU$k$C LP. As long as $\alpha_{1},\alpha_{2}\geq 2$,
the following is a fractional solution of 2-FF LP with value at least
$\mathsf{m}$ for the 2-FF instance output by Algorithm 2.

$y_{v}=\begin{cases}\mathsf{cov}_{1}(v)&v\in L_{1}\\\
\min\\{\mathsf{cov}_{2}(v),1-\mathsf{cov}_{1}(p(v))\\}&v\in L_{2}.\end{cases}$

Therefore, the problematic instances are precisely 2-FF instances that are
integrality gap examples for (2-FF LP). Our first observation stems from what
Adjiashvili, Baggio, and Zenklusen [ABZ16] call “the narrow integrality gap of
the firefighter LP”.

######  Lemma 2 (From Lemma 6 of [ABZ16]).

Any basic feasible solution $\\{y_{v}:i\in\\{1,2\\},v\in L_{i}\\}$ of the 2-FF
LP polytope has at most 2 _loose_ variables. A variable $y_{v}$ is loose if
$0<y_{v}<1$ and $y_{p(v)}=0$ in case $v\in L_{2}$.

In particular, if $y(L_{1})\leq k_{1}-2$, then the above lemma along with
Proposition 1 implies there exists an integral solution with value $\geq m$.
That is, the 2-FF instance is valuable. Conversely, the fact that the instance
is not valuable asserts that $y(L_{1})>k_{1}-2$ which in turn implies
$\mathsf{cov}_{1}(L_{1})>k_{1}-2$. In English, the fractional coverage puts a
lot of weight on the points in $L_{1}$.

This is where we exploit the ideas in [BIPV19, JSS20, AAKZ20]. By choosing
$\alpha_{1}>2$ to be large enough in Proposition 1, we can ensure that points
in $L_{1}$ are “well-separated”. More precisely, we can ensure for any two
$u,v\in L_{1}$ we have $d(u,v)>\alpha_{1}r_{1}$ (from 2). The well-separated
condition implies that the same center cannot be fractionally covering two
different points in $L_{1}$. Therefore, $\mathsf{cov}_{1}(L_{1})>k_{1}-2$ if
$(\mathsf{cov}_{1},\mathsf{cov}_{2})\in\mathscr{P}^{\mathcal{I}}_{\mathsf{cov}}$
is in the integer hull, then there must exist an integer solution which opens
at most $1$ center that does _not_ cover points in $L_{1}$. For the time being
assume in fact no such center exists and $\mathsf{cov}_{1}(L_{1})=k_{1}$.
Indeed, the integrality gap example in Figure 2 satisfies this equality.

Our last piece of the puzzle is that if the $\mathsf{cov}_{1}$’s are
concentrated on separated points, then indeed we can apply the round-or-cut
framework to obtain an approximation algorithm. To this end, we make the
following definition, and assert the following theorem.

######  Definition 4 (Well-Separated Robust $2$-NU$k$C).

The input is the same as Robust $2$-NU$k$C, along with $Y\subseteq X$ where
$d(u,v)>4r_{1}$ for all pairs $u,v\in Y$, and the algorithm is allowed to open
the radius $r_{1}$-centers only on points in $Y$.

######  Theorem 2.

Given a Well-Separated Robust $2$-NU$k$C instance there is a polynomial time
algorithm using the ellipsoid method that either gives a $4$-approximate
solution, or proves that the instance is infeasible.

We remark the natural (Robust $2$-NU$k$C LP) relaxation still has a bad
integrality gap, and we need the round-or-cut approach. Formally, given
fractional coverages $(\mathsf{cov}_{1},\mathsf{cov}_{2})$ we run Algorithm 2
(with $\alpha_{1}=\alpha_{2}=2$) to get a 2-FF instance. If the instance is
valuable, we are done by Lemma 1. Otherwise, we prove that
$(\mathsf{cov}_{1},\mathsf{cov}_{2})\notin\mathscr{P}^{\mathcal{I}}_{\mathsf{cov}}$
by exhibiting a separating hyperplane. This crucially uses the well-separated-
ness of the instance and indeed, the bad example shown in Figure 2 is not
well-separated. This implies Theorem 2 using the ellipsoid method.

In summary, to prove Theorem 1, we start with
$(\mathsf{cov}_{1},\mathsf{cov}_{2})$ purported to be in
$\mathscr{P}^{\mathcal{I}}_{\mathsf{cov}}$. Our goal is to either get a
constant approximation, or separate $(\mathsf{cov}_{1},\mathsf{cov}_{2})$ from
$\mathscr{P}^{\mathcal{I}}_{\mathsf{cov}}$. We first run the CGK Algorithm 2
with $\alpha_{1}=8$ and $\alpha_{2}=2$. If $\mathsf{cov}_{1}(L_{1})\leq
k_{1}-2$, we can assert that the 2-FF instance is valuable and get a
$10$-approximation. Otherwise, $\mathsf{cov}_{1}(L_{1})>k_{1}-2$, and we guess
the $O(n)$ many possible centers “far away” from $L_{1}$, and obtain that many
well-separated instances. We run the algorithm promised by Theorem 2 on each
of them. If any one of them gives a $4$-approximate solution, then we
immediately get an $8$-approximate111The factor doubles as we need to double
the radius, but that is a technicality. solution to the original instance. If
all of them fail, then we can assert $\mathsf{cov}_{1}(L_{1})\leq k_{1}-2$
must be a valid inequality for $\mathscr{P}^{\mathcal{I}}_{\mathsf{cov}}$, and
thus obtain a hyperplane separating $(\mathsf{cov}_{1},\mathsf{cov}_{2})$ from
$\mathscr{P}^{\mathcal{I}}_{\mathsf{cov}}$. The polynomial running time is
implied by the ellipsoid algorithm. Note that there are two nested runs of the
ellipsoid method in the algorithm. Figure 3 below shows an illustration of the
ideas.

Figure 3: Our framework for approximating Robust $2$-NU$k$C. The three black
arrows each represent separating hyperplanes we feed to the outer ellipsoid.
The box in the bottom row stating “4-approximation for well-separated Robust
$2$-NU$k$C” runs the inner ellipsoid method.

###  2.3 Discussion

Before we move to describing algorithms proving Theorem 2 and Theorem 1, let
us point out why the above set of ideas does not suffice to prove the full CGK
conjecture, that is, give an $O(1)$-approximation for NU$k$C with constant
many type of radii. Given fractional coverages, the CGK algorithm now returns
a $t$-layered firefighter instance and again if such an instance is valuable
(which can be checked in $n^{O(t)}$ time), we get an $O(1)$-approximation. As
above, the main challenge is when the firefighter instance is not valuable.
Theorem 2, in fact, does generalize if all layers are separated. Formally, if
there are $t$ types of radii, and there are $t$ sets $Y_{1},\ldots,Y_{t}$ such
that (a) any two points $p,q\in Y_{i}$ are well-separated, that is,
$d(p,q)>4r_{i}$, and (b) the $r_{i}$-radii centers are only allowed to be
opened in $Y_{i}$, then in fact there is an $O(1)$-approximation for such
instances. Furthermore, if we had fractional coverages
$(\mathsf{cov}_{1},\mathsf{cov}_{2},\ldots,\mathsf{cov}_{t})$ such that in the
$t$-layered firefighter instance returned, all layers have “slack”, that is
$\mathsf{cov}_{i}(L_{i})\leq k_{i}-t$, then one can repeatedly use Lemma 2 to
show that the tree instance is indeed valuable.

The issue we do not know how to circumvent is when some layers have slack and
some layers do not. In particular, even with $3$ kinds of radii, we do not
know how to handle the case when the first layer $L_{1}$ is well-separated and
$\mathsf{cov}_{1}(L_{1})=k_{1}$, but the second layer has slack
$\mathsf{cov}_{2}(L_{2})\leq k_{2}-3$. Lemma 2 does not help since all the
loose vertices may be in $L_{1}$, but they cannot all be picked without
violating the budget. At the same time, we do not know how to separate such
$\mathsf{cov}$’s, or whether such a situation arises when $\mathsf{cov}$’s are
in the integer hull. We believe one needs more ideas to resolve the CGK
conjecture.

##  3 Approximating Well-Separated Robust $2$-NU$k$C

In this section we prove Theorem 2 stated in Section 2.2. As mentioned there,
the main idea is to run the round-or-cut method, and in particular use ideas
from a previous paper [CN18] of ours. The main technical lemma is the
following.

######  Lemma 3.

Given Well-Separated Robust $2$-NU$k$C instance $\mathcal{I}$ and fractional
coverages $(\hat{\mathsf{cov}}_{1}(v),\hat{\mathsf{cov}}_{2}(v))$, if the
output of the CGK Algorithm 2 is not valuable, there is a hyperplane
separating $(\hat{\mathsf{cov}}_{1}(v),\hat{\mathsf{cov}}_{2}(v))$ from
$\mathscr{P}^{\mathcal{I}}_{\mathsf{cov}}$. Furthermore, the coefficients of
this hyperplane are bounded in value by $|X|$.


#  A Note on Over- and Under-Representation Among
Populations with Normally-Distributed Traits

Ronald F. Fox and Theodore P. Hill

###### Abstract

Among several subpopulations of a given species with a normally-distributed
trait, such as height, blood pressure, or various test scores in humans, one
and only one of the subpopulations will always strongly dominate all the
others in the right tail, that is, in the high-end values of that trait.
Examples are given to show that this is not true in general for other common
classes of continuous centrally-symmetric unimodal distributions such as
Laplace, nor even for other bell-shaped distributions such as Cauchy.

##  1 Introduction

The issue of over- and under-representation of various factions of our society
in various roles has become a multi-billion dollar business (e.g., Anand and
Winters, 2018). A standard assumption by experts is that many of the crucial
traits in these roles have approximately normal (Gaussian) distributions
(Feingold, 1995; Roser et al., 2019). The goal of this short note is to
present some basic but perhaps surprising properties of normal distributions
that are particularly pertinent to questions of over- and under-representation
in the tails. These properties, although not unique to normal distributions,
are not shared by other common continuous centrally-symmetric unimodal
distributions, even by other bell-shaped distributions such as classical
Cauchy (Lorentz) distributions. In particular, among a finite number of
different normal distributions, there will always be one, and only one, that
not only is over-represented in the right tail, but even becomes increasingly
over-represented among all other subpopulations in the rightmost tails.

##  2 Normal Distributions in Population Studies

When population research studies report only the means and standard deviations
of their results, the default scientific understanding is that the data are
approximately normally distributed, i.e., the distributions in question are
close to normal (Gaussian) distributions. For example, if a research study
reports that their data has average value 2 and standard deviation 1, then the
understanding is that the original dataset looks like the diagram in Figure
1(left) with $m=2$ and $s=1$, not like the somewhat similar distribution in
Figure 1(right). The underlying theoretical basis for the assumption of
normality in most cases is the remarkable Central Limit Theorem, which says
that if the results of independent repetitions of any experiment are added,
the empirical distribution always approaches a normal distribution.

Two concrete examples among human populations are height and test scores such
as those in the College Board Scholastic Aptitude Test (SAT). There are
enormous amounts of data on human height, which is essentially continuous and
is very close to being normally distributed (Roser et al., 2019, p. 24).
Scores on the SAT, on the other hand, are originally discrete but the
distribution “obtained from a continuized, smoothed frequency distribution of
original SAT scores” is a linear transformation of a normal distribution
(Dorans, 2002, p. 59). Thus, since all linear transformations of normal
distributions are normal, for all practical purposes the resulting SAT scores
have normal distributions.

The appropriateness of assuming a normal distribution to given data is often
tested using the well-known empirical observation called the “68%-95%-97.7%
rule” of normality. As is illustrated in Figure 1(left), in every normal
distribution, no matter what the mean and standard deviation (positive square
root of variance) are, about 68% of the values are within one standard
deviation of the mean, about 95% within two standard deviations, and about
97.7% within three (the exact values are irrational numbers, but easily
approximated to any desirable degree of accuracy). The one key property of a
continuous centrally-symmetric unimodal distribution that makes it normal is
the unique (after rescaling) rate of decrease of its density function away
from its mean. The normal density function, discovered by Gauss in 1809 in
connection with his studies of astronomical observation errors, decreases from
its mean at a rate exactly proportional to $e^{-x^{2}}$, not to $e^{-x}$ or
$x^{-2}$, for example, as is the case for the Laplace and Cauchy
distributions, respectively.

The Cauchy distribution, for instance, which sees widespread application in
physics, also has a continuous centrally-symmetric unimodal bell-shaped
density like the normal distribution, but the Cauchy distribution has an
undefined mean and variance and has a different rate of decrease from the
median that satisfies a different empirical rule. Figure 1(right) illustrates
the corresponding 50%-70%-79.5% empirical rule for Cauchy distributions -
exactly 50% of the values are within one scale parameter (distance from median
to inflection point of the density curve), and about 70% within two and 79.5%
within three scale parameters. Thus it is easy in practice to distinguish
between these two similar-looking common bell-shaped distributions.

Figure 1: Universal empirical rules for all normal (left) and Cauchy (right)
distributions. Here $m$ represents the median, and $s$ represents the distance
(called standard deviation for normal distributions, scale parameter for
Cauchy) from $m$ to the inflection point. Note that the tails of the normal
distribution drop off much more rapidly than those of the Cauchy; for example,
the proportion of a normal distribution that is more than 5s ( 5 standard
deviations) out in the right tail is about 6 in a million, whereas for a
Cauchy it is about 6 in a hundred.

It is easy to see that the density functions of every two different normal
distributions intersect either in exactly one or in exactly two distinct
points. Thus the density function of one of those two distributions is
strictly larger than that of the other at all points greater than the larger
of the two intersection points (or the unique one, if there is only one).
This, in turn, implies that the proportion of that distribution is strictly
larger than that of the other distribution from that point on, and thus that
this distribution will be over-represented in the right tail. In fact, much
stronger conclusions hold, and it is the goal of this note to present a few of
these. First, however, as will be seen in the next proposition, these points
of intersection are easily obtained explicitly, and are recorded here for
convenience; the proof follows from basic algebra.

######  Proposition 2.1.

The density functions of two different normal distributions, with means
$m_{1}$ and $m_{2}$ and positive standard deviations $\sigma_{1}$ and
$\sigma_{2}$, respectively, intersect at exactly one point if
$\sigma_{1}=\sigma_{2}$, namely at $x=\frac{m_{1}+m_{2}}{2}$; and otherwise
intersect at exactly two points

$x_{1,2}=\frac{\sigma^{2}_{1}m_{2}-\sigma^{2}_{2}m_{1}\pm\sigma_{1}\sigma_{2}\sqrt{(m_{1}-m_{2})^{2}+(\sigma^{2}_{1}-\sigma^{2}_{2})(\log\sigma^{2}_{1}-\log\sigma^{2}_{2})}}{\sigma^{2}_{1}-\sigma^{2}_{2}}\mbox{
if }\sigma_{1}\neq\sigma_{2}.$

N.B. For brevity, the standard notation $N(m,\sigma^{2})$ will be used
throughout this note to denote a normal distribution with mean $m$ and
standard deviation $\sigma>0$.

######  Example 2.2.

  1. (i)

Let $P_{1}\sim N(100,10^{2})$ and $P_{2}\sim N(110,10^{2})$. By Proposition
2.1, the unique crossing point of the density functions of $P_{1}$ and $P_{2}$
is at $x=105$, which implies that the proportion of $P_{2}$ that is above any
cutoff $c>105$ is greater than the proportion of $P_{1}$ above $c$.
Conversely, the proportion of $P_{1}$ below any $c<105$ is greater than the
proportion of $P_{2}$ below $c$.

  2. (ii)

Let $P_{1}\sim N(100,10^{2})$, and $P_{2}\sim N(101,11^{2})$. By Proposition
2.1, the two crossing points of the density functions of $P_{1}$ and $P_{2}$
are at $x_{1}\cong 83.52$ and $x_{2}\cong 106.95$, which implies that the
proportion of $P_{2}$ that is above any cutoff $c>x_{2}$ is greater than the
proportion of $P_{1}$ above $c$. (Similarly, in this case, $P_{2}$ also
dominates $P_{1}$ in the lower tail in that the proportion of $P_{2}$ that is
below any cutoff $c<x_{1}$ is greater than the proportion of $P_{1}$ below
$c$).

##  3 Right-Tail Dominance

As was seen in Proposition 2.1 and illustrated in Example 2.2, given any two
different normal distributions, one of them necessarily dominates the other in
the right tail. A much stronger conclusion is true, and that is the purpose of
this section. Similar conclusions follow about the left tails, of course, but
the emphasis here on the right tails is simply because in practice it is the
right tails that receive the most attention - the best athletes and
mathematicians, for example, not the worst, which are rarely identified.

Recall that a probability measure $P$ on the real line is uniquely determined
by its complementary cumulative distribution function (ccdf) $\bar{F_{P}}$,
defined by $\bar{F_{P}}(x)=P((x,\infty))$ for all $x\in\mathbb{R}$.
($\bar{F}_{P}$ is also often called the survival function of $P$, since
$\bar{F}_{P}(c)$ represents the $P$-probability of the set above the cutoff
theshold $c$, i.e., the fraction that survives when all values less than or
equal to $c$ are removed.)

######  Definition 3.1.

A probability distribution $P_{1}$ strongly dominates distribution $P_{2}$ in
the right tail if

$\lim_{c\to\infty}\frac{\bar{F}_{P_{1}}(c)}{\bar{F}_{P_{1}}(c)+\bar{F}_{P_{2}}(c)}=1,$

that is, if the relative proportion of $P_{1}$ in the right tail compared to
that of $P_{2}$ in the right tail approaches 100% as the cutoff threshold $c$
gets arbitrarily large.

Recall that a continuous (absolutely continuous) probability distribution $P$
is uniquely determined by its probability density function
$f_{P}:\mathbb{R}\to[0,\infty)$ via $P((a,b))=\int_{a}^{b}f_{P}(x)dx$, so in
particular, $\bar{F_{P}}(c)=\int_{c}^{\infty}f_{P}(x)dx$. The next lemma
records a simple relationship between the quotients of probability density
functions (pdf’s) and the quotients of the corresponding ccdf’s, and will be
used in several examples and proofs below.

######  Lemma 3.2.

Suppose $P_{1}$ and $P_{2}$ are continuous probability distributions with
strictly positive pdf’s $f_{1}$ and $f_{2}$ and with ccdf’s $\bar{F}_{1}$ and
$\bar{F}_{2}$, respectively. If
$\lim_{x\to\infty}{f_{1}(x)}/{f_{2}(x)}=\alpha>0$, then
$\lim_{c\to\infty}{\bar{F}_{1}(c)}/{\bar{F}_{2}(c))}=\alpha$.

###### Proof.

Straightforward from the definition of density functions and from the
linearity and order-preserving properties of integration. ∎

######  Example 3.3.

  1. (i)

Let $P_{1}$ and $P_{2}$ be Cauchy distributions with medians $m_{1}=0$ and
$m_{2}=0.5$ and scale parameters $s_{1}=1$ and $s_{2}=0.5$, respectively. Then
by Lemma 3.2,

$\lim_{x\to\infty}\frac{f_{x_{1}}(x)}{f_{x_{2}}(x)}=\lim_{x\to\infty}\frac{\pi(1+2x^{2}-2x)}{\pi(1+x^{2})}=2=\lim_{c\to\infty}\frac{\overline{F}_{x_{1}}(c)}{\overline{F}_{x_{2}}(c)},$

which implies that, as $c\to\infty$, the $P_{1}$-probability of the set of
numbers greater than $c$ approaches exactly twice the $P_{2}$-probability of
numbers greater than $c$. Thus $P_{1}$ dominates $P_{2}$ in the right tail,
but does not strongly dominate $P_{2}$ in the right tail.

  2. (ii)

Let $P_{1}$ and $P_{2}$ be Laplace distributions with medians $m_{1}=1$ and
$m_{2}=0$ and scale parameters $s_{1}=s_{2}=1$, respectively. Then

$\lim_{c\to\infty}\frac{\bar{F}_{P_{1}}(c)}{\bar{F}_{P_{2}}(c)}=\lim_{c\to\infty}\frac{e^{1-c}}{e^{-c}}=e,$

so neither $P_{1}$ nor $P_{2}$ strongly dominates the other in the right tail.

  3. (iii)

Let $P_{1}$ and $P_{2}$ be Laplace distributions with medians $m_{1}=m_{2}=0$
and scale parameters $s_{1}=1$ and $s_{2}=0.5$, respectively. Then $P_{1}$
strongly dominates $P_{2}$ in the right tail since

$\lim_{c\to\infty}\frac{\bar{F}_{P_{1}}(c)}{\bar{F}_{P_{1}}(c)+\bar{F}_{P_{2}}(c)}=\lim_{c\to\infty}\frac{e^{-c}}{e^{-c}+e^{-2c}}=1.$

  4. (iv)

Let $P_{1}$ and $P_{2}$ be normal distributions with identical variances $+1$,
and with means 1 and 0, respectively. Then the density functions
$f_{P_{1}}(x)=\frac{1}{\sqrt{2\pi}}e^{-{\frac{1}{2}}(x-1)^{2}}$ and
$f_{P_{2}}(x)=\frac{1}{\sqrt{2\pi}}e^{-{\frac{1}{2}}x^{2}}$ for $P_{1}$ and
$P_{2}$ satisfy $\frac{f_{P_{1}}(x)}{f_{P_{2}}(x)}=e^{x-{1/2}}\to\infty$ as
$x\to\infty$, so by Lemma 3.2, $P_{1}$ strongly dominates $P_{2}$ in the right
tail.

As was seen in Example 3.3, for two given different Cauchy distributions or
two different Laplace distributions, neither distribution may strongly
dominate the other in the right tail. This is in sharp contrast to the main
conclusions in this note, where it will be shown that given any finite number
of different normal distributions, there is always a unique one of those
distributions that strongly dominates every one of the other distributions in
the right tail. The next theorem, the key step in this conclusion, follows
easily from elementary basics of normal distributions; since the authors know
of no explicit reference to these conclusions, a proof is included.

######  Theorem 3.4.

Let $P_{1}$ and $P_{2}$ be different normal distributions. Then

  1. (i)

either $P_{1}$ strongly dominates $P_{2}$ in the right tail or $P_{2}$
strongly dominates $P_{1}$ in the right tail;

  2. (ii)

if $P_{1}$ strongly dominates $P_{2}$ in the right tail, then either $P_{1}$
has greater mean (average value) than $P_{2}$ or $P_{1}$ has greater variance
than $P_{2}$, or both;

  3. (iii)

if $P_{1}$ has greater variance than $P_{2}$, then $P_{1}$ strongly dominates
$P_{2}$ in both right and left tails, independent of the means.

###### Proof.

Suppose that $P_{1}\sim N(m,\sigma_{1}^{2})$ and $P_{2}\sim
N(m,\sigma_{2}^{2})$ are normal distributions with pdf’s $f_{1}$ and $f_{2}$,
respectively. Since $P_{1}$ and $P_{2}$ are different, either
${\sigma_{1}}\neq{\sigma_{2}}$, or ${\sigma_{1}}={\sigma_{2}}$ and $m_{1}\neq
m_{2}$.

Case 1. $\sigma_{1}\neq\sigma_{2}$. Without loss of generality,
$\sigma_{1}>\sigma_{2}=1$. Then

(3.1) $\displaystyle\frac{f{{}_{1}}(x)}{f{{}_{2}}(x)}$
$\displaystyle=\frac{\sqrt{2\pi}}{\sigma_{1}\sqrt{2\pi}}\exp\left(\frac{-(x-m_{1})^{2}}{2{\sigma_{1}}^{2}}+\frac{(x-m_{2})^{2}}{2}\right)$
$\displaystyle=\frac{1}{\sigma_{1}}\exp\left(\frac{x^{2}}{2}\left(1-\frac{1}{{\sigma_{1}}^{2}}\right)+x\left(\frac{m_{1}}{{\sigma_{1}}^{2}}-m_{2}\right)+\left(\frac{{m_{1}}^{2}}{2}-\frac{{m_{1}}^{2}}{2{\sigma_{1}}^{2}}\right)\right).$

Since $\sigma_{1}^{2}>1$, $(1-\frac{1}{\sigma_{1}^{2}})>0$, so (3.1) implies
that $\lim_{x\to\infty}\frac{f{{}_{1}}(x)}{f{{}_{2}}(x)}=\infty$, and thus by
Lemma 3.2, $P_{1}$ strongly dominates $P_{2}$ in the right tail.

Case 2. ${\sigma_{1}}^{2}={\sigma_{2}}^{2}$ and $m_{1}\neq m_{2}$. Without
loss of generality, $\sigma_{1}=\sigma_{2}=1$. Then

(3.2) $\displaystyle\frac{f{{}_{1}}(x)}{f{{}_{2}}(x)}$
$\displaystyle=\exp\left(\frac{-x^{2}+2m{{}_{1}}x-{m_{1}}^{2}+x^{2}-2m{{}_{2}}x+{m_{2}}^{2}}{2}\right)$
$\displaystyle=\exp\left((m_{1}-m_{2})x+\frac{({m_{2}}^{2}-{m_{1}}^{2})}{2}\right).$

Also without loss of generality, $m_{1}>m_{2}$, in which case (3.2) implies,
via Lemma 3.2 as in Case 1, that $P_{1}$ strongly dominates $P_{2}$ in the
right tail. This concludes the proof of (i); the proofs of (ii) and (iii)
follow similarly. ∎

######  Corollary 3.5.

Given a finite number of different normal distributions $P_{1},\ldots,P_{n}$,
there is one and only one distribution that strongly dominates all the others
in the right tail.

###### Proof.

For each $i\in\\{1,\ldots,n\\}$, let normal distributions $P_{i}$ have mean
$m_{i}$ and standard deviation $\sigma_{i}$. Since the distributions are all
different,

(3.3) $m_{i}=m_{j}\,\mbox{ and }\sigma_{i}=\sigma_{j}\,\mbox{ implies }i=j,$

which implies that there exists a unique $i^{*}\in\\{1,\ldots,n\\}$ such that
$m_{i^{*}}=\max\\{m_{j}:\sigma_{j}=\max\\{\sigma_{1},\ldots,\sigma_{n}\\}\\}$.
By Theorem 3.4, $P_{i^{*}}$ strongly dominates $P_{i}$ in the right tail for
all $i\neq i^{*}$. ∎

Figure 2: Feingold’s “Hypothetical superimposed male and female distributional
curves for three comparisons between the sexes” (Feingold, 1995, p. 7). Note
the strong dominance in the right tail of the M subpopulation. Note also that
the case where M has smaller mean and larger variance is missing, and this is
illustrated in Figure 3(left).

As was seen in Theorem 3.4, if $P_{1}$ has either greater variance than
$P_{2}$, or the same variance and higher mean, then $P_{1}$ will strongly
dominate $P_{2}$ in the right tail. Moreoever, as pointed out by Feingold,
“Most important, what might appear to be trivial group differences in both
variability and central tendency can cumulate to yield very appreciable
differences between the groups in numbers of extreme scorers” (Feingold, 1995,
p. 11). The next example, a slight modification of the numerical example
suggested by Feingold, illustrates this observation with two normal
distributions that are close in mean value (100 vs. 101) and in standard
deviation (10 vs. 11).

######  Example 3.6.

Suppose a population $X$ consists of two mutually exclusive subpopulations
$X_{1}$ and $X_{2}$, where the values of a given trait are normally
distributed with distributions $P_{1}$ and $P_{2}$ as in Example 2.2(ii), as
shown in Figure 3(center). Assuming an equal number of each group in the
overall population $X$, routine calculations with standard erf function
programs and Newton’s method yield that among the top one tenth of 1% of the
combined population, approximately 82% of the individuals will be type
$X_{2}$. (To put this in perspective, 0.1% of the current population of India
is more than 1.3 million people.)

Figure 3: Comparisons of the density functions of two different normal
distributions. The graph on the left complements Feingold’s illustration in
Figure 2 above, and illustrates how even a distribution with smaller mean will
eventually dominate in the right tail if its variance is larger. The graph on
the right illustrates the situation in Examples 2.2 and 3.6, with the blue
(solid) curve having mean 100 and standard deviation 10, and the red (dotted)
curve with mean 101 and standard deviation 11, showing how even small
increases in means and standard deviations can result in significant
differences in the (right) tail.

##  4 Over-Representation in the Right Tail

Whether a particular subpopulation is over-represented or under-represented
among the other subpopulations with respect to a given trait depends on the
relative size of that subpopulation with that trait compared to the size of
the whole population with that trait. For example, if subpopulation $X_{1}$
comprises 30% of the total population, but comprises 40% of the population
with trait values above a given cutoff $c$, then $X_{1}$ is over-represented
in the portion of the total population with values greater than $c$. The goal
of this section is to record a simple consequence of Corollary 3.5 that has a
much stronger conclusion than simple over-representation in the case of normal
distributions.

######  Definition 4.1.

If a population $X=\bigcup_{i=1}^{n}X_{i}$ consists of $n$ mutually exclusive
(disjoint) subpopulations $X_{1},\ldots,X_{n}$ with probability distributions
(for a given trait) $P_{1},\ldots,P_{n}$, respectively, then subpopulation
$X_{i^{*}}$ is strongly overrepresented in the right tail of $X$ if, for all
possible subpopulation sizes, the proportion of individuals in subpopulation
$X_{i}$ with trait values above a cutoff $c$ approaches 100% as $c\to\infty$,
that is, if

(4.1)
$\lim_{c\to\infty}\frac{S_{i^{*}}\bar{F}_{i^{*}}(c)}{\sum\limits_{i=1}^{n}S_{i}\bar{F}_{i}(c)}=1\quad\mbox{for
all strictly positive subpopulation sizes }S_{1},\ldots,S_{n}.$

######  Theorem 4.2.

Let $X=\bigcup_{i=1}^{n}X_{i}$, where $X_{1},\ldots,X_{n}$ are mutually
disjoint with different normal distributions for a given trait. Then there
exists a unique $i^{*}\in\\{1,\ldots,n\\}$ such that $X_{i^{*}}$ is strongly
overrepresented in the right tail of $X$ for that trait.

###### Proof.

Immediate from Corollary 3.5 and the definitions of strongly dominated and
strongly overrepresented. ∎

In real life examples, of course, there are no variables that are exactly
normally distributed, since the normal distribution is continuous, and the
numbers of people in various categories, for example, is necessarily finite.
But if distributions are close to being normally distributed, the right-tail
over-representation predicted by Theorem 4.2 is reasonable to expect.
Similarly, in real-life examples, calculations involving tails that are 6 or 7
standard deviations out involve probabilities of less than one in 10 billion,
and are meaningless among the current human population of this planet.

######  Example 4.3.

The College Board SAT scores of males and females are usually assumed (or
designed) to be approximately normally distributed (Dorans, 2002). Unless the
distributions are identical, Theorem 4.2 implies that exactly one of those two
genders must be strongly over-represented in the right tail, and that this
over-representation will increase as the score range increases; Figure 4
illustrates this with actual College Board SAT statistics.

Figure 4: Statistics for nearly two million students for the 2016 Edition of
the Scholastic Aptitude Test (SAT), with breakdown by gender and score ranges
(Sawyer, 2017). Note that the proportions of males in various score ranges
increase as the score range increases in the upper (right) tail. About 10%
more females participated than males, which is reflected in the Adjusted
Male/Female Ratios.

##  5 Mean vs. Variance

As predicted by Theorem 4.2, if the SAT scores of males and females are
approximately normally distributed then necessarily one of the two genders
must strongly dominate the other in the right tail. In this case, Figure 4
indicates that it happens to be males who are increasingly over-represented in
the high SAT scores. By Theorem 3.4(ii), this would mean that males either
have higher average SAT scores, or have higher variance in their SAT scores,
or both. Another look at Figure 4 shows that males are also over-represented
in the lower score ranges, and that this over-representation of males also
increases as the score range decreases, which suggests that males have higher
variance in SAT scores.

Greater variability of males than females was observed by Charles Darwin for
many species and traits throughout the animal kingdom, and as variability
expert psychologist Stephanie Shields observed about 19th century studies,
“The biological evidence overwhelmingly favored males as the more variable sex
…[and] Darwin originally suggested greater male variability as a tentative
hypothesis but later stated it as a fact” (Shields, 1982, emphasis added).
Similarly, extensive recent research has generally also supported Darwin’s
conclusion – for example, (Hill, 2018, Appendix A) surveys research findings
on gender differences in variability since 2000, including the first evidence
of greater male variability in cognitive traits in non-human and even non-
mammalian species (e.g., Branch et al., 2020; DeCasien et al., 2020).

As noted by inter- and intrasex variability experts Anne-Catherine Lehre and
colleagues, “In contrast to mean values, differences in variability are more
politically sensitive because they have the consequence (given similar mean
values) that the more variable sex will have a higher representation at the
extremes relative to the less variable sex” (Lehre et al., 2009). Similarly,
cognitive ability experts Rosalind Arden and Robert Plomin observed that “a
small difference in variance may have consequences at the extremes of ability
resulting in visibly unequal numbers of one sex among the less able or among
the elite” (Arden and Plomin, 2006). Theorem 3.4(iii) perhaps helps explain
this statistically in the case of normally-distributed traits, since a
distribution with higher variance will always be strongly over-represented in
both tails, whether or not its mean is larger or smaller than that of the
other gender’s distribution.

## References

  * Anand and Winters (2018) Anand, Rohini and Winters, Mary-Frances.  “A Retrospective View of Corporate Diversity Training From 1964 to the Present.”  _Academy of Management Learning & Education_ 7.3 (2018): 356–372.  Doi:10.5465/AMLE.2008.34251673.
  * Arden and Plomin (2006) Arden, Rosalind and Plomin, Robert.  “Sex differences in variance of intelligence across childhood.”  _Personality and Individual Differences_ 41: 39–48.  Doi:10.1016/j.paid.2005.11.027.
  * Branch et al. (2020) Branch, Carrie L., Sonnenberg, Benjamin R., Pitera, Angela M., Benedict, Lauren M., Kozlovsky, Dovid Y., Bridge, Eli S., and Pravosudov, Vladimir V.  “Testing the greater male variability phenomenon: male mountain chickadees exhibit larger variation in reversal learning performance compared with females.”  _Proceedings of the Royal Society B_ 287: 20200895.  Doi:10.1098/rspb.2020.0895.
  * DeCasien et al. (2020) DeCasien, Alex R., Sherwood, Chet C., Schapiro, Steven J., and Higham, James P.  “Greater variability in chimpanzee (Pan troglodytes) brain structure among males.”  _Proceedings of the Royal Society B_ 287: 20192858.  Doi:10.1098/rspb.2019.2858.
  * Dorans (2002) Dorans, Neil J.  “Recentering and Realigning the SAT Score Distributions: How and Why.”  _Journal of Educational Measurement_ 39.1 (2002): 59–84.
  * Feingold (1995) Feingold, Alan.  “The additive effects of differences in central tendency and variability are important in comparisons between groups.”  _American Psychologist_ 50.1 (1995): 5–13.  Doi:10.1037/0003-066X.50.1.5.
  * Hill (2018) Hill, Theodore P.  “An evolutionary theory for the variability hypothesis.”  2018\.  Preprint, arXiv:1703.04184v4 [q-bio.PE]. URL https://arxiv.org/abs/1703.04184
  * Lehre et al. (2009) Lehre, Anne-Catherine, Lehre, Knut, Laake, Petter, and Danbolt, Niels.  “Greater intrasex phenotype variability in males than in females is a fundamental aspect of the gender differences in humans.”  _Developmental Psychobiology_ 51: 198–206.  Doi:10.1002/dev.20358.
  * Roser et al. (2019) Roser, Max, Appel, Cameron, and Ritchie, Hannah.  “Human Height.”  https://ourworldindata.org/human-height, 2019.  Last accessed January 22, 2021.
  * Sawyer (2017) Sawyer, Art.  “How the New SAT has Disadvantaged Female Testers.”  https://www.compassprep.com/new-sat-has-disadvantaged-female-testers/, 2017\.  Last accessed January 15, 2021.
  * Shields (1982) Shields, Stephanie A.  “The Variability Hypothesis: The History of a Biological Model of Sex Differences in Intelligence.”  _Signs_ 7.4 (1982): 769–797.