# Improving Efficiency and Equality in School Choice111 We thank the anonymous
referees of the MATCH-UP 2022 workshop (where a preliminary version of this
paper was accepted) for their valuable suggestions. We also acknowledge
helpful comments from Mustafa Afacan, David Delacrétaz, Aytek Erdil, Yoan
Hermstrüwer, Peter Kosinar, Jörgen Kratz, Aditya Kuvalekar, Vincent Meisner,
Antonio Miralles, Hervé Moulin, Afshin Nikzad, Robert Parviainen, Juan
Sebastián Pereyra, Erel Segal-Halevi, Olivier Tercieux, Vivien Tisserand,
Peter Troyan, Bertan Turhan, Utku Ünver, Mark Wilson, Gabriel Ziegler, and
audiences at the Belfast Easter Workshop on School Choice, the Conference on
Economic Design, the Coalition Theory Network Workshop, and the ISER Essex
research seminar. We thank Sarah Fox and Taylor Knipe for proofreading this
paper. We acknowledge funding from the ESRC and the Leibniz Association as
part of project K125/2018: Improving school admissions for diversity and
better learning outcomes. Supplementary materials are available at
www.josueortega.com.

Josué Ortega<EMAIL_ADDRESS>(corresponding author). Thilo Klein  Queen’s
University Belfast, UK.  ZEW – Leibniz Centre for European Economic Research,
Mannheim, Germany.  Pforzheim University, Germany.

###### Abstract

How should students be assigned to schools? Two mechanisms have been suggested
and implemented around the world: deferred acceptance (DA) and top trading
cycles (TTC). These two mechanisms are widely considered excellent choices
owing to their outstanding stability and incentive properties. We show
theoretically and empirically that both mechanisms perform poorly with regard
to two key desiderata such as efficiency and equality, even in large markets.
In contrast, the rank-minimizing mechanism (RM) is significantly more
efficient and egalitarian. It is also Pareto optimal for the students, unlike
DA, and generates less justified envy than TTC.

###### keywords:

school choice , inequality , efficiency , justified envy.
JEL Codes: C78, D73.

††journal:

##  1 Introduction

School choice is a common way to assign students to schools based on the
students’ and schools’ preferences. Students and schools rank their potential
matches and submit this information to a centralized clearinghouse.
Afterwards, an algorithm (also known as a mechanism) is applied to the
submitted data and an allocation of students to schools is generated.

But which mechanism should we use to assign students to schools? Che and
Tercieux (2018) convincingly argue that: “the selection must be based on some
measure of aggregate welfare of participants. For instance, if one Pareto
efficient mechanism yields a significantly higher utilitarian welfare level or
a much more equal payoff distribution than others, that would constitute an
important rationale for favoring such a mechanism”.

We show that the mechanism that minimizes the sum of ranks for the students
(henceforth RM, Featherstone, 2020) outperforms two of the most popular
mechanisms used in school choice with respect to the two desiderata named
above, i.e. utilitarian welfare and equality. RM is superior to Gale’s and
Shapley’s deferred acceptance (DA) mechanism and to Gale’s top trading cycles
(TTC) mechanism in that: i) RM assigns the average student to a school they
prefer more (i.e. it is more efficient), and ii) RM assigns the worst-off
student to a school that they prefer _much_ more (i.e. it is more
egalitarian).

In particular, if there are $n$ students and $n$ schools with one seat each,
and preferences for both sides are drawn uniformly at random, TTC and DA
asymptotically assign the average student to approximately their $\log(n)$
most preferred school, whereas RM assigns them to a school better than their
second choice. If we focus on the worst placement, rather than the average,
the difference is even bigger: RM assigns them to their $\log_{2}(n)$ most
preferred school, whereas DA assigns them to their $\log^{2}(n)$ and TTC to a
school in the bottom half of their rank list (see Fig. 1 for the rank
distribution). In addition, because all Pareto optimal and strategy proof
mechanisms are equivalent (TTC and serial random dictatorship included), our
results show that requiring strategy-proofness in school choice mechanisms can
significantly hurt efficiency and equality.

Furthermore, RM is Pareto optimal for the students, unlike DA, and generates
justified envy for fewer students than TTC, which is surprising because RM
does not use schools’ priorities but TTC does. We prove these properties for
random markets where preferences are drawn independently and uniformly at
random (see Table 1), and document them by analyzing real data from the
student assignment system in Budapest (see Fig. 2).

Figure 1: Rounded average rank distribution in 1,000 random markets with $n=100$. Preferences are drawn independently and uniformly at random. The x-axis is truncated at the highest value with positive density. See Appendix B for details. Figure 2: Rank distribution generated for 10,131 students in the secondary school admissions in Budapest. The maximum rank is 244. See Section 5 for details. Table 1: Theoretical properties of school choice mechanisms in large random markets. | RM | TTC | DA
---|---|---|---
Average rank | $\leq 2$ | $\log(n)$ | $\log(n)$
Maximum rank | $\log_{2}(n)$ | $>0.5\,n$ | $\log^{2}(n)$
Students w. justified envy | $0.33\,n$ | $0.39\,n$ | 0
Pareto optimal | Yes | Yes | No
Strategy-proof | No | Yes | Yes

##  2 Related Literature

The question of which mechanism should be used to assign students to schools
has been frequently asked in the market design literature. So far, the answer
to this question has been that it does not matter which mechanism is chosen,
for all frequently used mechanisms are equivalent in terms of rank
distribution. This equivalence has been established theoretically for a wide
class of mechanisms (Pycia, 2019; Che and Tercieux, 2018) and empirically
using real-life data (Abdulkadiroğlu et al., 2009; Pathak and Sönmez, 2013;
Che and Tercieux, 2018; Abdulkadiroğlu et al., 2020).111Many equivalence
results are also available for one-sided matching markets, e.g. Che and Kojima
(2010), Carroll (2014), Liu and Pycia (2016). Our paper challenges the
literature consensus by showing that Pareto optimal mechanisms are not
equivalent, as can be observed in Figs. 1 and 2.222A two-sample Kolmogorov-
Smirnov test rejects the null-hypothesis that any two distributions in Figures
1 or 2 are the same at the 1% significance level. Three reasons explain the
discrepancy between our results and those in the literature, namely i)
different model specifications, ii) we consider non-strategy proof mechanisms,
like RM, and iii) RM has not been used in empirical studies. We explain these
differences in detail below.

Of the aforementioned articles, Che and Tercieux (2018) is the closest paper
to ours. Using a random market approach, in which preferences have both a
correlated and an uncorrelated component and where agents’ preferences are
bounded, they show that the _normalized_ payoff distribution generated by any
Pareto optimal mechanism converges to the best possible one in large markets.
Furthermore, they compare the rank distribution generated by DA and TTC (but
not RM) using data from the New York City school choice program. The main
lesson from their paper is that all Pareto optimal mechanisms are equivalent
in large markets, and therefore there is no reason to prefer any Pareto
optimal mechanism over another.333See also Theorem 1 in Che and Tercieux
(2019). Our paper shows that the payoff equivalence between Pareto optimal
mechanisms breaks down once i) ranks are used instead of normalized payoffs,
and ii) students rank all available schools, rather than just a few.

Pycia (2019) obtains a similar equivalence result to that of Che and Tercieux:
he shows that any anonymous statistics, such as rank distribution, generated
by Pareto efficient and strategy-proof mechanisms are equivalent (note that RM
is not strategy-proof). This implies that all of our results for TTC’s poor
performance with regards to efficiency and equality also apply to the random
serial dictatorship mechanism (RSD), which “has a long history and is used in
a wide variety of practical allocation problems, including school choice,
worker assignment, course allocation, and the allocation of public housing”
(Pycia and Troyan, 2021). Manea (2009) shows that the number of preferences
profiles for which the random serial dictatorship mechanism is ordinally
efficient (and thus rank efficient) vanishes when the number of agents grows.
Our result complement his by showing that RSD (and TTC) not only rarely
produces a rank efficient allocation, but also the size of its inefficiency
does not vanish in large markets.

To show that RM is more efficient than DA and TTC, we connect the school
choice problem to that of assigning one of $n$ jobs to each of $n$ workers so
to minimize costs.444A large literature in mathematics, uncited in economics,
has studied this problem. See Olin (1992) and Krokhmal and Pardalos (2009) for
a summary of it. Worker $i$ incurs a cost $c_{ij}$ when completing job $j$.
The matrix $C$ contains all such costs. When each row of $C$ is an independent
random permutation of $\\{1,\ldots,n\\}$, this problem is equivalent to that
of finding the rank-minimizing allocation of students to schools, ignoring
schools’ priorities. Each entry $c_{ij}$ denotes the rank (cost) of school
(job) $j$ for student (worker) $i$. To show that the RM is more efficient than
TTC and DA, we invoke a result in Parviainen (2004) which shows that the cost-
minimizing allocation has an average cost smaller than 2, and compare it with
the well-known average rank in TTC and DM, which is around $\log(n)$.
Obtaining the maximum rank lower bound and the fraction of students with
justified envy is easy using the limit distribution of ranks in RM, which is
also provided by Parviainen.

The result of average rank being bounded by 2 in RM was recently independently
discovered by Nikzad (2022). His proof uses random graph arguments and is
different (and significantly more involved) than ours. Sethuraman (2022) shows
that Nikzad’s result can be proved using the cost assignment problem with
costs distributed in $(0,1)$ (Aldous, 2001), without using Parviainen’s
result. Nikzad (2022) and Sethuraman (2022) do not study the maximum rank and
justified envy in RM, TTC and DA, and do not analyse the performance of these
three mechanisms using real-life data in which preferences are correlated.

The RM mechanism was first studied in economics by Featherstone (2020). He
documents that RM has been used in practice to assign teachers to schools in
the US, and shows that any selection of the RM mechanism cannot be strategy-
proof. Nonetheless, he shows that truth-telling is a best response in RM when
students have little information about other students’ preferences and do not
truncate their preference list. He shows that a rank efficient allocation must
be ordinally efficient (and thus ex-post efficient), but the converse is not
necessarily true. He also shows that an inefficient assignment can converge to
the RM outcome by performing local swaps. Troyan (2022) has recently shown
that RM is non-obviously manipulable, meaning that although potential
manipulations exist, they cannot be recognized by cognitively limited agents.
Therefore, RM has better icentives proprties than the well-known Boston
mechanism, which is obviously manipulable.

Finally, Abdulkadiroğlu et al. (2020) show that TTC minimizes justified envy
among all Pareto optimal and strategy-proof mechanisms. Neither DA nor RM are
in this class of mechanisms. We find theoretically that fewer students
experience justified envy in RM than in TTC. In practice RM and TTC generate
roughly the same amount of justified envy.

##  3 Model

We study a standard one-to-one school choice market (Abdulkadiroğlu et al.,
2020), which consists of:

  1. 1.

A set of students $T=\\{1,\ldots,n\\}$,

  2. 2.

A set of schools $S=\\{s_{1},\ldots,s_{n}\\}$, with each school having space
for one student only,

  3. 3.

Strict students’ preferences over schools
$\succ\coloneqq(\succ_{1},\ldots,\succ_{n})$, and

  4. 4.

Strict schools’ priorities over students
$\triangleright=(\triangleright_{s_{1}},\ldots,\triangleright_{s_{n}})$.

An allocation $x$ is a perfect matching between $T$ and $S$. We will denote by
$x_{t}$ the school to which student $t$ is assigned, and by $x_{s}$ the
student that school $s$ is assigned to. Student $i$ experiences justified envy
in allocation $x$ if there exists a school $s$ such that $s\succ_{t}x_{t}$ and
$t\triangleright_{s}x_{s}$.

The function $\textup{rk}_{t}(x_{t})$ returns an integer between 1 and $n$
corresponding to the ranking of $x_{t}$ in the preference list of student $t$,
i.e. the most desirable option gets a ranking of 1, whereas the least
desirable one gets a ranking of $n$. A mechanism is a map from school choice
markets to (a probability distribution over) allocations. An allocation $x$
Pareto dominates a different allocation $y$ if, for every student $t$,
$\textup{rk}_{t}(x_{t})\leq\textup{rk}_{t}(y_{t})$ and for some student $j$,
$\textup{rk}_{j}(x_{j})<\textup{rk}_{j}(y_{j})$. An allocation is Pareto
optimal if it is not Pareto dominated. A Pareto optimal mechanism returns a
Pareto optimal allocation in every school choice problem.

We use $x^{\text{RM}}$ to denote one of the (possibly many) allocations that
minimizes the sum of ranks for students, which we henceforth call rank
efficient or rank minimizing. $X^{\text{RM}}$ denotes the set of all rank
efficient allocations. The rank-minimizing mechanism (henceforth RM) is one
that returns a rank efficient allocation for every matching market.555Rank
efficiency is a stronger efficiency notion than ordinal efficiency and Pareto
optimality (Featherstone, 2020). We simply write efficiency to refer to rank
efficiency.

Two other mechanisms are of interest. The first is top trading cycles (TTC),
in which the following two steps are repeated until all agents have been
assigned an object:

  1. 1.

Construct a graph with one vertex per student or school. Each student (resp.
school) points to their top-ranked school (resp. student) among the remaining
ones. At least one cycle must exist and no two cycles overlap. Select the
cycles in this graph.

  2. 2.

Permanently assign each student in a cycle to the school they point to. Remove
all students and schools involved in a cycle.

The second mechanism of interest is student-proposing deferred acceptance
(DA). It works as follows:

  1. 1.

All unmatched students apply to their most preferred school that has not
rejected them. Each school that has received a proposal puts the one sent by
the highest priority student in a waiting list and permanently rejects all
other received applications (if any).

  2. 2.

Repeat step 1 until all schools have received at least one application. Assign
each student to the school which has them on a waiting list.

We use $x^{\text{TTC}}$ and $x^{\text{DA}}$ to denote the allocation obtained
by the TTC and DA mechanisms, respectively. Schools’ priorities are used to
compute TTC and DA, but are irrelevant in RM.

##  4 Results

Our theoretical results relate to the properties of the expected allocation
generated by RM, TTC and DA when students’ preferences and schools’ priorities
are drawn independently and uniformly at random. This assumption is commonly
used to analyze matching markets.666See Che and Tercieux (2018) and references
therein. We study the asymptotic behavior of: i) expected average rank
(efficiency), ii) expected maximum rank (inequality), and iii) expected number
of students with justified envy generated by RM, TTC and DA in the next
subsections.

### Efficiency

We first study the expected average rank generated by RM, TTC and DA in random
markets. To do so, we define
$\overline{x}\coloneqq\frac{1}{n}\sum_{i=1}^{n}\textup{rk}_{i}(x_{i})$, which
denotes the average rank of the school to which students are assigned in
allocation $x$.

Proposition 1 shows that the expected average ranking in RM is smaller (i.e.
better) than that in TTC and DA. It follows directly from a result by
Parviainen (2004) that has not yet been cited in the economics literature. In
contrast, the results for DA and TTC are well-known and we simply restate them
for completeness.

######  Proposition 1.

The expected average rank in RM, TTC and DA is:

$\lim_{n\to\infty}\mathbb{E}[\overline{x}^{\text{RM}}]\leq 2$ (1)

$\lim_{n\to\infty}\frac{\mathbb{E}[\overline{x}^{\text{TTC}}]}{\log n}=1$ (2)

$\lim_{n\to\infty}\frac{\mathbb{E}[\overline{x}^{\text{DA}}]}{\log n}=1$ (3)

###### Proof.

Statement 1 is proven by Parviainen (2004, Theorem 2.1, p. 105).777Parviainen
(2004) also provides a lower bound, and thus the expected average rank in RM
is such that
$\pi^{2}/6\leq\lim_{n\to\infty}\mathbb{E}[\overline{x}^{\text{RM}}]\leq 2$.
Statement 2 is proven by Knuth (1996, equation 4, p. 439).888Knuth shows that
$\mathbb{E}[\sum_{i=1}^{n}\textup{rk}_{i}(x_{i}^{\text{TTC}})]=(n+1)H_{n}-n$,
where $H_{n}$ is the $n$-th harmonic number and, therefore,
$\lim_{n\to\infty}\frac{1}{n}\mathbb{E}[\sum\textup{rk}(x_{i}^{\text{TTC}})]=\log(n)$.
See also the note after the acknowledgements in Frieze and Pittel (1995), p.
807. Statement 3 is proven by Pittel (1989, Theorem 2, p. 538).

∎

Proposition 1 shows that the rank inefficiency of DA and TTC does not vanish
as the market grows large because, even if the average rank obtained by DA and
TTC grows slowly with the size of the market, the average rank obtained by RM
is constant and does not grow with $n$. T

### Inequality

We measure inequality as the rank of the object obtained by the worst-off
agent in the market, i.e. the maximum rank in the rank distribution. This
measure follows John Rawls’ idea that the welfare of a society is that of its
worst-off member.999Alternatively, one could define inequality as the
difference in ranks between the worst- and best-off agent. Because the rank of
the object obtained by the best-off agent is 1 in any Pareto optimal
allocation (Abdulkadiroğlu and Sönmez, 1998), both measures are equivalent. To
do so, we define $\underline{x}\coloneqq\max_{i}\textup{rk}_{i}(x_{i})$, which
denotes the rank of the object obtained by the worst-off agent in allocation
$x$.

Proposition 2 shows that RM generates a significantly more egalitarian
allocation than DA and TTC. In particular, TTC generates an allocation so
unequal that the worst-off student is assigned to a highly undesirable school
in the lower half of their preference list. Such rank is much higher than the
corresponding value for RM ($\log_{2}(n)$) and DA ($\log^{2}(n))$.

######  Proposition 2.

The expected maximum rank of RM, TTC and DA is:

$\lim_{n\to\infty}\frac{\mathbb{E}[\underline{x}^{\text{RM}}]}{\log_{2}(n)}=1$
(4)

$\lim_{n\to\infty}\frac{\mathbb{E}[\underline{x}^{\text{TTC}}]}{n}>0.5$ (5)

$\lim_{n\to\infty}\frac{\mathbb{E}[\underline{x}^{\text{DA}}]}{\log^{2}(n)}=1$
(6)

###### Proof.

Statement 5 was proven by Knuth (1996, p. 440). Statement 6 was proven by
Pittel (1992), theorem 6.1, p. 382 and note before references, p. 400.

To prove statement 4 we use the asymptotic rank distribution in RM. The
probability that a student is assigned to their $i$-th choice is
asymptotically equal to $\frac{1}{2^{i}}$ (Theorem 1.3 in Parviainen (2004)),
so that a student is assigned to a school with rank 1 with probability 1/2, to
a school with rank 2 with probability 1/4, and so on. This probability
distribution is very similar to the number of consecutive heads in $n$
independent coin tosses, in which 0 heads obtains with probability 1/2, 1
heads with probability 1/4 and so on (the distribution of ranks in RM is
shifted by +1). Finding the longest run of heads is a known problem, in which
the longest run is equal to $\frac{\log(n/2)}{\log(2)}$ (Schilling, 2012).
Therefore, the maximum rank in RM is equal to
$\frac{\log(n)/2}{\log(2)}+1=\log_{2}(n)$.101010Frieze and Sorkin (2007,
Theorem 2, p. 1436) proves that the maximum cost in the cost assignment
problem when costs are uniformly distributed in $[0,n]$ is $\Theta(\log(n))$.
∎

Although we only provide a lower bound for the maximum rank in TTC (of
$0.5\,n$), simulations suggest that the maximum rank in TTC converges to
$0.63\,n$.

### Justified Envy

We use $e^{\text{RM}},e^{\text{TTC}}$ and $e^{\text{DA}}$ to denote the
fraction of students who experience justified envy in the allocation obtained
in RM, TTC and DA, respectively. Proposition 3 shows that RM generates fewer
cases of expected envy than TTC, which is interesting since TTC is envy
minimal in the class of strategy-proof and Pareto optimal mechanisms
(Abdulkadiroğlu et al., 2020).

######  Proposition 3.

The expected fraction of students with justified envy in RM, TTC and DA is:

$\lim_{n\to\infty}\mathbb{E}[e^{\text{RM}}]=0.33$ (7)

$\lim_{n\to\infty}\mathbb{E}[e^{\text{TTC}}]=0.3863$ (8)

$\lim_{n\to\infty}\mathbb{E}[e^{\text{DA}}]=0$ (9)

###### Proof.

Statement 9 is well-known, as DA does not generate justified envy (Gale and
Shapley, 1962).

For the remainder of the proof we use the fact that the number of students
with justified envy in TTC ($e^{\text{TTC}}$) and RSD ($e^{\text{RSD}}$) is
asymptotically equivalent (Che and Tercieux, 2017). Since schools’ priorities
are irrelevant in both RM and RSD, a student who is assigned to their $i$-th
most preferred school does _not_ experience justified envy with probability
$\frac{1}{2^{i-1}}$. To see this, notice that students placed into their 1st
choice trivially do not experience justified envy with probability 1; students
placed into their second best choice do not experience justified envy if the
student who is accepted at his most preferred school has a higher priority
than them, which occurs with probability 1/2; for students who are assigned to
their third choice, they do not experience justified envy if their first and
second most preferred school rank their assigned student above them, i.e. with
probability $1/4$, and so on.

Thus, to obtain the total fraction of students who do not experience justified
envy in RM and RSD (TTC), we just need to multiply i) the probability that a
student matched to their $i$-th most preferred school does not experience
justified envy, times ii) the fraction of students who are assigned to such a
choice in RSD and RM. The fraction of students assigned to their $i$-th choice
in RM asymptotically equals $\frac{1}{2^{i}}$ (Theorem 1.3 in Parviainen
(2004)), whereas in RSD the probability that the $k$-th dictator is assigned
to his $j$-th most preferred school is given by
$p_{k,j}=\frac{1}{n!}\binom{k-1}{j-1}(j-1)!(n-j)!(n+1-k)$ (Knuth,
1996).111111For example, if $k=1$, then $p_{1,1}=1$ and $p_{1,j}=0$ for any
$j>1$. Similarly, when $j=1$, then $p_{k,1}=\frac{n+1-k}{n}$. Note that
${n\choose 0}=1$ and ${n\choose m}=0$ for any $m>n$.  Putting these
expressions together, and after some algebra detailed in Appendix A (for RSD
only), we obtain:

$e^{\text{RM}}=1-\sum_{i=1}^{n}\frac{1}{2^{i}}\times\frac{1}{2^{i-1}}=1-\sum_{i=1}^{n}\frac{1}{2^{2i-1}}\rightarrow
0.33$ (10)

$e^{\text{RSD}}=1-\frac{1}{n}\sum_{i=1}^{n}\sum_{j=1}^{i}\frac{1}{n!}\binom{k-1}{j-1}(j-1)!(n-j)!(n+1-k)\frac{1}{2^{i-1}}\rightarrow
0.3863$ (11)

which finalizes the proof, since
$\lim_{n\to\infty}\mathbb{E}[e^{\text{TTC}}]=\lim_{n\to\infty}\mathbb{E}[e^{\text{RSD}}].$
∎

##  5 Data

One critique that can be made to our random market results is that they assume
that students’ preferences are independent, whereas students’ preferences tend
to be correlated, and such correlation may improve the performance of DA and
TTC with regards to efficiency and equality. We show that this is not the case
by using real-life data from secondary school admissions in Hungary in 2015.
In summary, we find that TTC and DA perform even worse than when we assumed
independent uniform preferences.

Our data contains the preferences and priorities of 10,131 students and 244
schools in Budapest. Because students only rank a few schools and schools only
rank students who apply to them, we apply RM, DA and TTC to i) the actual
reported preferences and priorities (Hungary assigns students to schools using
DA (Biró, 2008), so using the reported preferences as real preferences is a
sensible strategy), and ii) the estimated, complete preferences and
priorities.121212The complete preferences are estimated using the original
students’ reported preferences assuming that i) students do not use dominated
strategies, and ii) the realized assignment is stable. For the complete
estimation procedure see Aue et al. (2020). In both cases, we balanced the
demand and supply for seats by adjusting the schools capacities (this is
because there are substantially more school seats than students, repeating the
exercise with the unbalanced market does not change the comparison between
mechanisms). When a student only ranks $k$ schools, we use $k+1$ as the rank
of being unassigned. RM chooses the rank minimizing assignment randomly among
all rank efficient allocations. Figures 2 and 3 present the distribution of
the ranks realized after applying RM, DA and TTC to the estimated and reported
preferences, respectively. Table 2 presents summary statistics.

Table 2: Rank descriptive statistics for Budapest.

Preferences | Estimated Preferences | Reported Preferences
---|---|---
Variable $\backslash$ Mechanism | RM | TTC | DA | RM | TTC | DA
Mean | 2.7 | 8.9 | 12.3 | 1.5 | 1.9 | 2.1
Maximum | 16 | 244 | 241 | 6 | 14 | 13
Variance | 4.7 | 607.4 | 220.1 | 0.6 | 1.7 | 1.9
Share of students | 0.58 | 0.64 | 0 | 0.46 | 0.44 | 0
w. justified envy |  |  |  |  |  |
Unassigned students | – | – | – | 2,555 | 2,508 | 2,704

For reported preferences, the mean is computed dividing by the number of
assigned students.

The lessons we learn from computing the rank distributions in Budapest are
similar to those we learned from looking at random markets. Table 2 shows that
RM performs better than TTC and the currently used DA with regards to
efficiency and equality with reported and estimated preferences. When full,
estimated rank lists are used, the average student substantially improves
their placement (average rank in RM is 2.7, compared to 8.9 in TTC and 12.3 in
DA). RM still generates a better average rank when we use stated preferences,
but the difference with the average rank generated by TTC and DA is smaller
(this is because the average student only ranks 4.1 schools on average). RM
assigns the average student to a school in their 16 percentile of their
preference lists, whereas the corresponding percentile for DA and TTC are 35
and 29, respectively.

Figure 3: Rank distribution generated for 10,131 students in the secondary
school admissions in Budapest using reported preferences. The last bar (0)
denotes unassigned students.

With regards to inequality, RM performs much better than DA and TTC with
complete preferences, assigning the worst-off student to the 16th best choice
rather than to their 241th and 244th, respectively (out of 244). It also
assigns less than 2% of the student population to their 10th ranked school or
worse, whereas TTC and DA assign 16% and 41% of the student population to such
school, respectively. RM also generates a significantly more egalitarian
allocation with reported (incomplete) preferences, assigning the worst-off
student to the 6th best choice rather than their 13th or 14th best. With
estimated and reported preferences, we find that DA and TTC are incomparable
in terms of equality, since TTC assigns more students to a really undesirable
school, but also assigns more students to a top 3 school. When reported
(incomplete) preferences are used, the number of students unassigned in RM,
TTC and DA is roughly equivalent.

Our rank distributions are similar to those documented in other studies. Che
and Tercieux (2018) and Abdulkadiroğlu et al. (2020) also document that TTC
assigns more students to their first choice than DA. Both studies also find
that DA and TTC generate a similar number of unassigned students.

Our empirical analysis has used the preferences that students submit in DA
(arguably their true ones) to generate the TTC and RM allocations. One
potential concern is that students would submit different preferences when
allocations are determined by RM, which is not strategy-proof. To tackle this
concern, we have computed the rank distribution generated by RM when a
fraction of the students who have incentives to misrepresent their preferences
do so. We have found that the rank distribution and number of students with
justified envy remain largely unchanged, and thus is safe to conclude that the
rank distribution generated by RM is more efficient and equal than the ones
generated by DA and TTC, even when a fraction of agents misrepresent their
preferences.131313See the Appendix for detailed summary statistics.

Moreover, just because RM can be manipulated, does not mean that it will
actually be manipulated in practice. RM is non-obviously manipulable, and thus
cannot be manipulated by cognitively limited agents (Troyan, 2022).
Furthermore, the potential gains from manipulation are small (the average
student can only improve by less than one rank place in their preference list
with iid preferences, and by less than 2 rank places in the data). Finally,
there is evidence that truthful behavior can depend more on the complexity of
the mechanism rather than actual strategy-proofness (Cerrone et al., 2022),
and RM is arguably more complex to explain and predict than DA and
TTC.141414Cerrone et al. (2022) find that almost twice as many people (70%
versus 40%) behave truthfully in the efficiency adjusted deferred acceptance
(EADA) mechanism versus standard DA, even though DA is strategy-proof and EADA
is not. Truthful behavior is also more common in complex mechanisms in other
setups, like cake-cutting (Kyropoulou et al., 2022). Thus, it is not clear
that RM would be more manipulated in practice. Whether students actually
misrepresent their preferences in RM more than they do in DA or TTC is an open
question that could be tackled using lab experiments.

##  6 Conclusion

Our paper highlights the efficiency loss and inequality generated by the
celebrated deferred acceptance and top trading cycles mechanisms. We are also
the first to compute the asymptotic fraction of students with justified envy
in the rank minimizing and the top trading mechanisms. Our findings are
confirmed by real school choice data and simulations.

The rank minimizing mechanism is superior than deferred acceptance and top
trading cycles in terms of efficiency and equality, two key desiderata in
economic theory and distributive justice (Moulin, 2003). The outstanding
efficiency and equality of the rank minimizing mechanism in theory and
practice are strong arguments for its use in some situations, particularly
when schools’ priorities are random lotteries, as in Brighton and Hove (Allen
et al., 2013), Amsterdam (Oosterbeek et al., 2020) and a growing number of
British cities.151515The UK official School Admissions Code 2007 and the
report by Coldron et al. (2008) propose the use of lotteries to mitigate
segregation. In Northern Ireland, secondary schools’ priorities are not
allowed by law to depend on academic selection (Brown et al., 2021). In
England, a small but growing number of schools use lotteries as the main
admissions criterion (Noden et al., 2014).

Nonetheless, deferred acceptance and top trading cycles are better than RM in
two fronts. Firstly, the rank minimizing mechanism fails to be strategy-proof.
However, recent results have shown that theoretical strategy-proofness does
not imply truthful behavior in practice. Substantial strategic behavior in
strategy-proof mechanisms such as DA and TTC has been documented in laboratory
experiments (Chen and Sönmez, 2006; Rees-Jones and Skowronek, 2018; Guillen
and Veszteg, 2021; Cerrone et al., 2022) and in real life (Hassidim et al.,
2017; Rees-Jones, 2018; Shorrer and Sóvágó, 2018).161616Guillen and Veszteg
(2021) write: “In a school-allocation setting, we find that roughly half of
the observed truth-telling under TTC and DA is the result of naïve (non-
strategic) behaviour. Only 14–31% of the participants choose actions that are
compatible with rational behaviour. We argue that the use of a default option,
confusion and other behavioural biases account for the vast majority of
truthful play in both TTC and DA in laboratory experiments”. Thus, it is
unclear whether RM would be more manipulated in practice than DA or TTC,
particularly because RM is non-obviously manipulable (Troyan, 2022).

Secondly, DA and TTC are superior to RM in that they actually take schools’
priorities into account, which is a desirable property in some situations.
However, although TTC uses schools’ priorities and RM does not, TTC generates
more justified envy than RM in theory and about the same in practice,
suggesting that TTC does not use priorities _in the right way_ – a point also
argued by Che and Tercieux (2017). This concern, added to the fact that TTC
assigns some students to a school in the bottom half of their preference list,
are objections that our paper raises against using TTC in applications.
Pycia’s equivalence result implies that these serious concerns extend to the
well-known random serial dictatorship mechanism and to any other Pareto
optimal and strategy-proof mechanism. Furthermore, these concerns extend to
the application of TTC and random serial dictatorship to one-sided matching
problems with or without ownership (sometimes called assignment problems)
(Shapley and Scarf, 1974; Bogomolnaia and Moulin, 2001), to where our results
carry over.

## References

  * Abdulkadiroğlu et al. (2009) Abdulkadiroğlu, A., P. A. Pathak, and A. E. Roth (2009): “Strategy-proofness versus efficiency in matching with indifferences: Redesigning the NYC high school match,” _American Economic Review_ , 99, 1954–78.
  * Abdulkadiroğlu et al. (2020) Abdulkadiroğlu, A., Y.-K. Che, P. A. Pathak, A. E. Roth, and O. Tercieux (2020): “Efficiency, justified envy, and incentives in priority-based matching,” _American Economic Review: Insights_ , 2, 425–42.
  * Abdulkadiroğlu and Sönmez (1998) Abdulkadiroğlu, A. and T. Sönmez (1998): “Random serial dictatorship and the core from random endowments in house allocation problems,” _Econometrica_ , 66, 689–701.
  * Aldous (2001) Aldous, D. J. (2001): “The $\zeta$ (2) limit in the random assignment problem,” _Random Structures & Algorithms_, 18, 381–418.
  * Allen et al. (2013) Allen, R., S. Burgess, and L. McKenna (2013): “The short-run impact of using lotteries for school admissions: early results from Brighton and Hove’s reforms,” _Transactions of the Institute of British Geographers_ , 38, 149–166.
  * Aue et al. (2020) Aue, R., T. Klein, and J. Ortega (2020): “What happens when separate and unequal school districts merge?” _Centre for European Economic Research Discussion Paper_.
  * Biró (2008) Biró, P. (2008): “Student admissions in Hungary as Gale and Shapley envisaged,” _University of Glasgow Technical Report TR-2008-291_.
  * Bogomolnaia and Moulin (2001) Bogomolnaia, A. and H. Moulin (2001): “A new solution to the random assignment problem,” _Journal of Economic Theory_ , 100, 295 – 328\.
  * Brown et al. (2021) Brown, M., C. Donnelly, P. Shevlin, C. Skerritt, G. McNamara, and J. O’Hara (2021): “The rise and fall and rise of academic selection: The case of Northern Ireland,” _Irish Studies in International Affairs_ , 32, 477–498.
  * Carroll (2014) Carroll, G. (2014): “A general equivalence theorem for allocation of indivisible objects,” _Journal of Mathematical Economics_ , 51, 163–177.
  * Cerrone et al. (2022) Cerrone, C., Y. Hermstrüwer, and O. Kesten (2022): “School choice with consent: an experiment,” _MPI Collective Goods Discussion Paper_.
  * Che and Kojima (2010) Che, Y.-K. and F. Kojima (2010): “Asymptotic Equivalence of Probabilistic Serial and Random Priority Mechanisms,” _Econometrica_ , 78, 1625–1672.
  * Che and Tercieux (2017) Che, Y.-K. and O. Tercieux (2017): “Top trading cycles in prioritized matching: An irrelevance of priorities in large markets,” _Unpublished Manuscript, Columbia University_.
  * Che and Tercieux (2018) ——— (2018): “Payoff equivalence of efficient mechanisms in large matching markets,” _Theoretical Economics_ , 13, 239–271.
  * Che and Tercieux (2019) ——— (2019): “Efficiency and stability in large matching markets,” _Journal of Political Economy_ , 127, 2301–2342.
  * Chen and Sönmez (2006) Chen, Y. and T. Sönmez (2006): “School choice: an experimental study,” _Journal of Economic theory_ , 127, 202–231.
  * Coldron et al. (2008) Coldron, J., E. Tanner, S. Finch, L. Shipton, C. Wolstenholme, B. Willis, S. Demack, and B. Stiell (2008): “Secondary school admissions,” Tech. rep., Department for Children, Schools and Families.
  * Featherstone (2020) Featherstone, C. (2020): “Rank efficiency: Modeling a common policymaker objective,” _Unpublished paper, University of Pennsylvania_.
  * Frieze and Pittel (1995) Frieze, A. and B. G. Pittel (1995): “Probabilistic analysis of an algorithm in the theory of markets in indivisible goods,” _The Annals of Applied Probability_ , 768–808.
  * Frieze and Sorkin (2007) Frieze, A. and G. B. Sorkin (2007): “The probabilistic relationship between the assignment and asymmetric traveling salesman problems,” _SIAM Journal on Computing_ , 36, 1435–1452.
  * Gale and Shapley (1962) Gale, D. and L. S. Shapley (1962): “College admissions and the stability of marriage,” _The American Mathematical Monthly_ , 69, 9–15.
  * Guillen and Veszteg (2021) Guillen, P. and R. F. Veszteg (2021): “Strategy-proofness in experimental matching markets,” _Experimental Economics_ , 24, 650–668.
  * Hassidim et al. (2017) Hassidim, A., D. Marciano, A. Romm, and R. I. Shorrer (2017): “The mechanism is truthful, why aren’t you?” _American Economic Review_ , 107, 220–24.
  * Knuth (1996) Knuth, D. (1996): “An exact analysis of stable allocation,” _Journal of Algorithms_ , 20, 431 – 442.
  * Krokhmal and Pardalos (2009) Krokhmal, P. A. and P. M. Pardalos (2009): “Random assignment problems,” _European Journal of Operational Research_ , 194, 1–17.
  * Kyropoulou et al. (2022) Kyropoulou, M., J. Ortega, and E. Segal-Halevi (2022): “Fair cake-cutting in practice,” _Games and Economic Behavior_ , 133, 28–49.
  * Liu and Pycia (2016) Liu, Q. and M. Pycia (2016): “Ordinal efficiency, fairness, and incentives in large markets,” _SSRN preprint_.
  * Manea (2009) Manea, M. (2009): “Asymptotic ordinal inefficiency of random serial dictatorship,” _Theoretical Economics_ , 4, 165–197.
  * Moulin (2003) Moulin, H. (2003): _Fair division and collective welfare_ , Cambridge, MA, USA: MIT Press.
  * Nikzad (2022) Nikzad, A. (2022): “Rank-optimal assignments in uniform markets,” _Theoretical Economics_ , 17, 25–55.
  * Noden et al. (2014) Noden, P., A. West, and A. Hind (2014): “Banding and ballots: secondary school admisssions in England: admissions in 2012/13 and the impact of growth of academies,” Tech. rep., The Sutton Trust.
  * Olin (1992) Olin, B. (1992): _Asymptotic properties of random assignment problems_ , PhD Thesis, Stockholm Royal Institute of Technology.
  * Oosterbeek et al. (2020) Oosterbeek, H., N. Ruijs, and I. De Wolf (2020): “Using admission lotteries to estimate heterogeneous effects of elite schools,” _Unpublished paper, SSRN_.
  * Parviainen (2004) Parviainen, R. (2004): “Random assignment with integer costs,” _Combinatorics, Probability and Computing_ , 13, 103–113.
  * Pathak and Sönmez (2013) Pathak, P. A. and T. Sönmez (2013): “School admissions reform in Chicago and England: Comparing mechanisms by their vulnerability to manipulation,” _American Economic Review_ , 103, 80–106.
  * Pittel (1989) Pittel, B. (1989): “The average number of stable matchings,” _SIAM Journal on Discrete Mathematics_ , 2, 530–549.
  * Pittel (1992) ——— (1992): “On likely solutions of a stable marriage problem,” _The Annals of Applied Probability_ , 358–401.
  * Pycia (2019) Pycia, M. (2019): “Evaluating with statistics: Which outcome measures differentiate among matching mechanisms?” _Unpublished paper, University of Zurich_.
  * Pycia and Troyan (2021) Pycia, M. and P. Troyan (2021): “A theory of simplicity in games and mechanism design,” _Unpublished paper, University of Zurich_.
  * Rees-Jones (2018) Rees-Jones, A. (2018): “Suboptimal behavior in strategy-proof mechanisms: Evidence from the residency match,” _Games and Economic Behavior_ , 108, 317–330.
  * Rees-Jones and Skowronek (2018) Rees-Jones, A. and S. Skowronek (2018): “An experimental investigation of preference misrepresentation in the residency match,” _Proceedings of the National Academy of Sciences_ , 115, 11471–11476.
  * Schilling (2012) Schilling, M. F. (2012): “The surprising predictability of long runs,” _Mathematics Magazine_ , 85, 141–149.
  * Sethuraman (2022) Sethuraman, J. (2022): “A note on the average rank of rank-optimal assignments,” _unpublished_.
  * Shapley and Scarf (1974) Shapley, L. and H. Scarf (1974): “On cores and indivisibility,” _Journal of Mathematical Economics_ , 1, 23 – 37.
  * Shorrer and Sóvágó (2018) Shorrer, R. I. and S. Sóvágó (2018): “Obvious mistakes in a strategically simple college admissions environment: Causes and consequences,” _Available at SSRN 2993538_.
  * Troyan (2022) Troyan, P. (2022): “Non-Obvious Manipulability of the Rank-Minimizing Mechanism,” _arXiv preprint arXiv:2206.11359_.

## Appendix A - Proof of Proposition 3

In RSD the probability that the $k$-th dictator is assigned to his $j$-th most
preferred school is given by

$p_{k,j}=\frac{1}{n!}\binom{k-1}{j-1}(j-1)!(n-j)!(n+1-k)$ (12)

In equation (12), if $k=1$, then $p_{1,1}=1$ (the probability that the first
dictator gets his first school is one) and $p_{1,j}=0$ for any $j>1$ (the
probability that the first dictator gets a school worse than his top one is
zero). Similarly, when $j=1$, then $p_{k,1}=\frac{n+1-k}{n}$ (this is the
probability that the $k$-th dictator gets his top school, or equivalently, the
probability that the $k-1$ dictators before him are assigned to the school
that dictator $k$ ranks as first). Note that ${n\choose 0}=1$ and ${n\choose
m}=0$ for any $m>n$, so that the probability that dictator $k$ is assigned to
a school with a rank higher than $k$ is zero.

Equation (12) can be rewritten as:

$\displaystyle p_{k,j}$ $\displaystyle=$
$\displaystyle\frac{1}{n!}\binom{k-1}{j-1}(j-1)!(n-j)!(n+1-k)$ (13)
$\displaystyle=$
$\displaystyle(n+1-k)\frac{(k-1)!(j-1)!(n-j)!}{n!(j-1)!(k-j)!}$ (14)
$\displaystyle=$
$\displaystyle(n+1-k)\frac{(k-1)!(j-1)!(n-j)!}{n!(j-1)!(k-j)!}\frac{k}{k}\frac{j}{j}$
(15) $\displaystyle=$
$\displaystyle(n+1-k)\frac{k!j!(n-j)!}{n!j!(k-j)!}\frac{1}{k}$ (16)
$\displaystyle p_{k,j}$ $\displaystyle=$
$\displaystyle\frac{(n+1-k)}{k}\frac{\binom{k}{j}}{\binom{n}{j}}$ (17)

Since RSD is independent of schools’ priorities, a student placed in their
$j$-th most preferred school does _not_ experience envy with probability
$\frac{1}{2^{j-1}}$.

Therefore, the total number of students without justified envy in RSD
$(NE^{\text{RSD}})$ equals

$\displaystyle NE^{\text{RSD}}$ $\displaystyle=$
$\displaystyle\sum_{k=1}^{n}\sum_{j=k}^{n}\frac{(n+1-k)}{k}\frac{\binom{k}{j}}{\binom{n}{j}}\frac{1}{2^{j-1}}$
(18) $\displaystyle=$
$\displaystyle\sum_{j=1}^{n}\sum_{k=j}^{n}\frac{(n+1-k)}{k}\frac{\binom{k}{j}}{\binom{n}{j}}\frac{1}{2^{j-1}}$
(19) $\displaystyle=$
$\displaystyle\sum_{j=1}^{n}\frac{1}{\binom{n}{j}2^{j-1}}\sum_{k=j}^{n}\frac{(n+1-k)}{k}\binom{k}{j}$
(20) $\displaystyle=$
$\displaystyle\sum_{j=1}^{n}\frac{1}{\binom{n}{j}2^{j-1}}\left[(n+1)\underbrace{\sum_{k=j}^{n}\frac{1}{k}\binom{k}{j}}_{A}-\sum_{k=j}^{n}\binom{k}{j}\right]$
(21)

Where

$\displaystyle A$ $\displaystyle=$
$\displaystyle\sum_{k=j}^{n}\frac{1}{k}\binom{k}{j}=\sum_{k=j}^{n}\frac{1}{k}\frac{k!}{j!(k-j)!}=\sum_{k=j}^{n}\frac{(k-1)!}{j\,(j-1)!(k-j)!}$
(22) $\displaystyle=$
$\displaystyle\frac{1}{j}\sum_{k=j}^{n}\binom{k-1}{j-1}=\frac{1}{j}\sum_{k=j-1}^{n-1}\binom{k}{j-1}$
(23)

Plugging this in our expression for $NE^{\text{RSD}}$, we have

$\displaystyle
NE^{\text{RSD}}=\sum_{j=1}^{n}\frac{1}{\binom{n}{j}2^{j-1}}\left[\frac{n+1}{j}\sum_{k=j-1}^{n-1}\binom{k}{j-1}-\sum_{k=j}^{n}\binom{k}{j}\right]$
(24)

Using the Hockey-stick identity $\sum_{k=j}^{n}\binom{k}{j}=\binom{n+1}{j+1}$,
we can simplify the expression to

$\displaystyle NE^{\text{RSD}}$ $\displaystyle=$
$\displaystyle\sum_{j=1}^{n}\frac{1}{\binom{n}{j}2^{j-1}}\left[\frac{n+1}{j}\binom{n}{j}-\binom{n+1}{j+1}\right]$
(25) $\displaystyle=$
$\displaystyle\sum_{j=1}^{n}\frac{1}{\binom{n}{j}2^{j-1}}\left[\frac{n+1}{j}\binom{n}{j}-\frac{(n+1)\,n!}{(j+1)\,j!(n-j)!}\right]$
(26) $\displaystyle=$
$\displaystyle\sum_{j=1}^{n}\frac{1}{\binom{n}{j}2^{j-1}}\left[(n+1)\left(\frac{1}{j}-\frac{1}{j+1}\right)\binom{n}{j}\right]$
(27) $\displaystyle=$
$\displaystyle(n+1)\sum_{j=1}^{n}\left(\frac{1}{2}\right)^{j-1}\left(\frac{1}{j}-\frac{1}{j+1}\right)$
(28)

We divide both sides by $n+1$, and continue simplifying the expression to
obtain

$\displaystyle\frac{NE^{\text{RSD}}}{n+1}$ $\displaystyle=$
$\displaystyle\sum_{j=1}^{n}\left(\frac{1}{2}\right)^{j-1}\frac{1}{j}-\sum_{j=1}^{n}\left(\frac{1}{2}\right)^{j-1}\frac{1}{j+1}$
(29) $\displaystyle=$ $\displaystyle
2\sum_{j=1}^{n}\left(\frac{1}{2}\right)^{j}\frac{1}{j}-4\sum_{j=1}^{n}\left(\frac{1}{2}\right)^{j+1}\frac{1}{j+1}$
(30) $\displaystyle=$ $\displaystyle
2\sum_{j=1}^{n}\left(\frac{1}{2}\right)^{j}\frac{1}{j}-4\sum_{j=2}^{n+1}\left(\frac{1}{2}\right)^{j}\frac{1}{j}$
(31) $\displaystyle=$
$\displaystyle-2\sum_{j=2}^{n}\left(\frac{1}{2}\right)^{j}\frac{1}{j}+1-\frac{4}{(n+1)}\left(\frac{1}{2}\right)^{n+1}$
(32) $\displaystyle=$
$\displaystyle-2\sum_{j=2}^{n}\left(\frac{1}{2}\right)^{j}\frac{1}{j}+1-\frac{4}{(n+1)}\left(\frac{1}{2}\right)^{n+1}-1+1$
(33) $\displaystyle=$
$\displaystyle-2\sum_{j=1}^{n}\left(\frac{1}{2}\right)^{j}\frac{1}{j}+2-\frac{4}{(n+1)}\left(\frac{1}{2}\right)^{n+1}$
(34) $\displaystyle=$ $\displaystyle
2-\underbrace{\frac{1}{(n+1)}\left(\frac{1}{2}\right)^{n-1}}_{B}-2\underbrace{\sum_{j=1}^{n}\left(\frac{1}{2}\right)^{j}\frac{1}{j}}_{C}$
(35)

Taking the limit as $n$ goes to infinity, $B$ goes to 0 and $C$ is the Taylor
expansion for $-\ln(1/2)$, and we obtain

$\displaystyle\lim_{n\to\infty}\frac{NE^{\text{RSD}}}{n}=\lim_{n\to\infty}\frac{NE^{\text{RSD}}}{n+1}=\lim_{n\to\infty}2+2\ln(\frac{1}{2})=0.6137$
(36)

Thus, the fraction of students who experience justified envy in RSD tends to
$e^{\text{RSD}}=1-0.6137=0.3863$, which is what we wanted to prove.

## Appendix B - Simulations

In simulated markets (see Tables 3 and 4), we clearly see that RM dominates
TTC and DA in efficiency (average rank) and inequality (maximum rank). Given
the large ranks that realize in TTC, it is unsurprising that the variance of
the rank distribution is large too. The variance of RM is much smaller, which
shows that the ranks are heavily concentrated among the first four top
choices. Table 3 also allows us to assess the accuracy of the random market
results presented in section 4. For TTC, the mean rank is surprisingly close
to the theoretical prediction ($\pm 1$ of $\log(n)$). In RM, the upper bound
provided of 2 for the mean is quite tight, and the approximation $\log_{2}(n)$
for the max rank is also remarkably accurate.

Table 3: Rank descriptive statistics. Average over 1,000 simulations. Variable | $n=100$ | $n=500$
---|---|---
RM | TTC | DA | RM | TTC | DA
Mean | 1.8 | 4.3 | 5.0 | 1.8 | 5.8 | 6.7
Max | 6 | 64 | 23.2 | 8 | 315 | 42.6
Variance | 1.3 | 73.3 | 18.5 | 1.34 | 421.0 | 37.6

The severity of the inequality generated by TTC is fully exposed in Table 4.
TTC not only makes someone really worse off, assigning them a really bad
object ($0.63\,n$), but it assigns an object in the bottom 90% (not top 10%)
of their preferences to over 1.5% of the agents. In contrast, RM does not
assign such a poor option to any agent. RM also assigns more agents to their
top choice than TTC.

Table 4: Percentage of agents who receive an object with rank higher (worse) than $m$. Average over 1,000 simulations. $m$ | $n=100$ | $n=500$ |
---|---|---|---
RM | TTC | DA | RM | TTC | DA
$1$ | 46 | 50 | 96 | 46.6 | 49.8 | 93.2
$2$ | 21 | 33 | 72 | 21.0 | 33.2 | 79.6
$\log(n)$ | 3 | 20 | 40 | 0.6 | 14.2 | 39.8
$0.1\,n$ | 0 | 8 | 12 | 0 | 1.8 | 0
$0.25\,n$ | 0 | 3 | 0 | 0 | 0.6 | 0
$0.5\,n$ | 0 | 1 | 0 | 0 | 0.2 | 0

## Appendix C - Strategic applicants

To understand the impact of manipulating students on the rank distribution
generated by RM, we compute the RM allocation when a fraction (20%, 40%, 60%
and 80%) of students who have incentives to manipulate do so. We consider two
possible manipulations.

Drop-Assigned: In the reported preference data from Budapest, 5,183 students
are not assigned their first preference in the RM. A first possible
manipulation we consider is for them to move their assigned school to the end
of their preference list in the hope of increasing admissions chances at a
more preferred school. That is, a student who ranks $s_{1}\succ\cdots\succ
s_{i}\succ\cdots\succ s_{n}$ and gets $s_{i}$ will perform a manipulation of
the form $s_{1}\succ\cdots\succ s_{n}\succ s_{i}$. This is equivalent to not
ranking the school to which the applicant would have been assigned.

Drop-First: Another 3,369 students are neither assigned their first nor their
second preference in the RM. A second possible manipulation we consider is for
them to move their first preference to the end of their preference list in the
hope of increasing admissions chances at their second preference. That is, a
student who ranks $s_{1}\succ s_{2}\succ s_{3}\succ\cdots\succ s_{n}$ and gets
$s_{3}$ or worse will perform a manipulation of the form $s_{2}\succ
s_{3}\succ\cdots\succ s_{n}\succ s_{1}$. This manipulation has been observed
in real life applications (Abdulkadiroğlu and Sönmez, 1998).

Table 5 shows that the summary statistics in RM remain largely unchanged in
the presence of strategic applicants. The statistics for the RM with a share
of 0% strategic applicants are equivalent to the RM results with reported
preferences in Table 2. With an increasing share of strategic applicants, the
average and maximum rank change marginally, remaining well below the
corresponding ranks for DA and TTC. Justified envy remains about the same. The
number of unassigned students slightly decreases for the first manipulation,
and slightly increases for the second one.

Table 5: Rank descriptive statistics for RM with strategic applicants. Reported Preferences | Share (number) of strategic applicants
---|---
Variable $\backslash$ RM mechanism | 0% | 20% | 40% | 60% | 80%
| (0) | (1,036) | (2,073) | (3,109) | (4,146)
Panel A: Drop-Assigned
Mean | 1.48 | 1.50 | 1.51 | 1.53 | 1.54
Maximum | 6 | 7 | 6 | 6 | 7
Variance | 0.58 | 0.70 | 0.70 | 0.81 | 0.82
Share of students | 0.46 | 0.45 | 0.45 | 0.46 | 0.46
w. justified envy |  |  |  |  |
Unassigned students | 2,555 | 2,599 | 2,590 | 2,636 | 2,625
Panel B: Drop-First
Mean | 1.48 | 1.50 | 1.52 | 1.54 | 1.56
Maximum | 6 | 6 | 6 | 6 | 6
Variance | 0.58 | 0.61 | 0.63 | 0.65 | 0.67
Share of students | 0.46 | 0.46 | 0.46 | 0.47 | 0.47
w. justified envy |  |  |  |  |
Unassigned students | 2,555 | 2,526 | 2,503 | 2,479 | 2,449

Figure 4 presents the rank distributions. Overall, the results show that the
rank distributions remain largely unchanged, even for large shares of
strategic applicants.

(a) Drop-Assigned.

(b) Drop-First.

Figure 4: Rank distribution generated by RM for 10,131 students in the
secondary school admissions in Budapest using reported preferences by fraction
of strategic applicants. The last bar (0) denotes unassigned students.


Department of Computer Science, University of Iowa,
Iowa City, IA<EMAIL_ADDRESS>Department of Computer
Science, University of Iowa,
Iowa City, IA<EMAIL_ADDRESS>Department of Computer Science,
University of Iowa,
Iowa City, IA<EMAIL_ADDRESS>Department of Computer Science,
University of Iowa,
Iowa City, IA<EMAIL_ADDRESS>Sayan Bandyapadhyay, Tanmay
Inamdar, Shreyas Pai, and Kasturi Varadarajan The first, second and fourth
authors are partially supported by the National Science Foundation under Grant
CCF-1615845. [500]Theory of computation Facility location and clustering
[300]Theory of computation Computational geometry Michael A. Bender, Ola
Svensson, and Grzegorz Herman 3 27th Annual European Symposium on Algorithms
(ESA 2019) ESA 2019 ESA 2019 September 9–11, 2019 Munich/Garching, Germany 144
10

# A Constant Approximation for Colorful $k$-Center

Sayan Bandyapadhyay  Tanmay Inamdar  Shreyas Pai  Kasturi Varadarajan

###### Abstract

In this paper, we consider the colorful $k$-center problem, which is a
generalization of the well-known $k$-center problem. Here, we are given red
and blue points in a metric space, and a coverage requirement for each color.
The goal is to find the smallest radius $\rho$, such that with $k$ balls of
radius $\rho$, the desired number of points of each color can be covered. We
obtain a constant approximation for this problem in the Euclidean plane. We
obtain this result by combining a “pseudo-approximation” algorithm that works
in any metric space, and an approximation algorithm that works for a special
class of instances in the plane. The latter algorithm uses a novel connection
to a certain matching problem in graphs.

###### keywords:

Colorful $k$-center, Euclidean Plane, LP Rounding, Outliers

##  1 Introduction

In the $k$-center problem, we are given a finite metric space $(P,d)$, where
$P$ is a set of $n$ points, and $d:P\times P\rightarrow\mathbb{R}^{+}$ is the
associated distance function. We are also given an integer $1\leq k\leq n$.
The goal is to find a subset $C\subseteq P$ of centers, where $|C|=k$, so as
to minimize $\max_{p\in P}\min_{c\in C}d(p,c)$, the maximum distance of a
point from its nearest center. Geometrically, we want to find the smallest
radius $\rho$ such that $P$ can be covered by $k$ balls of radius $\rho$
(centered at points in $P$).

It is well known that $k$-center is NP-hard; furthermore, it is also NP-hard
to approximate the optimal radius to within a $2-\epsilon$ factor, for any
$\epsilon>0$. This is easily seen via a reduction from the minimum dominating
set problem [16]. On the other hand, it is possible to obtain a tight
approximation ratio of $2$ [11, 15]. A simple greedy algorithm of [11]
achieving this starts with $C$ containing an arbitrary point in $P$; in each
of the subsequent $k-1$ iterations, it finds a point $p\in P$ that maximizes
$d(p,C):=\min_{c\in C}d(p,c)$, and adds that point to $C$.

In the $k$-center with outliers problem, we are given an additional parameter
$1\leq p\leq n$. The goal is to find the smallest radius $\rho$ such that at
least $p$ points of $P$ can be covered by $k$ balls of radius $\rho$. Thus, we
allow up to $n-p$ points to remain uncovered, and these would be “outliers.”
Intuitively, in comparison to $k$-center, an algorithm for solving this
problem has to also figure out which $p$ points to cover. Nevertheless,
Charikar et al. [6], who introduced this problem, gave a simple
$3$-approximation using a greedy algorithm. Their algorithm guesses the
optimal radius $\rho$; then, for $k$ iterations, it finds the ball of radius
$\rho$ that covers the maximum number of yet uncovered points, expands it by a
factor of $3$, and adds it to the solution. More recently, the approximation
guarantee was improved to $2$, using LP-rounding techniques [4, 13]. Note that
this approximation guarantee is tight, in light of the $2-\epsilon$ hardness
result mentioned earlier.

We now introduce the colorful $k$-center problem, which is studied in this
article. As in $k$-center, the input consists of a set $P$ of $n$ points in a
metric space, and an integer $k$. Furthermore, we are given a partition
$\\{P_{1},P_{2},\ldots,P_{c}\\}$ of $P$ into $c$ color classes, and a coverage
requirement $0\leq t_{i}\leq|P_{i}|$ for each color class $1\leq i\leq c$. The
goal is to find the smallest radius $\rho$ such that using $k$ balls of radius
$\rho$, centered at points of $P$, we can simultaneously cover at least
$t_{i}$ points from each class $P_{i}$. When we have only one color class,
that is, when $c=1$, we obtain the $k$-center with outliers problem. In much
of this article, we focus on the case with two color classes, where $c=2$. In
this case, we call the colors red and blue; we denote $P_{1}$ and $P_{2}$,
respectively, by $R$ (red points) and $B$ (blue points), and denote the
coverage requirements $t_{1}$ and $t_{2}$, respectively, by $r$ and $b$. The
motivation for studying this problem is as follows. Each color class can be
thought of as a certain demographic with a specific coverage requirement,
which must be satisfied by the $k$ balls chosen in the solution.

Even with two colors, the colorful $k$-center is quite challenging. The greedy
algorithm for $k$-center with outliers [6] has no obvious generalization: with
two color classes, what do we optimize when adding the next ball to our
solution? The LP-based approaches for $k$-center with outliers do not
generalize either – as we point out (in Example 2.3), the natural LP has an
unbounded integrality gap.

Chakrabarty et al. [4] study a closely related problem called non-uniform $k$
center. As input to this problem, we are given a set $P$ of points in a metric
space, $\lambda$ distinct radii $r_{1}>\cdots>r_{\lambda}\geq 0$ and
corresponding integers $t_{1},\ldots,t_{\lambda}$. The goal is to find the
smallest dilation $\beta\geq 0$ such that $P$ can be covered by a collection
of balls formed by including, for each $1\leq i\leq\lambda$, $t_{i}$ balls of
radius $\beta\cdot r_{i}$. When $\lambda=1$, we get the regular $k$-center
problem. When $\lambda$ is unbounded, the problem is hard to approximate to
within any constant factor; when $\lambda=2$, one can get an
$O(1)$-approximation; and when $\lambda$ is a constant greater than $2$, it is
open as to whether an $O(1)$-approximation is possible [4].

As Chakrabarty et al. [4] observe, there is a close relationship between
$k$-center with outliers and non-uniform $k$-center with $\lambda=2$. In fact,
it can be shown that the two problems are equivalent up to an
$O(1)$-approximation factor. While the relationship between the colorful
$k$-center with $c$ color classes and non-uniform $k$-center with $c+1$
distinct radii is not known to be as close for $c\geq 2$, the study of the
latter problem is one motivation that led us to the colorful $k$-center
problem.

###  1.1 Other Related Work

The $k$-means and $k$-median are classic NP-hard clustering problems that are
closely related to the $k$-center problem. Like the $k$-center problem, these
problems have been extensively studied, resulting in different approaches
guaranteeing constant factor approximations. More recently, the outlier
versions of these problems were also studied; constant factor approximations
were obtained for $k$-median with outliers [8, 19] and $k$-means with outliers
[19]. A polynomial time bicriteria $(1+\epsilon)$-approximation using at most
$k(1+\epsilon)$ centers for any $\epsilon>0$ is known in low dimensional
Euclidean spaces, and metric spaces with constant doubling dimension [10].

Facility location with outliers, which is referred to as Robust Facility
Location, is a generalization of the uncapacitated Facility Location problem;
various constant approximations are known for the latter problem. The Robust
Facility Location problem was introduced in [6], who gave a $3$-approximation.
The approximation guarantee was later improved by Jain et al. [18] to $2$.

A colorful version of vertex cover is studied in [1], and colorful versions of
the Set Cover and Facility Location-type problems were considered in [17]. In
these problems, the cardinality of the cover (or its weight) shows up in the
objective function, unlike in $k$-center, where the number of centers/balls
$k$ is a “hard restriction”. These problems therefore have a different flavor.

Finally, $k$-center and $k$-median have been generalized in an orthogonal
direction, where there are additional constraints on the centers [12, 7, 5].
Again, the issues studied in these generalizations tend to be quite different
from the ones we confront here.

###  1.2 Our Results

We study the colorful $k$-center problem when the number of colors is a
constant. Our main result is a randomized polynomial time algorithm that, with
high probability, outputs an $O(1)$-approximation in the Euclidean plane. (As
$k$-center is APX-hard even in the plane [9], we cannot hope for a PTAS.)

To describe our approach, we focus on the case with two colors. We first
design a pseudo-approximation algorithm that outputs a $2$-approximation, but
with $k+1$ centers instead of $k$. This result holds in any metric space, not
just the Euclidean plane. To obtain it, we preprocess the solution to a
natural LP-relaxation into a solution for a simpler LP, using ideas from [4,
13]. We then note that a basic feasible solution to the simple LP opens at
most $k+1$ centers fractionally. A pseudo-approximation for $k$-median with
outliers was an important step in the recent work of Krishnaswamy et al. [19].

The pseudo-approximation allows us to reduce the colorful $k$-center problem
to a special case where the balls in the optimal solution are separated – the
distance between any two balls is much greater than their radii. Designing an
$O(1)$-approximation for this special case is challenging, even in the plane.
For instance, partitioning into small subproblems by using a grid (such as in
[14]) or other type of object does not work, because any such partitioning may
intersect balls in the optimal solution, and we have a hard bound $k$ on the
number of balls allowed.

We solve separated instances in the plane by reducing to exact perfect
matching on graphs. In this problem, we are given a graph in which each edge
has a red weight and a blue weight, both non-negative integers. Given integers
$w_{r}$ and $w_{b}$, the goal is to determine if the graph has a perfect
matching whose red and blue weights are, respectively, exactly $w_{r}$ and
$w_{b}$. This problem can be solved in randomized polynomial time, provided
the weights are bounded by a polynomial in the input size; see [3, 21]. To our
knowledge, this connection of geometric clustering and covering to exact
matching is a novel one.

In its current form, the reduction from separated instances of colorful
$k$-center to exact matching does not work even in $\mathbb{R}^{3}$.
Nevertheless, we are hopeful that this work will lead to an
$O(1)$-approximation to colorful $k$-center in dimensions $3$ and higher, and
indeed in any metric space.

Organization. We describe our pseudo-approximation in Section 2 and our
$O(1)$-approximation for the Euclidean plane in Section 3. In both these
sections, we focus on the case where the number of colors is $2$. We address
the extension of the planar result to multiple color classes in Section 4.

##  2 Pseudo-approximation via LP Rounding

Recall that an instance of colorful $k$-center is a metric space $(P=R\sqcup
B,d)$, where $R,B$ are non-empty, disjoint sets of red and blue points
respectively. We are also given red and blue coverage requirements $1\leq
r\leq|R|$ and $1\leq b\leq|B|$, respectively. A solution $(C,D)$, where
$C,D\subseteq P$, is said to be feasible, if (i) $|C|\leq k$, (ii) $|D\cap
R|\geq r$, and (iii) $|D\cap B|\geq b$. The cost of a solution is defined as
$\max_{j\in D}d(j,C)$. Any point in the set $D$ is said to be _covered_ by the
solution. The goal of the colorful $k$-center problem is to find a feasible
solution of the minimum cost.

In this section, we describe a pseudo-approximation algorithm for the colorful
$k$-center problem. That is, we show how to find a solution of cost at most
$2\cdot OPT$ using at most $k+1$ centers, where $OPT$ is the cost of an
optimal solution. This result is achieved in two steps. In the first step, we
use the natural LP relaxation for the decision version of the colorful
$k$-center problem, to partition the points in $P$ into disjoint clusters
using a simple greedy procedure. We also obtain a related fractional solution
during this clustering procedure. We use this to show that a much simpler LP
with a small number of constraints has a feasible solution, even though there
may not exist an integral feasible solution using at most $k$ centers.
Nevertheless, we use the simplicity of the LP to show that there exists a
solution using at most $k+1$ centers.

Find a feasible solution $(x,z)$ such that:
$\displaystyle\text{}\displaystyle\sum\limits_{i\in B(j,\rho)}x_{i}$
$\displaystyle\geq z_{j},\quad$ $\displaystyle\forall j\in P$ (1)
$\displaystyle\displaystyle\sum_{i\in P}x_{i}$ $\displaystyle\leq k,$ (2)
$\displaystyle\displaystyle\sum_{j\in R}z_{j}$ $\displaystyle\geq r,$ (3)
$\displaystyle\displaystyle\sum_{j\in B}z_{j}$ $\displaystyle\geq b,$ (4)
$\displaystyle\displaystyle z_{j},x_{i}$ $\displaystyle\in[0,1],\quad$
$\displaystyle\forall i,j\in P$ (5) Figure 1: The feasibility LP,
parameterized by $\rho$

Let $\rho$ denote our “guess” for the optimal cost. Note that the optimal cost
must be one of the $O(n^{2})$ interpoint distances, therefore there are
$O(n^{2})$ choices for $\rho$. We state the feasibility LP, parameterized by
$\rho$, in Figure 1. It is easy to see that an optimal solution satisfies all
the constraints when the guess $\rho$ is correct (i.e., when $\rho\geq OPT$).
Therefore, henceforth, we assume that $\rho=OPT$.

Now, we find a feasible fractional solution $(x^{\prime},z^{\prime})$ for this
LP, and use it to show that a related, but a much simpler LP is feasible. To
this end, we use the following “greedy clustering” procedure (see Algorithm
1), which also computes a modified LP solution $(\tilde{x},\tilde{z})$. Let
$P^{\prime}$ denote the set of unclustered points, initialized to $P$. We also
initialize $S$, the collection of cluster-centers, to the empty set. In each
iteration, we find a point $j\in P^{\prime}$ with the maximum $z_{j}$. We set
$\tilde{z}_{j}=\tilde{x}_{j}\leftarrow\min\\{1,\sum_{i\in
B(j,\rho)}x^{\prime}_{i}\\}$ – note that the sum is over all points in the
ball $B(j,\rho)$, as opposed to the points in $B(j,\rho)\cap P^{\prime}$. Let
$C_{j}$ denote the set of unclustered points within distance $2\rho$ from $j$.
We refer to the set $C_{j}$ as a cluster. We set
$\tilde{z}_{j^{\prime}}\leftarrow\tilde{z}_{j}$ for all other points
$j^{\prime}\in C_{j}\setminus\\{j\\}$. Finally, we remove the points in
$C_{j}$ from $P^{\prime}$ and repeat this process until all points are
clustered, i.e., $P^{\prime}$ becomes empty.

Algorithm 1 Clustering Algorithm

1:$S\leftarrow\emptyset$, $P^{\prime}\leftarrow P$

2:while $P^{\prime}\neq\emptyset$ do

3: $j\in P^{\prime}$ be a point with maximum $z^{\prime}_{j}$; let
$S\leftarrow S\cup\\{j\\}$

4: $\tilde{x}_{j}\leftarrow\min\\{1,\sum_{i\in B(j,\rho)}x^{\prime}_{i}\\}$;
$\tilde{z}_{j}\leftarrow\tilde{x}_{j}$

5: $C_{j}\leftarrow B(j,2\rho)\cap P^{\prime}$

6: For all $j^{\prime}\neq j\in C_{j}$, set $\tilde{x}_{j^{\prime}}\leftarrow
0,\tilde{z}_{j^{\prime}}\leftarrow\tilde{z}_{j}$

7: $P^{\prime}\leftarrow P^{\prime}\setminus C_{j}$

8:end while

For any point $i\in S$, let $R_{i}\coloneqq R\cap C_{i}$ and $B_{i}\coloneqq
B\cap C_{i}$ denote the sets of red and blue points in the “cluster” $C_{i}$
respectively. Additionally, for any $i\in S$, let $r_{i}$ and $b_{i}$ denote
the sizes of the sets $R_{i}$ and $B_{i}$ respectively. We start with a few
simple observations that are immediate from the description of the procedure.

######  Observation .

  1. 1.

The “clusters” $\\{C_{i}\\}_{i\in S}$ partition the point set $P$. Therefore,
$\\{R_{i}\\}_{i\in S}$ partition the red points $R$, and $\\{B_{i}\\}_{i\in
S}$ partition the blue points $B$,

  2. 2.

For any two distinct $i,i^{\prime}\in S$, $d(i,i^{\prime})>2\rho$,

  3. 3.

For any $j\in P$, there is at most one $i\in S$, such that $d(i,j)\leq\rho$.

The following observation follows from the greedy nature of the clustering
procedure.

######  Observation .

For any point $j_{1}\in P$, let $j\in S$ be the point in $S$ such that
$j_{1}\in C_{j}$. Then, $\tilde{z}_{j}=\tilde{z}_{j_{1}}\geq
z^{\prime}_{j_{1}}$

###### Proof.

Notice that, $\tilde{z}_{j_{1}}=\tilde{z}_{j}=\min\\{1,\sum_{i\in
B(j,\rho)}x^{\prime}_{i}\\}$. There are two cases to consider.

$\tilde{z}_{j_{1}}=\tilde{z}_{j}=1\geq z^{\prime}_{j_{1}}$, where the
inequality follows from the constraint (5) of the LP.

Otherwise, $\tilde{z}_{j}=\sum_{i\in B(j,\rho)}x^{\prime}_{i}$. In this case,
$\tilde{z}_{j}=\sum_{i\in B(j,\rho)}x^{\prime}_{i}\geq z^{\prime}_{j}\geq
z^{\prime}_{j_{1}}$. Here, the first inequality follows from constraint (1) of
the LP, and the second inequality follows from the fact that in the iteration
when $j_{1}$ was removed from $P^{\prime}$, $j\in P^{\prime}$ was chosen to be
a point with the maximum $z^{\prime}$-value in line 3. ∎

The next two claims help us construct a feasible solution to a simplified LP,
to be introduced later.

######  Claim 1.

  1. 1.

$\sum_{i\in S}r_{i}\tilde{x}_{i}\geq r$

  2. 2.

$\sum_{i\in S}b_{i}\tilde{x}_{i}\geq b$

######  Proof 2.1.

We prove the first part of the claim – the second part is analogous.

$\displaystyle\sum_{i\in S}r_{i}\tilde{x}_{i}$ $\displaystyle=\sum_{i\in
S}|R_{i}|\cdot\tilde{x}_{i}$ $\displaystyle=\sum_{i\in S}\sum_{j^{\prime}\in
R_{i}}\tilde{z}_{i}$ (For any $i\in S,\tilde{x}_{i}=\tilde{z}_{i}$ by
construction) $\displaystyle\geq\sum_{i\in S}\sum_{j^{\prime}\in
R_{i}}z^{\prime}_{j^{\prime}}$ (For any $j^{\prime}\in R_{i}\subseteq
C_{i},\tilde{z}_{i}\geq z^{\prime}_{j^{\prime}}$ from Observation 2)
$\displaystyle=\sum_{j\in R}z^{\prime}_{j}$ (Property 1 of Observation 2)
$\displaystyle\geq r$ (By constraint (3))

######  Claim 2.

$\sum_{i\in S}\tilde{x}_{i}\leq k$

######  Proof 2.2.

$\displaystyle\sum_{i\in S}\tilde{x}_{i}$ $\displaystyle\leq\sum_{i\in
S}\sum_{i^{\prime}\in B(i,\rho)}x^{\prime}_{i^{\prime}}$
($\tilde{x}_{i}\leq\sum_{i^{\prime}\in B(i,\rho)}x^{\prime}_{i^{\prime}}$)
$\displaystyle\leq\sum_{i^{\prime}\in P}x^{\prime}_{i^{\prime}}$ (From
Property 3 of Observation 2) $\displaystyle\leq k$ (By constraint (2))

###  2.1 A Simplified Problem

Recall that the clusters $\\{C_{j}\\}_{j\in S}$ are disjoint, and have radius
$2\rho$. Now, if we can find a collection of $k$ clusters from this set, that
cover at least $r$ red points and $b$ blue points, then this immediately leads
to a $2$-approximation. Unfortunately, it is not always possible to find such
a collection. However, in the following, we show that we can find a collection
of $k+1$ clusters that satisfies the coverage requirements of both colors. The
LP in Figure 2 is a relaxation of the problem of finding at most $k$ clusters
that satisfy the coverage requirements of both colors.

maximize $\displaystyle\sum\limits_{i\in S}r_{i}x_{i}$ subject to
$\displaystyle\sum\limits_{i\in S}b_{i}x_{i}\geq b$ (6)
$\displaystyle\displaystyle\sum_{i\in S}\ x_{i}\ \leq k,$ (7)
$\displaystyle\qquad x_{i}\in[0,1],\quad$ $\displaystyle\forall i\in S$ (8)
Figure 2: The Simplified LP

Note that Claims 1 and 2 imply that the fractional solution $(\tilde{x})$
constructed above is a feasible solution for this LP, and has objective value
at least $r$. However, there may not exist a feasible integral solution that
uses at most $k$ clusters from the set $\\{C_{i}\\}_{i\in S}$. The following
example illustrates this.

######  Example 2.3.

In the following figure, we have two clusters $C_{1}$ and $C_{2}$. Red points
are shown as boxes, whereas blue points are shown as dots. $C_{1}$ consists of
$3$ red points and $1$ blue point, whereas $C_{2}$ contains $3$ blue points
and $1$ red point. Suppose that $k=1$ and the coverage requirements of each
color class is $2$. Now, assigning $x_{1}=x_{2}=0.5$ yields a fractional
solution that satisfies the coverage requirements of each color class.
However, assuming that the distance between two clusters is very large
compared to the radii, $2\rho$, it can be seen that there is no feasible
integral solution of cost at most a constant multiple of $2\rho$.

Nevertheless, we show in the following that there exists a feasible solution
that uses at most $k+1$ clusters. First, we need the following classical
result from linear algebra (see Lemma 2.1.4 in [20]).

######  Lemma 2.4 ([20]).

In any extreme point feasible solution (or equivalently, a basic feasible
solution) to a linear program, the number of linearly independent tight
constraints is equal to the number of variables.

Furthermore, an extreme point optimal solution can be computed in polynomial
time. Now, we find such an optimal solution $(x^{*})$ to the simplified LP. It
follows from Claim 1 that its objective value is at least $r$. We prove the
following lemma, which is a simple consequence of Lemma 2.4.

######  Lemma 2.5.

The number of $x^{*}$-variables in an extreme point optimal solution that are
strictly fractional, is at most $2$. Therefore, the number of strictly
positive variables is at most $k+1$.

######  Proof 2.6.

Let $m\coloneqq|S|$ denote the number of variables. From Lemma 2.4, it follows
that the number of linearly independent tight constraints is equal to $m$.
Note that, even though there are $2m+2$ constraints in the LP, at most $m+2$
constraints can be simultaneously tight. Now, even if constraints (6) and (7)
are tight, it follows that number of tight constraints from
$(\ref{constr:fractional-x})$ is at least $m-2$. That is, the number of
strictly fractional variables is at most $2$.

If there are $k$ variables that are equal to $1$, then constraint (7) is
tight, and there are no strictly fractional variables. Otherwise, the number
of variables equal to $1$, is at most $k-1$. Along with at most $2$ strictly
fractional variables, the number of positive variables is at most $k+1$.

Note that the red and blue coverage can only increase while rounding up the
fractional variables to $1$. If there is exactly one fractional variable, we
round it up, giving a $2$-approximation using exactly $k$ centers. Otherwise,
let $x^{*}_{1},x^{*}_{2}$ be the two fractional variables, corresponding to
clusters $C_{1},C_{2}$ respectively. Note that, although the fractional
solution satisfies both red and blue coverage, adding only $C_{1}$ or $C_{2}$
to the solution may not satisfy coverage demands for both colors – recall
Example 2.3. Therefore, we include both clusters in the solution, resulting in
a pseudo-approximation of cost at most $2\rho$, using at most $k+1$ centers.
We summarize the result of this section in the following theorem.

######  Theorem 2.7.

There exists a polynomial time algorithm to find a $2$-approximation for the
colorful $k$-center problem (with two colors) in any metric space, using at
most $k+1$ centers.

This theorem generalizes readily to an arbitrary number of color classes
$c\geq 2$. Having $c$ color classes corresponds to having $c-1$ constraints
instead of constraint (6) in the corresponding Simplified LP. As we now have
constraints corresponding to $c-1$ color classes, we obtain the following
lemma for the Simplified LP, the proof of which goes along the same lines as
that of Lemma 2.5.

######  Lemma 2.8.

The number of $x^{*}$-variables in an extreme point optimal solution that are
strictly fractional, is at most $c$. Therefore, the number of strictly
positive variables is at most $k+c-1$.

Therefore, if we round up these fractional variables, we get a pseudo-
approximation of cost at most $2\cdot\rho$, using at most $k+c-1$ centers.

##  3 A Constant Approximation Algorithm in $\mathbb{R}^{2}$

In this section, we describe a constant approximation algorithm for the
colorful $k$-center problem with two color classes, red and blue, where the
set of points lies in the Euclidean plane. Recall that $P=R\sqcup B$ denotes
the input set of $n$ points, and $r$ and $b$ the red and blue coverage
requirements. Our algorithm consists of two subroutines which we describe in
the following two subsections. The two subroutines are intended to handle two
different types of instances. In order to describe these instances we need the
following definitions.

######  Definition 3.1.

Let $\alpha>0$ be a parameter. A set $S$ of balls of radius $\rho^{\prime}$ is
$\alpha$-separated if the distance between the centers of every two balls in
$S$ is greater than $\alpha\cdot\rho^{\prime}$. An instance of colorful
$k$-center is $\alpha$-separated if the set of balls in some optimal solution
is $\alpha$-separated.

The first subroutine (described in Section 3.1) gives a
$2(\alpha+1)$-approximation algorithm for instances that are not
$\alpha$-separated. The second subroutine (described in Section 3.2) gives a
$(0.5\alpha+2)$-approximation algorithm for $\alpha$-separated instances where
$\alpha>4/\gamma$ for some absolute constant $\gamma>0$, which is defined
below.

Therefore for a large enough constant $\alpha$, we get a
$\max\\{2(\alpha+1),0.5\alpha+2\\}$-approximation algorithm for the colorful
$k$-center problem with two color classes. From the geometric arguments in
Section 3.2 that determine $\alpha$, it is apparent that taking
$\alpha=8+\epsilon^{\prime}$ for any $\epsilon^{\prime}>0$ is sufficient.
Therefore, the approximation guarantee of our algorithm is $17+\epsilon$ for
any $\epsilon>0$.

###  3.1 Handling Non-Separated Instances

If an instance is not $\alpha$-separated, we can use the pseudo-approximation
algorithm of Section 2 to immediately get a $2(\alpha+1)$-approximation
algorithm. This is formalized in the following lemma. It is worth pointing out
that this subroutine does not require the set of points to be in
$\mathbb{R}^{2}$ – it works for any metric.

######  Lemma 3.2.

If an instance is not $\alpha$-separated then we get a
$2(\alpha+1)$-approximate solution to the colorful $k$-center problem in
polynomial time.

######  Proof 3.3.

Let the optimal radius be $\rho$. Since the instance is not
$\alpha$-separated, there are two balls in some optimal solution whose centers
are within distance $\alpha\cdot\rho$ of each other. Let $C_{1}$ and $C_{2}$
be two such balls in the optimal solution. We replace $C_{1}$ with a ball of
radius $(\alpha+1)\rho$ centered at the same point as $C_{1}$. This allows us
to remove $C_{2}$ without violating any of the coverage requirements (since
the new ball replacing $C_{1}$ covers all points originally covered by
$C_{2}$). This means that there exists a feasible solution using $k-1$ centers
with cost $(\alpha+1)\rho$. Therefore, if we run the pseudo-approximation
algorithm of the previous section with number of centers being $k-1$, we will
get a solution using at most $k$ centers having cost $2(\alpha+1)\rho$, which
proves the lemma.

###  3.2 Reduction of Separated Instances to Exact Perfect Matching

Let us assume that the instance we are given is $\alpha$-separated for some
$\alpha>4/\gamma$ for some absolute constant $\gamma>0$. From the proof of
Lemma 3.4, it will be clear that taking $\alpha>8$ is sufficient. The
$\alpha$-separability of the instance helps us design a
$(0.5\alpha+2)$-approximation algorithm for this problem in $\mathbb{R}^{2}$.
We do this by reducing the problem to the _Exact Perfect Matching_ problem
[22, 2]. In the exact perfect matching problem we are given an edge-weighted
graph $G=(V,E)$ and a target weight $W$. The goal is to find a perfect
matching in $G$ having weight _exactly_ $W$. The result in [3, 21] gives a
randomized pseudo-polynomial algorithm for exact perfect matching. In other
words, their algorithm runs in polynomial time if the largest edge weight in
the input graph is bounded by a polynomial in $|V|$. We now describe our
reduction from the $k$-center problem to exact perfect matching.

We first assume that we have guessed correctly the radius $\rho$ of an optimal
solution to the given instance. We cover $\mathbb{R}^{2}$ with a grid of
equilateral triangles of side length $\ell=0.5\alpha\rho$. See Figure 3 for an
illustration. Consider the following three lines through the origin: $L_{1}$
is the $x$-axis, $L_{2}$ has angle $60$ degrees with $L_{1}$, and $L_{3}$ has
angle $120$ degrees with $L_{1}$. The grid of side length $\ell$ can be
formally defined as the arrangement of the collection of lines parallel to
$L_{1}$, $L_{2}$, and $L_{3}$, with two adjacent parallel lines having
distance $\sqrt{3}\ell/2$. We can interpret the grid as an infinite graph
where the edges are the sides of each atomic triangle in the grid and the
vertices are the intersection points of the edges.

Define the _Voronoi region of an edge_ $e$ as the set of points that are at
least as close to $e$ as any other edge. It is easy to see that the Voronoi
region of $e$ is a rhombus whose four end points are the two end points of $e$
and the centroids of the two triangles sharing the edge $e$. We are interested
in the _extended Voronoi region of an edge_ $e$ which is the Minkowski sum of
the Voronoi region of $e$ and a ball of radius $\rho$ centered at the origin.

Figure 3: Here, we show a triangular grid of side $\ell=0.5\alpha\rho$. We
also show the Voronoi region of the edge $e$ (the area inside the dash-dotted
rhombus around $e$), and the extended Voronoi region of $e$ (the area inside
the lightly shaded object). We also show the Voronoi regions of the
“neighboring edges” that do not share a vertex with $e$ as dashed rhombuses.
Notice that the Voronoi regions (resp. extended Voronoi regions, not shown for
simplicity) of the neighboring edges do not intersect with the Voronoi region
(resp. extended Voronoi region) of $e$. We use this fact in the proof of Lemma
3.4. Notice that, the extended Voronoi region of $e$ contains $2$ red points
and $4$ blue points. Therefore, we will set the weight of the edge to be
$4\cdot N^{2}+2$.

######  Lemma 3.4.

The extended Voronoi regions of two edges $e$ and $e^{\prime}$ intersect each
other iff $e$ and $e^{\prime}$ share a common vertex.

######  Proof 3.5.

The reverse direction of the lemma is trivial, so we focus on the forward
direction. Take two edges $e$ and $e^{\prime}$ that are not incident on a
common vertex. Note that their Voronoi regions do not intersect (see Figure
3). Thus, there is an absolute constant $\gamma>0$ such that the distance
between the closest pair of points, one in each region, is at least
$\gamma\cdot\ell=\gamma\cdot 0.5\alpha\rho$. Therefore, if $\alpha>4/\gamma$,
the distance between the two Voronoi regions is greater than $2\rho$. 111With
simple geometric calculations, one can show that $\gamma=1/2$, which implies
that $\alpha>8$. Thus, the extended Voronoi regions of $e$ and $e^{\prime}$ do
not intersect because each Voronoi region “expands” by only an additive factor
of $\rho$.

For each edge define $P(e)$ as the set of points in $P$ that lie in the
extended Voronoi region of $e$. Let $G^{\prime}=(V^{\prime},E^{\prime})$ be
the graph where $E^{\prime}$ is the set of all grid edges such that
$P(e)\neq\emptyset$, and $V^{\prime}$ is the set consisting of the endpoints
of edges in $E^{\prime}$. Define $N=2\max\\{n,|V^{\prime}|\\}$, note that
$N=O(n)$ because each point can belong to at most six triangles. The weight of
an edge $e\in E^{\prime}$ is set to $w_{e}=N^{2}\cdot b_{e}+r_{e}$ where
$b_{e}$ and $r_{e}$ are the number of blue and red points respectively in
$P(e)$.

######  Lemma 3.6.

There exists a matching in $G^{\prime}$ with $k$ edges and with weight exactly
$b^{\prime}\cdot N^{2}+r^{\prime}$ for some $|B|\geq b^{\prime}\geq b$ and
$|R|\geq r^{\prime}\geq r$.

######  Proof 3.7.

Let $S^{*}$ be the set of balls in an optimal solution that is
$\alpha$-separated. For each ball $C_{i}\in S^{*}$, $1\leq i\leq k$, let
$e_{i}$ be any edge (from the infinite grid) such that the center of $C_{i}$
lies in the Voronoi region of $e_{i}$. Note that the extended Voronoi region
of $e_{i}$ contains $C_{i}$, and thus $e_{i}\in E^{\prime}$. We claim that if
$i\neq j$, then (a) $e_{i}\neq e_{j}$, and (b) $e_{i}$ and $e_{j}$ are not
incident on a common vertex of $V^{\prime}$. If either (a) or (b) does not
hold, the distance between the centers of $C_{i}$ and $C_{j}$ is at most
$0.5\alpha\rho+0.5\alpha\rho=\alpha\rho$, which violates the fact that the
instance is $\alpha$-separated. Therefore the set $M=\\{e_{i}|1\leq i\leq
k\\}$ is a matching of $k$ edges in $G$.

If we set $b^{\prime}$ and $r^{\prime}$ to be the total number of blue and red
points in the extended Voronoi regions of the $k$ edges, then we have a
matching of weight $b^{\prime}\cdot N^{2}+r^{\prime}$ in $G$. Since the
extended Voronoi regions cover all the points covered by $S^{*}$, we have
$b^{\prime}\geq b$ and $r^{\prime}\geq r$ which finishes the proof.

We now define a graph $G$ such that perfect matchings in $G$ correspond to
matchings with $k$ edges in $G^{\prime}$. To construct $G=(V,E)$, we start
with $G^{\prime}$ and add $|V^{\prime}|-2k$ auxiliary vertices that are
connected to all vertices of $G^{\prime}$ with edges of weight zero. We can do
this because Lemma 3.6 implies that $|V^{\prime}|\geq 2k$. Now $G$ obeys the
following property that is easy to prove.

######  Observation 3.7.

Any matching in $G^{\prime}$ of weight $W$ having exactly $k$ edges can be
extended to a perfect matching in $G$ of weight exactly $W$. Conversely, from
any perfect matching in $G$ with weight exactly $W$, we can obtain a matching
in $G^{\prime}$ with $k$ edges and weight exactly $W$.

Using Lemma 3.6 and Observation 3.2 we get the following Corollary.

######  Corollary 3.8.

There exists a perfect matching in $G$ of weight exactly $b^{\prime}\cdot
N^{2}+r^{\prime}$ for some $|B|\geq b^{\prime}\geq b$ and $|R|\geq
r^{\prime}\geq r$.

We now show how to go from a perfect matching in $G$ to a cover for the input
instance.

######  Lemma 3.9.

If $G$ has a perfect matching of weight exactly
$W=b^{\prime}N^{2}+r^{\prime}$, with $0\leq b^{\prime}\leq|B|$ and $0\leq
r^{\prime}\leq|R|$, then we can place exactly $k$ balls of radius
$(0.5\alpha+2)\rho$ that cover at least $r^{\prime}$ red points and at least
$b^{\prime}$ blue points.

######  Proof 3.10.

Suppose $G$ has a perfect matching $M$ of weight $W$. Using Observation 3.2,
we recover a matching $M^{\prime}$ in $G^{\prime}$ with $k$ edges and weight
$W$. For $e\in M^{\prime}$, let $b_{e}=|P(e)\cap B|$ and $r_{e}=|P(e)\cap R|$.
Thus, the weight $w_{e}$ for each edge $e$ is $b_{e}N^{2}+r_{e}$. It follows
that

$\left(\sum_{e\in M^{\prime}}b_{e}\right)N^{2}+\left(\sum_{e\in
M^{\prime}}r_{e}\right)=W=b^{\prime}N^{2}+r^{\prime}.$

By our choice of $N$, both $r^{\prime}$ and $\sum_{e\in M^{\prime}}r_{e}$ are
strictly less than $N^{2}$. It follows that $\sum_{e\in
M^{\prime}}r_{e}=r^{\prime}=W\text{ mod }N^{2}$, and furthermore $\sum_{e\in
M^{\prime}}b_{e}=b^{\prime}$. Furthermore, since $M^{\prime}$ is a matching,
by Lemma 3.4, the extended Voronoi regions of the edges in $M^{\prime}$ do not
intersect. Thus, $\cup_{e\in M^{\prime}}P(e)$ contains exactly $r^{\prime}$
red points and $b^{\prime}$ blue points.

For each $e\in M^{\prime}$ such that $P(e)\neq\varnothing$, we place a ball of
radius $(0.5\alpha+2)\rho$ centered at any point in $P(e)$. These at most $k$
balls cover all points in $\bigcup_{e\in M^{\prime}}P(e)$. This is because the
distance between any two points in $P(e)$ for an edge $e$ is at most
$(0.5\alpha+2)\rho$. This finishes the proof of the lemma.

We are now ready to state our algorithm for our $\alpha$-separated instance of
colorful $k$-center, assuming that we know the optimal radius $\rho$. We
construct the graph $G$ and check if it has a perfect matching of weight
exactly $W=b^{\prime}\cdot N^{2}+r^{\prime}$, for each $b\leq
b^{\prime}\leq|B|$ and $r\leq r^{\prime}\leq|R|$. For the check, we invoke the
algorithm of [3]. Corollary 3.8 ensures that for at least one of these guesses
for $W$, an exact perfect matching does exist, and the algorithm of [3]
returns it.222The algorithm of [3] is actually a randomized Monte-Carlo
algorithm, and thus has an error probability that can be made arbitrarily
small. For the sake of exposition, we ignore this eventuality of error, except
in the statement of our final result. Once we find an exact perfect matching
solution for any of these weight values, we convert it into a
$(0.5\alpha+2)$-approximate solution by invoking the algorithm of Lemma 3.9.
This completes our algorithm.

As we do not know the optimal radius for the given input instance, we will run
the above algorithm for each choice of $\rho$ from the set of $O(n^{2})$
interpoint distances induced by $P$. Fix a particular choice of $\rho$. If
there exists a feasible solution with balls of radius $\rho$ that is
$\alpha$-separated, then the above algorithm will return a feasible solution
with cost at most $(0.5\alpha+2)\cdot\rho$. If there is no feasible solution
with balls of radius $\rho$ that is $\alpha$-separated, then the above
algorithm may not return a feasible cover.

Overall, we simply return the minimum cost feasible solution that we encounter
after applying the above algorithm for all choices of $\rho$. This is a
$(0.5\alpha+2)$-approximation for $\alpha$-separated instances.

######  Remark 3.11.

We note that the algorithm described here generalizes to any constant number
of color classes, in the following sense. Suppose we have an input instance
for which there exists an $\alpha$-separated solution of cost $\rho^{\prime}$,
for some $\rho^{\prime}$. In particular, we do not assume that $\rho^{\prime}$
is the optimal cost for the input instance. Then the algorithm computes a
feasible solution of cost at most $(0.5\alpha+2)\cdot\rho^{\prime}$. Note that
in this case, for any edge $e$ of the graph $G^{\prime}$, the weight of each
edge will be of the form $\sum_{i\geq 0}P_{i}(e)N^{2i}$ where $P_{i}(e)$ is
the number of points of color class $i$ in the extended Voronoi region of that
edge.

###  3.3 Combining Separated and Non-Separated Cases

We do not know if a given instance of colorful $k$-center is
$\alpha$-separated or not. Therefore, we do not know which subroutine to use.
So we run both the subroutines and return the solution with the lowest cost.
We conclude with our main result.

######  Theorem 3.12.

There is a randomized polynomial time algorithm that, given any instance of
colorful $k$-center in the plane with two colors, outputs, with high
probability, an $O(1)$-approximate solution.

##  4 Multiple Color Classes in the Plane

So far we have only considered two color classes for the sake of keeping the
exposition simple. We now sketch an extension to the colorful $k$-center
problem in the plane with $c$ color classes for any integer constant $c$.

For a given instance in the plane, fix the optimal set of balls $S^{*}$, and
assume it has cost $\rho$. Let $S$ be any maximal $\alpha$-separated subset of
$S^{*}$. That is, for each pair of balls in $S$, the distance between the
centers is greater than $\alpha\cdot\rho$, whereas for every ball $B\in
S^{*}\setminus S$, there is a ball $B^{\prime}\in S$, such that the distance
between the centers of $B$ and $B^{\prime}$ is at most $\alpha\cdot\rho$. Let
$\bar{S}=S^{*}\setminus S$. We consider two cases:

#### Case 1: $|\bar{S}|\geq c-1$

Notice that if we expand each ball in $S$ to have radius
$(\alpha+1)\cdot\rho$, and discard the balls in $\bar{S}$, we obtain a
feasible solution with at most $k-(c-1)$ balls and cost $(\alpha+1)\cdot\rho$.
For this case, running the pseudo-approximation algorithm on the original
input, but with the number of centers set to $k-(c-1)$, will give us a
solution with $k$ balls and cost $2(\alpha+1)\cdot\rho$.

#### Case 2: $|\bar{S}|\leq c-2$

We guess the balls in $\bar{S}$. Because $|\bar{S}|\leq c-2$, and there are
$O(n^{2})$ choices for $\rho$, we have $O(n^{c})$ possibilities to guess from.
After guessing $\bar{S}$, we remove the points covered by $\bar{S}$, and
decrease the coverage requirement for each color class by the number of points
of that color class covered by $\bar{S}$. For this residual instance, $S$ is
an $\alpha$-separated solution with $k-|\bar{S}|$ balls and cost $\rho$. If we
run the algorithm of Section 3.2 on this residual instance, allowing
$k-|\bar{S}|$ centers, we obtain a cover with $k-|\bar{S}|$ balls and cost at
most $(0.5\alpha+2)\cdot\rho$. We output the union of this cover and
$\bar{S}$. This is a feasible solution to the original problem with $k$ balls
and cost $O(\rho)$.

The overall running time of the algorithm is $n^{O(c)}$.

##  5 Open Problems

One question raised by our work is whether an $O(1)$-approximation for
colorful $k$-center (with a constant number of colors) can be obtained in
$\mathbb{R}^{d}$ for $d\geq 3$, or indeed in an arbitrary metric space.
Another question is whether one can obtain an $O(1)$-approximation for non-
uniform $k$-center in the plane (with a constant number of distinct radii).

## References

  * [1] Suman K Bera, Shalmoli Gupta, Amit Kumar, and Sambuddha Roy.  Approximation algorithms for the partition vertex cover problem.  Theoretical Computer Science, 555:2–8, 2014.
  * [2] André Berger, Vincenzo Bonifaci, Fabrizio Grandoni, and Guido Schäfer.  Budgeted matching and budgeted matroid intersection via the gasoline puzzle.  Mathematical Programming, 128(1-2):355–372, 2011.
  * [3] Paolo M. Camerini, Giulia Galbiati, and Francesco Maffioli.  Random pseudo-polynomial algorithms for exact matroid problems.  Journal of Algorithms, 13(2):258–273, 1992.
  * [4] Deeparnab Chakrabarty, Prachi Goyal, and Ravishankar Krishnaswamy.  The non-uniform k-center problem.  In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016\.
  * [5] Deeparnab Chakrabarty and Maryam Negahbani.  Generalized center problems with outliers.  In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018\.
  * [6] 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, pages 642–651. Society for Industrial and Applied Mathematics, 2001.
  * [7] Danny Z Chen, Jian Li, Hongyu Liang, and Haitao Wang.  Matroid and knapsack center problems.  Algorithmica, 75(1):27–52, 2016.
  * [8] Ke Chen.  A constant factor approximation algorithm for k-median clustering with outliers.  In Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, pages 826–835. Citeseer, 2008.
  * [9] Tomás Feder and Daniel Greene.  Optimal algorithms for approximate clustering.  In Proceedings of the twentieth annual ACM symposium on Theory of computing, pages 434–444. ACM, 1988.
  * [10] Zachary Friggstad, Kamyar Khodamoradi, Mohsen Rezapour, and Mohammad R Salavatipour.  Approximation schemes for clustering with outliers.  ACM Transactions on Algorithms (TALG), 15(2):26, 2019.
  * [11] Teofilo F Gonzalez.  Clustering to minimize the maximum intercluster distance.  Theoretical Computer Science, 38:293–306, 1985.
  * [12] MohammadTaghi Hajiaghayi, Rohit Khandekar, and Guy Kortsarz.  Budgeted red-blue median and its generalizations.  In European Symposium on Algorithms, pages 314–325. Springer, 2010\.
  * [13] David G Harris, Thomas Pensyl, Aravind Srinivasan, and Khoa Trinh.  A lottery model for center-type problems with outliers.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017.
  * [14] Dorit S Hochbaum and Wolfgang Maass.  Approximation schemes for covering and packing problems in image processing and vlsi.  Journal of the ACM (JACM), 32(1):130–136, 1985.
  * [15] Dorit S Hochbaum and David B Shmoys.  A best possible heuristic for the k-center problem.  Mathematics of operations research, 10(2):180–184, 1985.
  * [16] Wen-Lian Hsu and George L Nemhauser.  Easy and hard bottleneck location problems.  Discrete Applied Mathematics, 1(3):209–215, 1979.
  * [17] Tanmay Inamdar and Kasturi R. Varadarajan.  On the partition set cover problem.  CoRR, abs/1809.06506, 2018.  arXiv:1809.06506.
  * [18] Kamal Jain, Mohammad Mahdian, Evangelos Markakis, Amin Saberi, and Vijay V Vazirani.  Greedy facility location algorithms analyzed using dual fitting with factor-revealing lp.  Journal of the ACM (JACM), 50(6):795–824, 2003.
  * [19] Ravishankar Krishnaswamy, Shi Li, and Sai Sandeep.  Constant approximation for k-median and k-means with outliers via iterative rounding.  In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 646–659. ACM, 2018.
  * [20] Lap Chi Lau, Ramamoorthi Ravi, and Mohit Singh.  Iterative methods in combinatorial optimization, volume 46.  Cambridge University Press, 2011.
  * [21] Ketan Mulmuley, Umesh V Vazirani, and Vijay V Vazirani.  Matching is as easy as matrix inversion.  Combinatorica, 7(1):105–113, 1987.
  * [22] Christos H Papadimitriou and Mihalis Yannakakis.  The complexity of restricted spanning tree problems.  Journal of the ACM (JACM), 29(2):285–309, 1982.