Aggregating Inconsistent Information:

Ranking and Clustering

NIR AILON
Google Research, New York, NY

MOSES CHARIKAR
Princeton University, Princeton, NJ

AND
ALANTHA NEWMAN
DIMACS, Rutgers University, New Brunswick, NJ 23

Abstract. We address optimization problems in which we are given contradictory pieces of input
information and the goal is to find a globally consistent solution that minimizes the extent of dis-
agreement with the respective inputs. Specifically, the problems we address are rank aggregation, the
feedback arc set problem on tournaments, and correlation and consensus clustering. We show that
for all these problems (and various weighted versions of them), we can obtain improved approxima-
tion factors using essentially the same remarkably simple algorithm. Additionally, we almost settle a
long-standing conjecture of Bang-Jensen and Thomassen and show that unless NP⊆BPP, there is no
polynomial time algorithm for the problem of minimum feedback arc set in tournaments.
Categories and Subject Descriptors: F.2 [Theory of Computation]: Analysis of Algorithms and
Problem Complexity; G.2 [Mathematics of Computing]: Discrete Mathematics

The work of N. Ailon was done while he was at Princeton University, partly supported by a Princeton
University Honorific Fellowship.
M. Charikar was supported by a National Science Foundation (NSF) ITR grant CCR-0205594,
DOE Early Career Principal Investigator award DE-FG02-02ER25540, NSF CAREER award CCR-
0237113, and Alfred P. Sloan fellowship and a Howard B. Wentz Jr. Junior Faculty award.
The work of A. Newman was done while she was visiting Princeton University, supported by M.
Charikar’s Alfred P. Sloan fellowship.
Authors’ addresses: N. Ailon, Google NY, 4th Floor, 76 Ninth Avenue, New York NY 10011, e-mail:
nailon@[Link]; M. Charikar, Department of Computer Science, Princeton University, 35 Olden
Street, Princeton, NJ 08540, e-mail: moses@[Link]; A. Newman, DIMACS Center, CoRE
Building, 4th Floor, Rutgers University, 96 Frelinghuysen Road, Piscataway, NJ 08854, e-mail:
[Link]@[Link].
Permission to make digital or hard copies of part or all of this work for personal or classroom use is
granted without fee provided that copies are not made or distributed for profit or direct commercial
advantage and that copies show this notice on the first page or initial screen of a display along with the
full citation. Copyrights for components of this work owned by others than ACM must be honored.
Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, to redistribute
to lists, or to use any component of this work in other works requires prior specific permission and/or
a fee. Permissions may be requested from Publications Dept., ACM, Inc., 2 Penn Plaza, Suite 701,
New York, NY 10121-0701 USA, fax +1 (212) 869-0481, or permissions@[Link].
C 2008 ACM 0004-5411/2008/10-ART23 $5.00 DOI 10.1145/1411509.1411513 [Link]
10.1145/1411509.1411513

Journal of the ACM, Vol. 55, No. 5, Article 23, Publication date: October 2008.
23:2 N. AILON ET AL.

General Terms: Algorithms, Theory

Additional Key Words and Phrases: Rank aggregation, consensus clustering, correlation clustering,
minimum feedback arc-set, tournaments
ACM Reference Format:
Ailon, N., Charikar, M., and Newman, A. 2008. Aggregating inconsistent information: Ranking and
clustering. J. ACM 55, 5, Article 23 (October 2008), 27 pages. DOI = 10.1145/1411509.1411513
[Link]

1. Introduction
The problem of aggregating inconsistent information from many different sources
arises in numerous contexts and disciplines. For example, the problem of ranking a
set of contestants or a set of alternatives based on possibly conflicting preferences
is a central problem in the areas of voting and social choice theory. Combining k
different complete ranked lists on the same set of n elements into a single ranking,
which best describes the preferences expressed in the given k lists, is known as the
problem of rank aggregation. This problem dates back to as early as the late 18th
century when Condorcet and Borda each proposed voting systems for elections with
more than two candidates [Condorcet 1785; Borda 1781]. There are numerous ap-
plications in sports, databases, and statistics [Dwork et al. 2001a; Fagin et al. 2003]
in which it is necessary to effectively combine rankings from different sources.
Another example of aggregating information is the problem of integrating possibly
contradictory clusterings from existing data sets into a single representative cluster-
ing. This problem is known as consensus clustering or ensemble clustering and can
be applied to remove noise and incongruencies from data sets [Filkov and Skiena
2003] or combine information from multiple classifiers [Strehl 2002].
In the last half century, rank aggregation has been studied and defined from
a mathematical perspective. In particular, Kemeny proposed a precise criterion
for determining the “best” aggregate ranking [Kemeny 1959; Kemeny and Snell
1962].1 Given n candidates and k permutations of the candidates, {π1 , π2 , . . . , πk },
a Kemeny optimal ranking of the candidates is the ranking π that minimizes a

“sum of distances”, ik d(π, πi ), where d(π j , πk ) denotes the number of pairs
of candidates that are ranked in different orders by π j and πk .2 For example, if
π j = (1, 2, 3, 4) and πk = (2, 3, 1, 4), then d(π j , πk ) = 2 since elements 1 and 2
appear in different orders in the two rankings as do elements 1 and 3. In other words,
a Kemeny optimal ranking minimizes the number of pairwise disagreements with
the given k rankings. Throughout this article we will refer to the problem of finding
a Kemeny optimal ranking as RANK-AGGREGATION.
More recently, RANK-AGGREGATION has been studied from a computational per-
spective. Finding a Kemeny optimal ranking is NP-hard [Bartholdi et al. 1989]
and remains NP-hard even when there are only four input lists to aggregate
[Dwork et al. 2001a]. This motivates the problem of finding a ranking that ap-
proximately minimizes the number of disagreements with the given input rankings.
Several 2-approximation algorithms are known [Diaconis and Graham 1977; Dwork

1
Historically known as Kemeny aggregation.
The distance function d(·, ·) is in fact a distance function and is known as the Kendall tau distance.
2

Journal of the ACM, Vol. 55, No. 5, Article 23, Publication date: October 2008.
Aggregating Inconsistent Information: Ranking and Clustering 23:3

et al. 2001a]. In fact, if we take the best of the input rankings, then the number of
disagreements between this ranking and the k input rankings is no more than twice
optimal.
The feedback arc set problem on tournaments is closely related to the RANK-
AGGREGATION problem. A tournament is a directed graph G = (V, A) such that
for each pair of vertices i, j ∈ V , either (i, j) ∈ A of ( j, i) ∈ A. The minimum
feedback arc set is the smallest set A ⊆ A such that (V, A − A ) is acyclic. The
size of this set is exactly the minimum number of backward edges induced by
a linear ordering of V . Throughout the article, we refer to this problem as FAS-
TOURNAMENT. This problem turns out to be useful in studying RANK-AGGREGATION,
but is also interesting in its own right. For example, imagine a sports tournament
where each player plays against every other player once: How should we rank
the players based on these possibly non-transitive (inconsistent) outcomes? The
complementary problem to finding a minimum feedback arc set is the maximum
acyclic subgraph problem, also known as the linear ordering problem. RANK-
AGGREGATION can be cast as a special case of weighted FAS-TOURNAMENT, where
the objective is to minimize the total weight of backward edges in a linear order of
the vertices. When the weight of edge (i, j) is the fraction of input rankings that
order i before j, solving RANK-AGGREGATION is equivalent to solving this weighted
FAS-TOUR-NAMENT instance.
The last problem we consider is that of clustering objects based on complete
but possibly conflicting pairwise information. An instance of this problem can be
represented by a graph with a vertex for each object and an edge labeled (+) or
(−) for each pair of vertices, indicating that two elements should be in the same
or different clusters, respectively. The goal is to cluster the elements so as to min-
imize the number of “−” edges within clusters and “+” edges crossing clusters.
This problem is known as CORRELATION-CLUSTERING (on complete graphs) [Bansal
et al. 2004]. A useful application of CORRELATION-CLUSTERING is optimally com-
bining the output of different machine learning classifiers [Bansal et al. 2004;
Strehl 2002]. Bansal et al. [2004] provide in-depth descriptions of other applica-
tions of CORRELATION-CLUSTERING. An analog to RANK-AGGREGATION is known as
CONSENSUS-CLUSTERING. In this problem, we are given k clusterings of the same
set of n elements. The goal is to find a clustering that minimizes the number of
pairwise disagreements with the given k clusterings. This problem can also be used
to optimally combine datasets. For example, CONSENSUS-CLUSTERING has been ap-
plied to the problem of integrating data resulting from experiments that measure
gene expression [Filkov and Skiena 2003].

1.1. PREVIOUS WORK. The minimum feedback arc set problem can be approx-
imated to within a factor of O(log n log log n) in general graphs [Even et al. 1998;
Seymour 1995] and has (at least) the same approximation hardness as the vertex
cover problem [Karp 1972], which is 1.36 [Dinur and Safra 2002]. More than a
decade ago, Bang-Jensen and Thomassen [1992] conjectured that FAS-TOURNAMENT
is NP-hard. However, for the past decade, no progress has been made on settling
this conjecture. In contrast, the minimum feedback vertex set problem on tourna-
ments is NP-hard [Speckenmeyer 1989] and is approximable to within 5/2 [Cai
et al. 2001].
We are not aware of any approximation for FAS-TOURNAMENT that improves on
the bound for the feedback arc set problem in general graphs. The complementary

Journal of the ACM, Vol. 55, No. 5, Article 23, Publication date: October 2008.
23:4 N. AILON ET AL.

maximization problem on tournaments has been studied; Arora et al. [1996] and
Frieze and Kannan [1999] gave PTASs for the maximum acyclic subgraph problem
in dense graphs, which implies a PTAS for the problem on tournaments. Inter-
estingly, since the appearance of the conference version of this work [Ailon et al.
2005], Kenyon-Mathieu and Schudy [2007] used the maximization PTAS as a main
component in a minimization PTAS. This significantly improves on the result in this
work for the ranking problems (in particular for RANK-AGGREGATION), since here
we guarantee only constant approximation factors. Neverthelss, our algorithms are
very simple and practical and more suitable for applications. Refer to Section 10
for a complete survey and comparison with followup work.
There are two well-known factor 2-approximation algorithms for sc Rank-Aggre-
gation. Since both RANK-AGGREGATION and CONSENSUS-CLUSTERING are equivalent
to finding the median of a set of points with a metric distance function, it easy to
see that choosing one of the given lists or given clusters at random, yields a 2-
approximation algorithm. We refer to these algorithms as PICK-A-PERM and PICK-
A-CLUSTER, respectively. The Spearman’s footrule distance  between two permuta-
tions πi and π j on n elements is defined to be: F(πi , π j ) = nk=1 |πi (k) − π j (k)|.
The footrule distance is no more than twice the Kemeny distance [Diaconis
and Graham 1977] and can be computed in polynomial time via a minimum
cost matching [Dwork et al. 2001a, 2001b]. These observations yield another
2-approximation.
CORRELATION-CLUSTERING has been studied both on general and complete graphs.
Both the minimization and maximization versions have been investigated. Bansal
et al. [2004] gave the first constant-factor approximation for the problem of min-
imizing disagreements on the complete graph. This factor was improved to 4
by rounding a linear program Charikar et al. [2003]. The weighted version of
CORRELATION-CLUSTERING, in which edges have fractional ± assignments has also
been studied. Each edge is assigned fractional values w ij+ and w ij− rather than a dis-
crete “+” or “−” label. When the edge weights satisfy the probability constraints
(i.e., w ij+ + w ij− = 1 for all edges), the best previous approximation factor was 7
[Gionis et al. 2005; Bansal et al. 2004]. When the edge weights satisfy the prob-
ability and the triangle inequality constraints (see Section 1.2), the best previous
approximation factor was 3 [Gionis et al. 2005]. CORRELATION-CLUSTERING on com-
plete graphs is MAX-SNP-hard [Charikar et al. 2003] and CONSENSUS-CLUSTERING
is NP-hard [Wakabayashi 1998]. However, CONSENSUS-CLUSTERING is not
known to be NP-hard if the number of input clusters is constant [Filkov and Skiena
2003].
1.2. OUR RESULTS. We give improved approximation algorithms for the fol-
lowing optimization problems:
—FAS-TOURNAMENT,
—RANK-AGGREGATION,
—CORRELATION-CLUSTERING, and
—CONSENSUS-CLUSTERING.
We show that they can all be approximated using essentially the same remarkably
simple algorithm. For example, the algorithm for FAS-TOURNAMENT, called KWIK-
SORT, is as follows: First, we pick a random vertex i to be the “pivot” vertex. Second,
we place all vertices connected to i with an in-edge on the left side of i and all

Journal of the ACM, Vol. 55, No. 5, Article 23, Publication date: October 2008.
Aggregating Inconsistent Information: Ranking and Clustering 23:5

vertices connected to i with an out-edge on the right side of i. We then recurse on

the two tournaments induced by the vertices on each side.
The analysis of KWIKSORT yields a 3-approximation algorithm for FAS-TOURNA-
MENT, improving on the best-known previous factor of O(log n log log n). Our anal-
ysis relies on a new technique for arguing a lower bound for FAS-TOURNAMENT by
demonstrating a fractional packing of edge disjoint directed triangles. The KWIK-
SORT algorithm is presented in Section 3, in which we introduce the basic ideas
we use throughout the article. In Section 4, we extend these ideas to approximate
weighted FAS-TOURNAMENT.
We further extend our techniques to RANK-AGGREGATION in Section 5. We con-
vert the RANK-AGGREGATION instance into a weighted FAS-TOURNAMENT instance,
which we convert to an unweighted FAS-TOURNAMENT instance using the major-
ity tournament (see Definition 2.1), and we then run KWIKSORT on this majority
tournament. Although this algorithm by itself is yet another 2-approximation, the
following is an 11/7-approximation: run both KWIKSORT and PICK-A-PERM and
output the best solution. This improved approximation ratio is due to the fact that
each algorithm does well on instances in which the other algorithm does poorly.
A simple lower bound on the value of an optimal solution for the weighted
FAS-TOURNAMENT is to take the sum over all vertices i < j of min{w ij , w ji }. In
contrast, our analysis uses a stronger lower bound based on the weight of directed
triangles (“bad triangles”) in the majority tournament. Interestingly, the analysis
of our simple combinatorial algorithm bounds the integrality gap of a natural LP
relaxation for FAS-TOURNAMENT. In fact, it demonstrates an LP dual solution based
on probabilities of random events occurring during the execution.
For CORRELATION-CLUSTERING and CONSENSUS-CLUSTERING, we present similar
combinatorial algorithms and analyses, with a different notion of “bad triplets”.
Interestingly, this gives results that are analogous to the results for FAS-TOURNA-
MENT and RANK-AGGREGATION and improve upon previously known approxima-
tion factors. We discuss CORRELATION-CLUSTERING and CONSENSUS-CLUSTERING in
Section 6.
Our analysis is applied to various cases of weighted FAS-TOURNAMENT (resp.
weighted CORRELATION-CLUSTERING). More precisely, we analyze the following
cases:
(i) Probability Constraints: w ij + w ji = 1 (respectively, w ij+ + w ij− = 1) for all
i, j ∈ V .
(ii) Triangle Inequality: w ij ≤ w ik + w kj (respectively, w ij− + w jk− ≤ w jk− ) for all
i, j, k ∈ V .
(iii) Aggregation: Edge weights are a convex combination of actual permutations
(respectively, clusters). Constraints (i) and (ii) are implied in this case.
As indicated, in instances of weighted FAS-TOURNAMENT that correspond to RANK-
AGGREGATION, the edge weights obey both the probability constraints and triangle
inequality, although these instances corresponding to RANK-AGGREGATION are even
more restricted.
Table I summarizes the approximation factors we achieve for the different sce-
narios with the combinatorial algorithms. Additionally, we consider LP relaxations
for FAS-TOURNAMENT and CORRELATION-CLUSTERING. After choosing a pivot vertex,
instead of deterministically placing vertices on the right or left side (in KWIKSORT),

Journal of the ACM, Vol. 55, No. 5, Article 23, Publication date: October 2008.
23:6 N. AILON ET AL.

TABLE I. THE PREVIOUS BEST-KNOWN FACTORS ARE SHOWN IN PARENTHESES

Ordering Clustering Ordering-LP Clustering-LP
Unweighted Instances 3∗ 3 (4† ) 5/2 5/2
Probability Constraints (i) 5∗ 5(9†† ) 5/2 5/2
Triangle Inequality (ii) 2∗ N/A∗∗
Probability Constraints + 2∗ 2 (3†∗ ) 2 2
Triangle Inequality (i,ii)
Aggregation (iii) 11/7 (2) 11/7 (2) 4/3 4/3
∗
The best-known factor was the O(log n log log n) algorithm [Even et al. 1998; Seymour
1995] for digraphs.
∗∗
Our techniques cannot directly be applied to weighted CORRELATION-CLUSTERING with
triangle inequality but no probability constraints.
†
Charikar et al. [2003].
††
Charikar et al. [2003], Bansal et al. [2004].
†∗
Gionis et al. [2005].

or in a cluster (in KWIKCLUSTER), we decide randomly based on LP values. This

results in vastly improved approximation factors.
Finally, we show that FAS-TOURNAMENT has no polynomial time algorithm as-
suming NPBPP. The question of NP-hardness of FAS-TOURNAMENT has been a
long-standing conjecture of Bang-Jensen and Thomassen [1992]. We show a ran-
domized reduction from the problem of finding a minimum feedback arc set in
general digraphs (which is known to be NP-hard) to the special case of tourna-
ments. This construction has been recently derandomized by Alon [2006], and
the conjecture is therefore proven completely. We present the weaker randomized
version here.
In Section 7, we extend our ideas to round LP’s for FAS-TOURNAMENT and
CORRELATION-CLUSTERING. In Section 8, we prove certain polynomial inequali-
ties that are stated in several lemmas in the preceding sections. In Section 9, we
prove hardness results for FAS-TOURNAMENT. In Section 10, we discuss work that
has appeared since the publication of the conference version of this work [Ailon
et al. 2005], and finally, in Section 11, we discuss open problems.

2. Preliminaries and Definitions

We study the following problems in this article. In what follows, we fix a ground
set V = {1, . . . , n}.

—FAS-TOURNAMENT (Minimum Feedback Arc Set in Tournaments). We are given

a tournament G = (V, A) (a digraph with either (i, j) ∈ A or ( j, i) ∈ A for
all distinct i, j ∈ V ). We want to find a permutation π on V minimizing the
number of pairs ordered pairs (i, j) such that i <π j and ( j, i) ∈ A (backward
edges with respect to π).3 In a weighted FAS-TOURNAMENT instance, we are given
weights w ij ≥0 for all ordered i, j ∈ V . We want to find a permutation π on V
minimizing i, j:i<π j w ji . Clearly, the unweighted case can be encoded as a 0/1
weighted case.

By i <π j we mean that π ranks i before j.

3

Journal of the ACM, Vol. 55, No. 5, Article 23, Publication date: October 2008.
Aggregating Inconsistent Information: Ranking and Clustering 23:7

—RANK-AGGREGATION. We are given a list of permutations (rankings) correspond-

ing to k voters π1 , .., πk on V . We want to find a permutation π minimizing the
k
sum of distances i=1 d(π, πi ), where d(π, ρ) is the number of ordered pairs
(i, j) such that i <π j but j <ρ i (the Kemeny distance).
—CORRELATION-CLUSTERING. Between any two unordered i, j ∈ V , we either have
a (+) or a (−) relation, indicating that i and j are similar or different, respectively.
We let E + (resp. E − ) denote the set of pairs i = j that are (+)-related (resp. (−)-
related). We want to find disjoint clusters C1 , . . . , Cm covering V and minimizing
the number of disagreement pairs ((+) pairs in different clusters or (−) pairs in
the same cluster). In a weighted CORRELATION-CLUSTERING instance, we assign
for each pair i, j two weights w ij+ ≥ 0 and w ij− ≥ 0. The cost of a clustering will
now be the sum of w ij+ over all i, j in different clusters, plus the sum of w ij− over
all i, j in the same cluster. Clearly, the unweighted case can be encoded as a 0/1
weighted case.
—CONSENSUS-CLUSTERING: We are given a list of clusterings corresponding to
k voters C1 , . . . , Ck of V , and we wish to find one clustering C that minimizes
k
i=1 d(C, Ci ), where the distance d(C, D) between two clusterings is the number
of unordered pairs i, j ∈ V that are clustered together by one and separated by
the other.

For a weighted FAS-TOURNAMENT instance, we will apply our algorithm for FAS-
TOURNAMENT on an unweighted graph to a majority tournament, which is an un-
weighted tournament that corresponds to the input weighted tournament. Similarly,
a weighted CORRELATION-CLUSTERING instance has a corresponding unweighted
majority instance.

Definition 2.1. Given an instance (V, w) of weighted FAS-TOURNAMENT, we

define the unweighted majority tournament G w = (V, Aw ) as follows: (i, j) ∈ Aw
if w ij > w ji . If w ij = w ji , then we decide (i, j) ∈ Aw or ( j, i) ∈ Aw arbitrarily.
Given an instance (V, w + , w − ) of weighted CORRELATION-CLUSTERING, we de-
fine the unweighted majority instance (V, E w+ , E w− ) as follows: (i, j) ∈ E w+ if
w ij+ > w ij− , and (i, j) ∈ E w− if w ij− > w ij+ . If w ij+ = w ij− , then we decide arbitrarily.

Note that although the majority instances depend on the weights of the weighted
instances, they are unweighted instances.
We will use (i, j, k) to denote the directed triangle (i → j, j → k, k → i). It
will be clear from the context whether a triangle is the set of its vertices or its edges.

3. Minimum Feedback Arc Set in Tournaments

Let G = (V, A) be a FAS-TOURNAMENT instance. We present the following algorithm
KWIKSORT for approximating it.
In our analysis, we will use the following notation. Let C OPT denote the cost of
an optimal solution. Let C KS denote the cost of KWIKSORT on G = (V, A).

THEOREM 3.1. KWIKSORT is a randomized algorithm for FAS-TOURNAMENT

with expected cost at most three times the optimal cost.

Journal of the ACM, Vol. 55, No. 5, Article 23, Publication date: October 2008.
23:8 N. AILON ET AL.

KWIKSORT(G = (V, A))

If V = ∅ then return empty-list

Set VL → ∅, VR → ∅.
Pick random pivot i ∈ V .

For all vertices j ∈ V \ {i}:

If ( j, i) ∈ A then
Add j to VL (place j on left side).
Else (If (i, j) ∈ A)
Add j to VR (place j on right side).

Let G L = (VL , A L ) be tournament induced by VL .

Let G R = (VR , A R ) be tournament induced by VR .

Return order KWIKSORT(G L ),i,KWIKSORT(G R ).

(Concatenation of left recursion, i, and right recursion.)

PROOF. We want to show that E[C KS ] ≤ 3C OPT . An edge (i, j) ∈ A becomes

a backward edge if and only if there exists a third vertex k such that (i, j, k)
form a directed triangle in G and k was chosen as a pivot when all three were
input to the same recursive call. Pivoting on k would then place i to its right and
j to its left, rendering edge (i, j) backward. In this case, we will charge a unit
cost of the backward edge (i, j) to the directed triangle (i, j, k). Let T denote the
set of directed triangles. For a directed triangle t ∈ T , denote by At the event that
one of its vertices is chosen as pivot when all three are part of the same recursive
call. Let pt denote the probability of event At . Now we observe, that a triangle t
is charged a unit cost exactly when At occurs, and it can be charged  at most once.
Therefore, the expected cost of KWIKSORT is exactly E[C KS ] = t∈T pt .
Clearly, if we had a set of edge disjoint triangles, then its cardinality would be
a lower bound for C OPT . This is also true fractionally: If {βt } t∈T is a system of
nonnegative weights on triangles in T such that for all e ∈ A, t:e∈t βt ≤ 1, then
C OPT ≥  t∈T βt . Indeed, consider the following LP relaxation for the problem:
minimize e∈A xe , subject to xe1 + xe2 + xe3 ≥ 1 for edge sets {e1 , e2 , e3 } ∈ T ,
and xe ≥ 0 for all e ∈ A. The solution to this LP clearly lower bounds C OPT . It is
easy to show that a packing {βt } is a feasible solution to the dual LP, hence a lower
bound on the optimal. Specifically, let C represent the set of directed cycles in G,
and let yc correspond to cycle c ∈ C. Then the dual LP is:

max yc
c∈C

∀e ∈ E, yc ≤ 1
c∈C :e∈c
0 ≤ yc ≤ 1.

We will demonstrate such a packing using the probabilities pt . Let t = (i, j, k)

be some triangle. Conditioned on the event At , each one of the 3 vertices of t was

Journal of the ACM, Vol. 55, No. 5, Article 23, Publication date: October 2008.
Aggregating Inconsistent Information: Ranking and Clustering 23:9

the breaking vertex with probability 1/3, because all vertices input to a recursive
call are chosen as pivot with equal probability. Therefore, any edge e = (i, j) of
t becomes a backward edge with probability 1/3 (still, conditioned on At ). More
formally, if we let Be denote the event that e becomes a backward edge, then
1
Pr [Be ∧ At ] = Pr [Be |At ] Pr [At ] =pt .
3
The event Be ∧ At means that the backwardness of edge e was charged to triangle
t to which it is incident. The main observation of this proof is as follows: for two
different triangles t, t  ∈ T sharing an edge e, the events Be ∧ At and Be ∧ At 
are disjoint. Indeed, an edge e can be charged to only one triangle t incident to e.
Therefore, for all e ∈ E,
1
pt ≤ 1 . (1)
t:e∈t 3

So { pt /3}t∈T is a fractional packing of T . Thus, C OPT ≥ t∈T pt /3 = E[C KS ]/3,
as required.

4. Minimum Feedback Arc Set in Weighted Tournaments

Let (V, w) be a weighted FAS-TOURNAMENT instance, where w ∈ (R+ )
n(n−1)
. We
suggest the following approximation algorithm: construct the unweighted majority
tournament G w = (V, Aw ) and return the ordering generated by KWIKSORT(G w ).
We analyze this algorithm.
For an edge e = (i, j) ∈ Aw , we let w(e) = w ij , and w(e) = w ji = 1 −
w(e) ≤ w(e). Fix an optimal solution π ∗ , and let c∗ (e) denote the cost incurred
to it by e =  (i, j) ∈ Aw , that is, c∗ (e) = w(e) if j <π ∗ i, else c∗ (e) = w(e).
∗
So C OPT
= e∈Aw c (e). Let T denote the set of directed triangles in G w . For
any t = (e1 , e2 , e3 ) ∈ T , we define c∗ (t) = c∗ (e1 ) + c∗ (e2 ) + c∗ (e3 ) and w(t) =
w(e1 ) + w(e2 ) + w(e3 ). Note that c∗ (t) is always less than w(t). Finally, let C KS
denote the cost the solution returned by KWIKSORT(V, G w ).
LEMMA 4.1. For an instance (V, w) of weighted FAS-TOURNAMENT, if there
exists a constant α > 0 such that w(t) ≤ αc∗ (t) for all t ∈ T , then E[C KS ] ≤ αC OPT ,
that is, KWIKSORT(G w ) is an expected α-approximation solution.
PROOF. Note that for any triangle t, any ordering will incur cost at most w(t)
on the edges of this triangle, whereas the optimal cost is c∗ (t). The assumption that
w(t) < αc∗ (t) means that we do not incur much more cost than the optimal solution.
In order to extend this to the whole graph, we generalize the triangle packing idea
presented in Section 3.
When KWIKSORT is run on G w , an edge e ∈ Aw is heavily charged if it becomes
a backward edge, and thus incurs the heavy cost w(e). It is lightly charged if it
incurs the light cost w(e). Clearly, e = (i, j) ∈ Aw is heavily charged if and only
if a third vertex k is chosen as pivot when all three i, j, k are in the same recursive
call, and (i, j, k) form a directed triangle in G w . We charge this cost to triangle
t = (i, j, k). Again, we consider the set T of directed triangles in G w , and their
corresponding events At with probability pt (see Section 3). Fix a triangle t ∈ T
with edges e1 , e2 , e3 . Conditioned on At , each of e1 , e2 and e3 are equally likely to

Journal of the ACM, Vol. 55, No. 5, Article 23, Publication date: October 2008.
23:10 N. AILON ET AL.

be heavily charged, so the expected charge of t is 13 pt w(t). The probability that an

edgee ∈ Aw does not incur a heavy cost (not charged to a triangle t ∈ T ) is exactly
1 − t:e∈t 13 pt . Therefore, E[C KS ] = B KS + F KS , where
1
B KS =
pt w(t)
3 t∈T
 
 1
F =
KS
1− pt w(e).
e∈Aw t:e∈t 3

We rearrange the sum C OPT = e∈T c∗ (e) as C OPT = B OPT + F OPT , where
1
B OPT = pt c∗ (t)
t∈T
3
 
 1
F OPT = 1− pt c∗ (e) .
e∈Aw t:e∈t 3

Notice that for all e ∈ Aw , the term (1− t:e∈t 31 pt ) is nonnegative (see Section 3).
Obviously, F KS ≤ F OPT , because w(e) ≤ c∗ (e) for any e ∈ Aw . Therefore, if for
some α > 0, w(t) ≤ αc∗ (t) for all t, then E[C KS ] ≤ αC OPT as required.
LEMMA 4.2. If the weights satisfy the probability constraints (w ij + w ji = 1),
then w(t) ≤ 5c∗ (t) for all t ∈ T . If the weights satisfy the triangle inequality
constraints (w ij ≤ w ik + w kj ), then w(t) ≤ 2c∗ (t).
PROOF. First assume probability constraints on the weights. In this case, we
claim that w(t) ≤ 5c∗ (t). Indeed, in this case, w(e) ≥ 1/2 for all e ∈ Aw , and
w(e) = 1 − w(e). Fix a triangle t containing edges e1 , e2 , e3 , and assume
1/2 ≤ w(e1 ) ≤ w(e2 ) ≤ w(e3 ) ≤ 1 . (2)
Clearly, w(t) = w(e1 ) + w(e2 ) + w(e3 ) ≤ 2 + w(e1 ). Any solution has to di-
rect at least one of the edges in t backwards, therefore c∗ (t) ≥ w(e1 ). Since
w(e1 ) ∈ [1/2, 1], we therefore have w(t) ≤ 5c∗ (t). Consequently, KWIKSORT has
an expected approximation ratio of at most 5 on weighted tournament instances
with probability constraints on the weights.
Now we assume that the edge weights satisfy the triangle inequality. Fix t ∈ T
with edge weights w(e1 ), w(e2 ), w(e3 ). By the triangle inequality,
w(e3 ) ≤ w(e1 ) + w(e2 )
w(e1 ) ≤ w(e2 ) + w(e3 ) (3)
w(e2 ) ≤ w(e3 ) + w(e1 )
Summing up, we get w(t) ≤ 2(w(e1 )+w(e2 )+w(e3 )). But c∗ (t) ≥ w(e1 )+w(e2 )+
w(e3 ), because the optimal solution must at least pay the lower cost at each edge.
This concludes the proof.
In the conference version [Ailon et al. 2005], a weaker bound of 3 was proven
for the triangle inequality constraints only case and 2 for the combined constraints.
This improvement in Lemma 4.2 is due to Warren Schudy.

Journal of the ACM, Vol. 55, No. 5, Article 23, Publication date: October 2008.
Aggregating Inconsistent Information: Ranking and Clustering 23:11

Combining Theorem 4.1 and Lemma 4.2, we get

THEOREM 4.3. Running algorithm KWIKSORT on G w gives an expected 5 and
2 approximation for the probability constraints case and the triangle inequality
constraints case, respectively.

5. An Improved Approximation Ratio for Rank Aggregation

Let {π1 , . . . , πk } be a RANK-AGGREGATION instance over some V . Consider the
corresponding equivalent weighted FAS-TOURNAMENT instance (V, w) (where w ij
is the fraction of inputs ranking i before j). Clearly, this weight system {w ij } is
a convex combination of acyclic tournaments. Therefore, by linearity, the edge
weights obey the probability constraints and the triangle inequality constraints.
Theorem 4.3 shows that we get a 2 approximation for this case, but the additional
structure in these instances allows us to improve upon this factor. As stated in
the introduction, there already exists a well-known 2-approximation algorithm for
RANK-AGGREGATION:

PICK-A-PERM({π1 , π2 , . . . πk })
Output a permutation πi chosen uniformly at random
from the input permutations.

(In practice, we can pick the permutation πi that minimizes the cost, but we use
the randomized version for the analysis.) Let C PAP denote the cost of PICK-A-PERM
on the RANK-AGGREGATION instance. Let G w = (V, Aw ) be the corresponding
unweighted majority tournament. Let z(e) = 2w(e)w(e), where w(e) and w(e) are
defined as in Section 4. We claim that

E[C PAP ] = z(e) . (4)
e∈Aw

Indeed, edge e ∈ Aw becomes a backward (respectively, forward) edge with proba-

bility w(e) (respectively, w(e)), in which case it incurs the cost of w(e) (respectively,
w(e)). For a directed triangle t = (e1 , e2 , e3 ) ∈ T , we let z(t) = z(e1 ) + z(e2 ) +
z(e3 ). The following theorem shows how to analyze a “convex combination” of
KWIKSORT and PICK-A-PERM:
THEOREM 5.1. If there exist constants β ∈ [0, 1] and γ > 0 such that
βw(t) + (1 − β)z(t) ≤ γ c∗ (t) for all t ∈ T, and
βw(e) + (1 − β)z(e) ≤ γ c∗ (e) for all e ∈ Aw ,
then the best of KWIKSORT and PICK-A-PERM is a γ -approximation for RANK-
AGGREGATION.
PROOF. We use the notation C OPT , F OPT , B OPT , c∗ (e), c∗ (t) defined in Section 4.
We rearrange (4) as E[C PAP ] = B PAP + F PAP , where
 
1  1
B PAP = pt z(t) F PAP = 1− pt z(e) .
t∈T
3 e∈Aw t:e∈t 3

Journal of the ACM, Vol. 55, No. 5, Article 23, Publication date: October 2008.
23:12 N. AILON ET AL.

If we now have β,  γ asin the statement

 of the theorem, then (keeping in mind
the crucial fact that 1 − t:e∈t 31 pt ≥ 0 for all e ∈ Aw ),
β E[C KS ] + (1 − β)E[C PAP ] = β B KS + (1 − β)B PAP + β F KS + (1 − β)F PAP
1
= pt (βw(t) + (1 − β)z(t))
t∈T
3
 
 1
+ 1− pt (βw(e) + (1 − β)z(e))
e∈Aw t:e∈t 3
 
1  1
∗
≤ pt γ c (t) + 1− pt γ c∗ (e)
t∈T
3 e∈Aw t:e∈t 3
= γ C OPT ,

as required.
11 ∗
LEMMA 5.2. For all t ∈ T , 37 w(t) + 47 z(t) ≤ 7
c (t) , and for all e ∈ Aw ,
3
7
w(e) + 47 z(e) ≤ 11
7
c∗ (e).
PROOF. The second inequality in the lemma is obtained by verifying the simple
fact that w(e) ≤ c∗ (e) and z(e) ≤ 2c∗ (e) for all e ∈ Aw . To prove the first inequality,
we want to show that
3 4 11
f (t) = w(t) + z(t) − c∗ (t) ≤ 0, (5)
7 7 7
where (slightly changing notation) t = (w 1 , w 2 , w 3 ) and
w(t) = w 1 + w 2 + w 3
z(t) = 2w 1 (1 − w 1 ) + 2w 2 (1 − w 2 ) + 2w 3 (1 − w 3 )
c∗ (t) = 1 − w 2 + 1 − w 3 + w 1
1/2 ≤ w 1 ≤ w j ≤ 1 for j = 2, 3
w1 + w2 + w3 ≤ 2
The proof can be completed by finding the global maximum of f (t) on the
defined polytope using standard techniques of multivariate calculus.
Note that for (w 1 , w 2 , w 3 ) = (1/2, 3/4, 3/4) we obtain w(t) = 2, z(t) = 5/4 and
c∗ (t) = 1, so (5) is tight. Theorem 5.3 follows from Theorem 5.1 and Lemma 5.2,
using β = 3/7 and γ = 11/7:
THEOREM 5.3. The best of KWIKSORT on G w and PICK-A-PERM is an expected
11/7 approximation for RANK-AGGREGATION.
In using Theorem 5.1 to derive bounds, we can also take advantage of a priori
knowledge of the system of weights w. We illustrate this using the special case of
only k = 3 voters, a case of independent interest in applications [Chaudhuri et al.
2006].
LEMMA 5.4. If k = 3, then for all t ∈ T , 25 w(t) + 35 z(t) ≤ 65 c∗ (t) and for all
e ∈ Aw , 25 w(e) + 35 z(e) ≤ 65 c∗ (e).

Journal of the ACM, Vol. 55, No. 5, Article 23, Publication date: October 2008.
Aggregating Inconsistent Information: Ranking and Clustering 23:13

PROOF. In this special case, we have that w(e) ∈ {2/3, 1} for all e ∈ Aw , and
w(e1 ) = w(e2 ) = w(e3 ) = 2/3 for all t = (e1 , e2 , e3 ) ∈ T , therefore w(t) =
2, z(t) = 4/3 and c∗ (t) ≥ 4/3. The inequalities can now be easily verified.

Theorem 5.5 follows from Theorem 5.1 and Lemma 5.4, using β = 2/5 and
γ = 6/5.

THEOREM 5.5. The best of KWIKSORT on G w and PICK-A-PERM is an expected

6/5 approximation for RANK-AGGREGATION when there are k = 3 voters.

6. Correlation Clustering and Consensus Clustering

In this section, we show how to apply the techniques presented in Section 3 to
CORRELATION-CLUSTERING and CONSENSUS-CLUSTERING. Recall that our goal is to
minimize disagreements. In FAS-TOURNAMENT, we used “bad triangles” in tourna-
ments to charge the disagreements in our solution. In CORRELATION-CLUSTERING,
disagreements in the solution can also be charged to bad triplets, which will be
defined shortly. Thus, the bad triplets replace the role taken by the directed trian-
gles in tournaments. Let (V, E + , E − ) be a CORRELATION-CLUSTERING instance. Our
algorithm KWIKCLUSTER, which is an analog of KWIKSORT, is defined as follows:

KWIKCLUSTER(G = (V, E + , E − ))

If V = ∅ then return ∅
Pick random pivot i ∈ V .
Set C = {i}, V  = ∅.

For all j ∈ V, j = i:
If (i, j) ∈ E + then
Add j to C
Else (If (i, j) ∈ E − )
Add j to V 

Let G  be the subgraph induced by V  .

Return C ∪ KWIKCLUSTER(G  ) .

As in the analysis of KWIKSORT, a pair i, j incurs a unit cost if a third vertex k

is chosen as pivot when the triplet (i, j, k) is in the same recursive call, and there
are two (+) and one (−) relations among i, j, k (doesn’t matter in which order). A
triplet (i, j, k) is therefore a bad triplet if it has two (+) and one (−) relations.4 Let
T denote the set of (not necessarily disjoint) bad triplets. For each t = (i, j, k) ∈ T
we define At as the event that all three i, j, k are in the same recursive call when

4
A CORRELATION-CLUSTERING instance with no bad triplets induces a consistent clustering, just as a
tournament with no 3-cycles is acyclic. Our algorithms have an optimal cost of 0 on these instances.

Journal of the ACM, Vol. 55, No. 5, Article 23, Publication date: October 2008.
23:14 N. AILON ET AL.

the first one among them was chosen as pivot. Let pt denote the probability of At .
The analysis continues identically to that of KWIKSORT.
THEOREM 6.1. Algorithm KWIKCLUSTER is a randomized expected 3-approxi-
mation algorithm for CORRELATION-CLUSTERING.
Now let (V, w + , w − ) be a weighted CORRELATION-CLUSTERING instance, where
n
w , w − ∈ (R+ )(2) . Unlike weighted FAS-TOURNAMENT, we will only consider
+

weight systems that satisfy the probability constraints w ij+ + w ij− = 1. We create the
unweighted majority CORRELATION-CLUSTERING instance G w = (V, E w+ , E w− ) and
return the clustering generated by KWIKCLUSTER(G w ).
Triangle inequality constraints in weighted CORRELATION-CLUSTERING have the
following form: for all i, j, k, w ij+ +w jk+ +w ik− ≤ 2. (Equivalently, w ik− ≤ w ij− +w jk− .)
Theorem 6.2 is analogous to Theorem 4.3:
THEOREM 6.2. Algorithm KWIKCLUSTER on G w is a 5 (respectively, 2) approx-
imation for weighted
CORRELATION-CLUSTERING with probability constraints (respectively, with prob-
ability and triangle inequality constraints combined).
The proof is almost identical to that of Theorem 4.3, with “+ + −” (bad) triplets
in G w replacing the role of directed (bad) triangles in tournaments.
Solving CONSENSUS-CLUSTERING is equivalent to solving weighted CORRELATION-
CLUSTERING with w ij+ (respectively, w ij− ) as the fractional number of input clusters
with a (+) (respectively, (−)) relation between i and j. This weighted CORRELATION-
CLUSTERING instance obeys both the probability constraints and the triangle inequal-
ity constraints, but we can do better than the 2 approximation guaranteed by The-
orem 6.2. Analysis almost identical to the one in Section 5 gives an expected 11/7
approximation for this case. The KWIKCLUSTER is coupled with PICK-A-CLUSTER,
which is defined analogously to PICK-A-PERM: Simply return a cluster chosen uni-
formly at random from the list.
THEOREM 6.3. The best of KWIKCLUSTER on G w and PICK-A-CLUSTER has an
expected approximation ratio of at most 11
7
for CONSENSUS-CLUSTERING.

7. Using the Pivot Scheme for Rounding the LP

We show how the techniques introduced above can be used for rounding the LP’s
for FAS-TOURNAMENT and CORRELATION-CLUSTERING. We consider the LP’s given
in Figure 1 [Potts 1980; Charikar et al. 2003]. Given a solution to the LP, we
consider algorithms LP-KWIKSORT and LP-KWIKCLUSTER (Figure 1) for rounding
the solutions for FAS-TOURNAMENT and CORRELATION-CLUSTERING, respectively.
The main idea of these algorithms is that, after we choose some pivot, we use the
LP solution variables to randomly decide where to put all other vertices, instead of
deciding greedily. We note that our LP-based algorithms only solve the LP once
and use the same LP solution in all recursive calls.
THEOREM 7.1. Our sorting LP rounding algorithm LP-KWIKSORT obtains the
following approximation ratios on weighted FAS-TOURNAMENT instances:
—5/2 when the weights satisfy the probability constraints,

Journal of the ACM, Vol. 55, No. 5, Article 23, Publication date: October 2008.
Aggregating Inconsistent Information: Ranking and Clustering 23:15

LP for weighted FAS-TOURNAMENT LP for weighted CORRELATION-CLUSTERING

 
min i< j (xij w ji + xji w ij ) s.t. minimize i< j (xij+ w ji− + xji− w ij+ ) s.t.
−
xik ≤ xij + xjk ∀ distinct i, j, k xik ≤ xij− + xjk −
for all distinct i, j, k
+ −
xij + xji = 1 for all i = j xij + xij = 1 for all i = j
xij ≥ 0 for all i = j xij− , xij+ ≥ 0 for all i = j

LP-KWIKSORT(V, x) LP-KWIKCLUSTER(V, x + , x − )
A recursive algorithm for rounding A recursive algorithm for rounding
the LP for weighted FAS-TOURNAMENT. the LP for weighted CORRELATION-
Given an LP solution: CLUSTERING.
x = {xij }i, j∈V , returns an ordering Given an LP solution:
on the vertices. x + = {xij+ }i< j , x − = {xij− }i< j ,
returns a clustering of the vertices.
If V = ∅ then return empty-list
Pick random pivot i ∈ V. If V = ∅ then return ∅
Set VR = ∅, VL = ∅. Pick random pivot i ∈ V.
Set C = {i}, V  = ∅.
For all j ∈ V, j = i:
With probability xji For all j ∈ V, j = i :
Add j to VL . With probability xij+
Else (W/ prob. xij = 1 − xji ) Add j to C.
Add j to VR . Else (W/ prob. xij− = 1 − xij+ )
Add j to V  .
Return order
LP-KWIKSORT(VL , x), i, Return clustering
LP-KWIKSORT(VR , x) {C}∪LP-KWIKCLUSTER(V  , x + , x − )

FIG. 1. Standard LP relaxations and their corresponding rounding algorithms.

—2 when the weights satisfy the probability and the triangle inequality constraints,
and
—4/3 for RANK-AGGREGATION.
The result for RANK-AGGREGATION is obtained by returning the better of LP-
KWIKSORT and PICK-A-PERM.
THEOREM 7.2. Our clustering LP rounding algorithm LP-KWIKCLUSTERING
obtains the following approximation ratios on weighted CORRELATION-CLUSTERING
instances:
—5/2 when the weights satisfy the probability constraints,
—2 when the weights satisfy the probability and the triangle inequality constraints,
and

Journal of the ACM, Vol. 55, No. 5, Article 23, Publication date: October 2008.
23:16 N. AILON ET AL.

—4/3 for CONSENSUS-CLUSTERING.

The result for CONSENSUS-CLUSTERING is obtained by returning the better of LP-
KWIKCLUSTER and PICK-A-CLUSTER.
The bounds in Theorems 7.1 and 7.2 are obtained with respect to the optimal
corresponding LP solution, and hence imply bounds on their integrality gaps. We
further remark that the integrality gap of the FAS-TOURNAMENT LP can be lower
bounded by 3/2. This follows from the fact that, for any tournament on n vertices,
there is a feasibly solution to the FAS-TOURNAMENT LP that has value at most n/3
and there exist tournaments with no minimum feedback arc set of size smaller than
n(1/2 − ε), where ε is arbitrarily small.
We now prove Theorems 7.1 and 7.2. The common technique will be to reduce
the problem to proving global bounds of certain multinomials in high dimensional
polytopes. We start with the analysis of LP-KWIKSORT (Theorem 7.1).
Let C LKS denote the cost of the ordering returned by the rounding algorithm
LP-KWIKSORT. We divide all pairs i, j into those that are charged dangerously and
those that are charged safely by the algorithm. The safe edges are charged when one
of their endpoints is chosen as pivot, and the other endpoint is in the same recursive
call. The expected cost of pairs that are charged safely in LP-KWIKSORT is
xij w ji + xji w ij , (6)
which is exactly the contribution to the LP solution.
 We let cij∗ denote expression
(6). So the value of the LP solution is CLP = i< j cij∗ .

A pair i, j is charged dangerously when a third vertex k is chosen as pivot, all

three i, j, k are in the same recursive call, and i, j are placed on opposite sides of
k. The charge is w ij (respectively, w ji ) if j (respectively, i) is placed on the left side
of k and i (respectively, j) on its right. In either case, we charge this cost to the
triplet i, j, k. We let T denote the set of all triplets of distinct vertices, and for any
t = {i, j, k} ∈ T we denote by At the event that all of i, j, k are in the same recursive
call when the first one among them is chosen as pivot. Let pt denote the probability
of At . Let Bijt denote the event that (i, j) is dangerously charged to triangle t, in
that order (i to the left, j to the right). Then we have for any t = {i, j, k},
  1
Pr At ∧ Bijt = Pr [At ] Pr Bijt |At = pt xik xkj .
3
(The 1/3 comes from the fact that conditioned on At , each one of i, j, k was equally
likely to be the pivot vertex.) Denote qijt = 13 xik xkj . So the total expected charge to
a triplet t = {i, j, k} is pt y(t), where
y(t) = qijt w ji + qjit w ij + qjkt w kj + qkjt w jk + qkit w ik + qikt w ki .

Now we notice that for any t = {i, j, k} and t  = {i, j, k  } (two triplets sharing
 
a pair i, j), the events At ∧ (Bijt ∨ Bjit ) and At  ∧ (Bijt ∨ Bjit ) are disjoint, because a
pair i, j can be split into two different recursion branches only once. Thus,

pt (qijt + qjit ) ≤ 1 .
t:i, j∈t

Journal of the ACM, Vol. 55, No. 5, Article 23, Publication date: October 2008.
Aggregating Inconsistent Information: Ranking and Clustering 23:17

The above expression is exactly the probability that the pair i, j is dangerously
charged. Therefore, the total expected cost of LP-KWIKSORT is E[C LKS ] = B LKS +
F LKS , where

B LKS = pt y(t)
t
 
 
F LKS
= 1− pt (qij + qji ) cij∗ .
t t

i< j t:i, j∈t


The following expression is a rearrangement of the sum CLP = i< j cij∗ : CLP =
BLP + FLP , where
 
BLP = pt (qijt + qjit )cij∗
t {i, j}⊆t
 
 
FLP = 1− pt (qij + qji ) cij∗ .
t t

i< j t:i, j∈t

So FLP = F LKS ≥ 0. We have the following lemma. We defer the proof to

Section 8.
LEMMA 7.3. If the weight system satisfies the probability constraints (respec-
tively, probability constraints and triangle inequality constraints), then for any
t ∈ T,

y(t) ≤ τ (qijt + qjit )cij∗ ,
{i, j}⊆t

where τ = 5/2 (respectively, τ = 2).

Therefore, in this case, B LKS ≤ τ BLP . We conclude that E[C LKS ] ≤ τ CLP . This
concludes the proof of the first two items of Theorem 7.1.
We now prove the last item of Theorem 7.1 by coupling LP-KWIKSORT with
PICK-A-PERM. Recall from Section 5 that the expected value of the PICK-A-PERM
algorithm is

E[C PAP ] = z ij ,
i< j

where z ij = 2w ij (1 − w ij ). We rearrange this sum as follows:

E[C PAP ] = BLP
PAP
+ FLP
PAP
,
where
 
PAP
BLP = pt (qijt + qjit )z ij
t {i, j}⊆t
 
 
PAP
FLP = 1− pt (qijt + qjit ) z ij .
i< j t:{i, j}⊆t


It is easy to see that 0 ≤ FLP
PAP
≤ 2FLP (because z ij ≤ 2cij∗ , and t:i, j∈t pt (qijt +
qjit ) ≤ 1). Along with F LKS = FLP , this implies that 23 F LKS + 13 FLPPAP
≤ 43 FLP .

Journal of the ACM, Vol. 55, No. 5, Article 23, Publication date: October 2008.
23:18 N. AILON ET AL.

Likewise, in Lemma 7.4 (proof in Section 8), we bound a convex combination of

B LKS and BLP
PAP
.
LEMMA 7.4. For all t = {i, j, k},
2 1   t  4   t 
y(t) + qij + qjit z ij ≤ qij + qjit cij∗ .
3 3 {i, j}⊆t 3 {i, j}⊆t

As a consequence, 23 B LKS + 13 BLP

PAP
≤ 43 BLP .
Combining, we conclude that
2 1  PAP 4
E[C LKS ] + E CLP ≤ CLP .
3 3 3
This means, in particular, that the best of LP-KWIKSORT and PICK-A-PERM has
an expected approximation ratio of at most 43 with respect to the LP cost. This
concludes the proof of Theorem 7.1.
We now prove Theorem 7.2, by analyzing the output of LP-KWIKCLUSTER on
CORRELATION-CLUSTERING and CONSENSUS-CLUSTERING instances. Define cij∗ =
xij+ w ij− + xij− w ij+ . This is the LP contribution as well as the expected charge of
the safe pairs, which are defined as above: these are pairs of vertices i = j such
that one was chosen as pivot when the other was in the same recursive call to
LP-KWIKCLUSTER. All other pairs are dangerously charged.
For a triplet t = (i, j, k) of disjoint vertices, as usual, we let At denote the
event that one of i, j, k was chosen as pivot when the other two vertices are in
the same recursive call to LP-KWIKCLUSTER. Let pt = Pr [At ]. Let B{i} t
j denote
the event that i, j was dangerously charged to t, because k is the pivot, i is taken
in k’s cluster and j is placed aside (the charge to t is then w ij+ ). The probability
1 + −
j conditioned on At is q{i} j = 3 x ki x kj . Let B{ij} denote the event that i, j
t t t
of B{i}
was dangerously charged to t, because k is the pivot, and both i and j are taken
in k’s cluster (the charge is w ij− ). The probability of B{tij} conditioned on At is

q{tij} = 13 xki+ xkj+ . Define y(t) = {i, j}⊆t (q{i}
t + −
j + q{ j}i )w ij + q{ij} w ij .
t t

For all i = j,

j + q{ j}i + q{ij} ) ≤ 1
t t t
pt (q{i}
t:{i, j}⊆t

by disjointness of events. As before, we decompose E[C LKS ] = B LKS + F LKS and

CLP = FLP + BLP , where

B LKS = pt y(t)
t
 
   t 
F LKS = 1− pt q{i} j + q{t j}i + q{tij} cij∗ .
i< j t:{i, j}⊆t
    ∗
BLP = pt t
q{i} j + q{ j}i + q{ij} cij
t t

t {i, j}⊆t
 
   t  ∗
FLP = 1− pt q{i} j + q{ j}i + q{ij} cij .
t t

i< j t:{i, j}⊆t

Journal of the ACM, Vol. 55, No. 5, Article 23, Publication date: October 2008.
Aggregating Inconsistent Information: Ranking and Clustering 23:19

LEMMA 7.5. If the weight system satisfies the probability constraints (respec-
tively, probability constraints and triangle inequality constraints), then for any
t ∈ T,

∗
y(t) ≤ τ t
q{i} j + q{ j}i + q{ ji} cij ,
t t

{i, j}⊆t

where τ = 5/2 (respectively, τ = 2).

As a result, we get a 5/2 approximation for the probability constraints case, and
a 2 approximation for the probability and triangle inequality constraints case. This
proves the first two items of Theorem 7.2.
PAC
For CONSENSUS-CLUSTERING, we let CLP denote the value of PICK-A-CLUSTER.
So E[CLP ] = BLP + FLP , where
PAC PAC PAC

   
PAC
BLP = pt t
q{i} j + q{ j}i + q{ij} z ij
t t

t {i, j}⊆t
 
 
PAC
FLP = 1− t
pt (q{i} j + q{t j}i + q{tij} ) z ij ≥ 0.
i< j t:{i, j}⊆t

z ij = 2w ij+ w ij−
LEMMA 7.6. For all t = {i, j, k},
2 1   t  4   t 
y(t) + q{i} j + q{t j}i + q{tij} z ij ≤ q{i} j + q{t j}i + q{tij} cij∗ .
3 3 {i, j}⊆t 3 {i, j}⊆t

Also, it is easy to see that z ij ≤ 2cij∗ , so 0 ≤ FLP

PAC
≤ 2FLP and consequently
2 LKS
3
F + 3 FLP ≤ 3 FLP . Combining this with Lemma 7.6, we conclude that
1 PAC 4
2 LKS
3
C + 13 CLP
PAC
≤ 43 FLP , as desired. The proofs of Lemmas 7.5 and 7.6 can be
found in Section 8. This completes the proof of Theorem 7.2.

8. Proving Polynomial Inequalities in Polytopes

In this section, we prove Lemmas 7.3, 7.4, 7.5 and 7.6. All these lemmas are equiv-
alent to proving certain inequalities on polynomials in R6 . We restate these inequal-
ities for the sake of clarity, and slightly change notation to reduce indexing. In what
follows, we fix a triplet t consisting of three arbitrary vertices, t = (1, 2, 3) ⊆ V . For
the ranking proofs (Lemmas 7.3 and 7.4), we let x1 = x23 , x2 = x31 , x3 = x12 and
w 1 = w 23 , w 2 = w 31 , w 3 = w 12 . For the clustering proofs (Lemmas 7.5 and 7.6),
− − − − − −
we let x1 = x23 , x2 = x31 , x3 = x12 and w 1 = w 23 , w 2 = w 31 , w 3 = w 12 . We use
x ∈ R3 as shorthand for (x1 , x2 , x3 ) and w ∈ R3 as shorthand for (w 1 , w 2 , w 3 ). We
will use the same symbols to denote parallel objects in the ranking (Lemmas 7.3
and 7.4) and clustering (Lemmas 7.5 and 7.6) proofs. To avoid confusion, we now
separate between the two.
8.1. POLYHEDRAL INEQUALITIES FOR RANKING. Let ⊆ R3 denote the proba-
bility constraints polytope, that is,
= {(a1 , a2 , a3 ) : 0 ≤ ai ≤ 1, i = 1, 2, 3} . (7)

Journal of the ACM, Vol. 55, No. 5, Article 23, Publication date: October 2008.
23:20 N. AILON ET AL.

Let ⊆ denote the triangle inequality and probability constraints for ranking
polytope, that is
= {(a1 , a2 , a3 ) ∈ : 1 ≤ a1 + a2 + a3 ≤ 2} .
We define three functions, piv, pap, lp : R6 → R, as follows:
piv(x, w) = x1 x2 w 3 + (1 − x1 )(1 − x2 )(1 − w 3 )
+ x2 x3 w 1 + (1 − x2 )(1 − x3 )(1 − w 1 )
+ x3 x1 w 2 + (1 − x3 )(1 − x1 )(1 − w 2 );

pap(x, w) = (x1 x2 + (1 − x1 )(1 − x2 ))2w 3 (1 − w 3 )

+ (x2 x3 + (1 − x2 )(1 − x3 ))2w 1 (1 − w 1 ) (8)
+ (x3 x1 + (1 − x3 )(1 − x1 ))2w 2 (1 − w 2 );

lp(x, w) = (x1 x2 + (1 − x1 )(1 − x2 ))(x3 (1 − w 3 ) + (1 − x3 )w 3 )

+ (x2 x3 + (1 − x2 )(1 − x3 ))(x1 (1 − w 1 ) + (1 − x1 )w 1 )
+ (x3 x1 + (1 − x3 )(1 − x1 ))(x2 (1 − w 2 ) + (1 − x2 )w 2 ).

Lemma 7.3 is equivalent to showing that f = piv − 52 lp ≤ 0 for all (x, w) ∈

× and g = piv − 2lp ≤ 0 for all (x, w) ∈ × . We make two simplification
steps.

(1) Linearity in w. The functions f and g are linear in w (for x fixed). Therefore, f
obtains its maximum on (x, w) for w which is some vertex of , and similarly g
obtains its maximum value on (x, w) for w, which is some vertex of . For f , it
suffices to check w = (0, 0, 0) and w = (0, 0, 1) (due to symmetry), and for g,
it suffices to check w = (0, 0, 1). Let f̃ (x) = f (x, 0, 0, 0), fˆ (x) = f (x, 0, 0, 1)
and g̃(x) = g(x, 0, 0, 1). It remains to show that f̃ , fˆ , g̃ : R3 → R are bounded
above by 0 on .
(2) Trilinearity in x. For i = 1, 2, 3, the functions f̃ , fˆ and g̃ are linear in xi when
x j ’s are fixed for j ∈ {1, 2, 3} \ {i}. This means that any point x ∈ such that
x + tei ∈ for all t ∈ [−ε, ε] for some ε > 0 and some i ∈ {1, 2, 3} (where ei
is a standard basis element of R3 ) is not a strict local maximum of f̃ , fˆ and g̃
in , so these points x can be ignored. The points that are left are x ∈ such
that that x1 + x2 + x3 = 1 or x1 + x2 + x3 = 2.
Let Hk ⊆ R3 denote the hyperplane x1 + x2 + x3 = k for k = 1, 2, and let
k = ∩ Hk . The closed polytopes k are two dimensional and the polynomials
f̃ , fˆ and g̃ are of total degree 3 and maximal degree 2 in each variable. It is tedious
yet elementary to verify that the maxima are obtained in accordance with Table II.
Lemma 7.4 is equivalent to proving that h = 2piv/3 + pap/3 − 4lp/3 ≤ 0 for
all (x, w) ∈ × . The trilinearity in x still holds true for h, so as before we can
assume that either x ∈ 1 or x ∈ 2 . We can assume without loss of generality
(by symmetry) that x ∈ 2 , that is, x1 + x2 + x3 = 2. When x is fixed, then h
is a (possibly degenerate) concave paraboloid in w. In case of nondegeneracy, its
unique global maximum is obtained when ∇w h = 0, which can be easily verified

Journal of the ACM, Vol. 55, No. 5, Article 23, Publication date: October 2008.
Aggregating Inconsistent Information: Ranking and Clustering 23:21

TABLE II. MAXIMA OF f̃ , fˆ AND g̃ ON 1, 2

function\domain 1 2
f̃ 0 at (1/2, 0, 1/2) 0 at (1, 0, 1)
fˆ 0 at (0, 0, 1) 0 at (1, 0, 1)
g̃ 0 at (0, 0, 1) 0 at (1, 0, 1)

to be solved by w = w∗ = (w 1∗ , w 2∗ , w 3∗ ) defined by
x2 x3
w 1∗ = + 2x1 − 1
x2 x3 + (1 − x2 )(1 − x3 )
x3 x1
w 2∗ = + 2x2 − 1 (9)
x3 x1 + (1 − x3 )(1 − x1 )
x1 x2
w 3∗ = + 2x3 − 1
x1 x2 + (1 − x1 )(1 − x2 )
(the paraboloid in w is degenerate if and only if any of the denominators in (9) are
0, equivalently xi = 0 and x j = 1 for some i, j. But this implies that after possibly
permuting coordinates, x = (1, 1, 0). But h(1, 1, 0, w) = −2w 32 /3 ≤ 0, proving
the desired assertion trivially). Since we are assuming x1 + x2 + x3 = 2, we have
that for any 1 ≤ i < j ≤ 3, xi + x j ≥ 1, equivalently xi x j ≥ (1 − xi )(1 − x j ).
Therefore (9) implies w i ≥ 12 + 2xi − 1 for i = 1, 2, 3. Summing up, we obtain
w 1 + w 2 + w 3 ≥ − 32 + 2(x1 + x2 + x3 ) = 52 > 2. In other words, (9) implies that w∗
and are strictly on different sides of H2 . Let w = (w 1 , w 2 , w 3 ) be any point in .
Consider the straight line passing through w and w∗ , and let w the intersection of
this line with H2 . Restricted to (and for our fixed x ∈ 2 ) h is a parabola, attaining
its maximum on w∗ . Therefore h(x, w ) ≥ h(x, w  ), and we can assume in what
follows that w = w ∈ H2 (we must drop the assumption that w ∈ though).
We change variables and let h̃ : R4 → R be defined by h̃(x1 , x2 , w 1 , w 2 ) =
h(x1 , x2 , 2 − x1 − x2 , w 1 , w 2 , 2 − w 1 − w 2 ). We reduced the problem to proving
that h̃ ≤ 0 on {x1 ≤ 1, x2 ≤ 1, x1 + x2 ≥ 1} × R2 . It is elementary to verify, using
vanishing derivatives, that for (x1 , x2 ) fixed, the maximum of h̃ is obtained when
(w 1 , w 2 ) = (x1 , x2 ). Substituting, we get h̃(x1 , x2 , x1 , x2 ) = −2(−1 + x1 )(−1 +
x2 )(−1 + x2 + x3 ), which is less than or equal to 0 because x1 + x2 ≥ 1 and
x1 , x2 ≤ 1.
8.2. POLYHEDRAL INEQUALITIES FOR CLUSTERING. Let ⊆ R3 denote the prob-
ability constraints polytope as defined in (7). Let ⊆ denote the triangle
inequality and probability constraints polytope for clustering, that is,
= {(a1 , a2 , a3 ) ∈ : a3 ≤ a1 + a2 , a1 ≤ a2 + a3 , a2 ≤ a3 + a1 } .

We define three functions, piv, pap, lp : R6 → R, as follows:

piv(x, w) = (1 − x1 )(1 − x2 )w 3 + (x1 (1 − x2 ) + (1 − x1 )x2 )(1 − w 3 )
+ (1 − x2 )(1 − x3 )w 1 + (x2 (1 − x3 ) + (1 − x2 )x3 )(1 − w 1 )
+ (1 − x3 )(1 − x1 )w 2 + (x3 (1 − x1 ) + (1 − x3 )x1 )(1 − w 2 );
pap(x, w) = ((1 − x1 )(1 − x2 ) + (1 − x1 )x2 + x1 (1 − x2 ))2w 3 (1 − w 3 )
+ ((1 − x2 )(1 − x3 ) + (1 − x2 )x3 + x2 (1 − x3 ))2w 1 (1 − w 1 )
+ ((1 − x3 )(1 − x1 ) + (1 − x3 )x1 + x3 (1 − x1 ))2w 2 (1 − w 2 );

Journal of the ACM, Vol. 55, No. 5, Article 23, Publication date: October 2008.
23:22 N. AILON ET AL.

TABLE III. MAXIMUM OF f 000 , f 001 , f 011 , f 111 , g000 , g011 , g111 ON 1, 2, 3

function \ domain 1 2 3
f 000 0 at (0, 0, 0) 0 at (0, 0, 0) 0 at (0, 0, 0)
f 001 0 at (1/2, 0, 1/2) −1 at (0, 1/2, 1/2) 0 at (1/2, 1/2, 1)
f 011 −3/2 at (1/2, 0, 1/2) 0 at (0, 1, 1) 0 at (0, 1, 1)
f 111 0 at (1, 0, 1) 0 at (1, 1, 0) 0 at (1, 0, 1)
g000 0 at (0, 0, 0) 0 at (0, 0, 0) 0 at (0, 0, 0)
g011 −1 at (1, 0, 1) 0 at (0, 1, 1) 0 at (0, 1, 1)
g111 0 at (1, 0, 1) 0 at (1, 1, 0) 0 at (1, 0, 1)

lp(x, w) = ((1 − x1 )(1 − x2 ) + (1 − x1 )x2 + x1 (1 − x2 ))(x3 (1 − w 3 ) + (1 − x3 )w 3 )

+ ((1 − x2 )(1 − x3 ) + (1 − x2 )x3 + x2 (1 − x3 ))(x1 (1 − w 1 ) + (1 − x1 )w 1 )
+ ((1 − x3 )(1 − x1 ) + (1 − x3 )x1 + x3 (1 − x1 ))(x2 (1 − w 2 ) + (1 − x2 )w 2 ).
(10)

Lemma 7.5 is equivalent to showing that f = piv − 52 lp ≤ 0 for all (x, w) ∈

× and g = piv −2lp ≤ 0 for all (x, w) ∈ × . We make the two simplification
steps as before.
(1) Linearity in w. The functions f and g are linear in w (for x fixed). Arguing as
before, it suffices to analyze f on w = (0, 0, 0), w = (0, 0, 1), w = (0, 1, 1)
and w = (1, 1, 1), and g on w = (0, 0, 0), w = (0, 1, 1), w = (1, 1, 1). We
denote the functions on x after substituting for w by f 000 , f 001 , f 011 , f 111 and
g000 , g011 , g111 (with obvious correspondence).
(2) Trilinearity in x. For i = 1, 2, 3 the functions f and g are linear in xi when
x j ’s are fixed for j ∈ {1, 2, 3} \ {i}. This means that any point x ∈ such that
x + tei ∈ for all t ∈ [−ε, ε] for some ε > 0 and some i ∈ {1, 2, 3} (where ei
is a standard basis element of R3 ) is not a strict local maximum of f, g in , so
these points x can be ignored. The points that are left are x ∈ 1 ∪ 2 ∪ 3 where
i = ∩ Hi for i = 1, 2, 3 and H1 = {(a1 , a2 , a3 ) ∈ R3 : a1 = a2 +a3 }, H2 =
{(a1 , a2 , a3 ) ∈ R3 : a2 = a3 + a1 }, H3 = {(a1 , a2 , a3 ) ∈ R3 : a3 = a1 + a2 }.
The functions f, g restricted to one of the finitely many “interesting” points w and
to x ∈ i for some i ∈ {1, 2, 3} can be represented as polynomials of total degree 3
and maximal degree 2 in each variable. k are two dimensional and the polynomials
f̃ , fˆ and g̃ are of total degree 3 and maximal degree 2 in each variable. It is tedious
yet elementary to verify that the maxima are obtained in accordance with Table III.
Lemma 7.6 is equivalent to proving that h = 2piv/3 + pap/3 − 4lp/3 ≤ 0 for
all (x, w) ∈ × . We prove this assertion as follows:
Using Symmetries of h. Let (x, w) be some local maximum of h in × . Assume
there is an index i ∈ {1, 2, 3} such that all of xi , xi+1 , w i , w i+1 ∈
/ {0, 1} (the index
arithmetic is modulo 3). Without loss of generality, assume that x1 , x2 , w 1 , w 2 ∈ /
{0, 1}. Since (x, w) is a local maximum of h on × , and since x1 , x2 , w 1 , w 2 ∈ /
{0, 1}, the derivatives of h on the hyperplane H = {(x, w) + t(1, −1, 0, 0, 0, 0) +
s(0, 0, 0, 1, −1, 0)|t, s ∈ R} must vanish at t = s = 0. One verifies that h is
a polynomial of total degree 2 in t, s on H , and the derivatives vanish in the
unique point t = (x2 − x1 )/2, s = (w 2 − w 1 )/2. Therefore, we may assume
that x1 = x2 and w 1 = w 2 . Now, if in addition x3 , w 3 ∈ / {0, 1}, then we use
the same argument (switching the roles of the variables), and we can assume that
x1 = x2 = x3 , w 1 = w 2 = w 3 . It is trivial to show that h ≤ 0 under this constraint.

Journal of the ACM, Vol. 55, No. 5, Article 23, Publication date: October 2008.
Aggregating Inconsistent Information: Ranking and Clustering 23:23

TABLE IV. MAXIMA OF f GIVEN DIFFERENT CONSTRAINTS ON 1, 2, 3

constraint 1 2 3
00**** 0:000000 0:000000 0:000000
11**** 0:11011 12 0:11011 12 infeasible
**01* − 23 :101011 0:011011 0:011011
0**0** 0:000000 0:000000 0:000000
1**0** − 23 :110011 − 23 :110011 − 23 :101011
0***0* 0:000000 0:000000 0:000000
1***0* 0:101101 − 23 :110101 0:101101
x x0ww* 0:000000 0:000000 0:000000
x x*ww0 0:000000 0:000000 0:000000
01**** infeasible 0:011 12 11 0:011 12 11
***00* 0:000000 0:000000 0:000000
***11* 0:101111 0:11011 12 0:101111
0**1** − 54 :0001 14 34 0:011111 0:011111
1**1** 0:1 59 5 59 5
1
64 64 64 64
0:11011 12 0:1011 12 1
0***1* − 53 :000 12 1 12 0:011 12 11 0:011 12 11
1***1* 0:11011 12 0:11011 12 0:101111
x x1ww* infeasible infeasible 0: 12 21 1 12 21 1
x x*ww1 0:110111 0:110111 0: 12 21 1 12 21 1
The constraint 0**0*1 means, as an example, x1 = 0, w1 = 0, w3 = 1.
A constraint of the form x x0ww* means x1 = x2 , x3 = 0, w 1 = w 2 . The
maxima are denoted by M:x1 x2 x3 w 1 w 2 w 3 , where M is the maximum value,
attained at (x1 , x2 , x3 , w 1 , w 2 , w 3 ).

Boundary Cases. We can now assume that either: (1) at least two of x1 , x2 , x3 ,w 1 ,
w 2 , w 3 are in {0, 1}, or, (2) x1 = x2 , w 1 = w 2 and at least one of x3 , w 3 are in
{0, 1}. In addition, the function h is trilinear in x, so we may assume (as above) that
x ∈ 1 ∪ 2 ∪ 3 . This reduces the problem to proving inequalities for polynomials
of total degree at most 4 and maximal degree at most 3 (respectively, 2) in each
x-variable (respectively, w-variable), in 3-dimensional polytopes. We summarize
the analysis in Table IV.

9. NP-Hardness of Feedback Arc Set on Tournaments

All the problems referred to in Table I in Section 1.2 were previously known to be
NP-hard except for FAS-TOURNAMENT. In this section, we show:
THEOREM 9.1. Unless NP ⊆ BPP, FAS-TOURNAMENT has no polynomial time
algorithm.
PROOF. We reduce to FAS-TOURNAMENT from FAS-DIGRAPH, which is the prob-
lem of finding a minimum feedback arc set in a general directed graph. FAS-DIGRAPH
is NP-hard [Karp 1972] (in fact, it is MAX-SNP-hard, see Håstad [2001], Newman
[2000], and Newman and Vempala [2001]).
Let G = (V, A) (with |V | = n) be an instance of FAS-DIGRAPH. Suppose we
could add a set of edges A R to G such that (V, A ∪ A R ) is a tournament, and such
that exactly half of A R are backward in any ordering π of V . Then, by solving
FAS-TOURNAMENT we would be able to recover the feedback arc set of G. This is
generally impossible. However, if we add the edges A R randomly (i.e., for every
i, j such the neither (i, j) nor ( j, i) are in A add (i, j) or ( j, i) to A R with equal
probability) then for any π the expected number of backward edges is half |R|.

Journal of the ACM, Vol. 55, No. 5, Article 23, Publication date: October 2008.
23:24 N. AILON ET AL.

The variance makes this approach fail. By blowing up G and using a concentration
property of the random variable counting the number of backward edges in A R ,
we can use this construction (see similar random digraph constructions in Newman
[2000] and Newman and Vempala [2001]).
We pick an integer k = poly(n) (chosen later). The blow-up digraph G k =
(V k , Ak ) is defined as follows:
Vk = {v 1 , . . . , v k }
v∈V
Ak = {(u i , v j )|(u, v) ∈ A, i, j ∈ {1, . . . , k}} .
We observe that the minimum feedback arc set of G k is exactly k 2 times the
minimum feedback arc set of G. Indeed, it suffices to consider only rankings π
on V k that rank the vertices v 1 , . . . , v k as one block for all v ∈ V (as explained
in Alon [2006], if v i <π v j are not adjacent in the ranking, then either moving v i
immediately to the left of v j or moving v j immediately to the right of v i will result
in a ranking inducing no more feedback edges than π).
Now we turn G k into a tournament T k = {V k , Ak ∪ AkR } using the construction
defined above. For a ranking π of V k , let f R (π ) denote the number of feedback
edges in AkR with respect to π. Denote by μ the expected value of f R (π), which is the
same for all π, and can be efficiently computed. We claim that for k = poly(n), √ with
probability at least 2/3, all rankings π satisfy | f R (π) − μ| = O((nk)3/2 log(nk)).
This would imply, using the above observation, that, for big enough k = poly(n),
the size of the minimum feedback arc set of T k can be used to √ efficiently recover
the size of the minimum feedback arc set of G, because (nk)3/2 log(nk) = o(k 2 ).
To prove the claim, for any fixed ranking π, set a random indicator variable X wπ z
for every nonedge {w, z} of G k that equals k
1 iffπ the edge between w and z in A R is
backward with respect to π. So f R (π ) = X w z . A simple application of Chernoff
bounds [Alon and Spencer 1992] and union bound (over all possible (nk)! rankings)
completes the proof of the claim. It follows that unless FAS-DIGRAPH ∈ B P P, we
cannot solve FAS-TOURNAMENT in polynomial time.
We wish to thank Noga Alon for ideas significantly simplifying the proof [Alon
2006]. Our initial hardness result was via max-SNP hardness of FAS-DIGRAPH, and
Noga Alon pointed out that the same idea also works with the weaker NP-hardness.

10. Related Work

Since the publication of the conference version of this work [Ailon et al. 2005],
there have been interesting developments in the field.
On the ranking side, Kenyon-Mathieu and Schudy [2007] presented a PTAS for
FAS-TOURNAMENT, thus considerably improving the constant approximation guar-
antee presented here. Williamson and Van Zuylen [2007] derandomized the pivot
algorithms introduced in this article for both ranking and clustering, with match-
ing approximation guarantees. In addition, Coppersmith et al. [2006] showed that
ordering a weighted tournament by in-degree is a 5-approximation for weighted
FAS-TOURNAMENT with probability constraints, thus obtaining another natural con-
stant factor approximation. Ailon [2008] extends this work to partial rankings, often
found in information science applications. In the machine learning community, the

Journal of the ACM, Vol. 55, No. 5, Article 23, Publication date: October 2008.
Aggregating Inconsistent Information: Ranking and Clustering 23:25

problem of learning how to rank has been revisited in the context of reduction to
binary preference learning. We refer the reader to a recent paper by Ailon and Mohri
[2008], which is inspired by this work and improves a result by Balcan et al. [2007]
(inspired by Coppersmith et al. [2006]).
On the clustering side, Ailon and Charikar [2005] extended results here to hier-
archical clulstering, a problem well studied in phylogeny. They generalize KWIK-
CLUSTER to that setting and obtain constant factor approximation guarantees.

11. Open Problems

—KWIKSORT is in fact the well-known quick-sort algorithm for ordered data with
transitivity violations. Can we use other standard sorting algorithms, such as
merge-sort to obtain similar approximation algorithms?
—Finding tight examples for the algorithms presented in this work is an interesting
problem. For weighted weighted FAS-TOURNAMENT and weighted CORRELATION-
CLUSTERING with probability constraints, Warren Schudy communicated the
following tight example for the KWIKSORT and KWIKCLUSTER, respectively. It
suffices to consider unweighted instances (weights are 0, 1). For the ranking
problem, take an acyclic tournament and flip the edge connecting the lowest and
the highest ranked vertices. The optimal solution pays 1. KWIKSORT pays n − 2 if
the lowest or highest ranked vertices are chosen as pivot in the first step, otherwise
1. Therefore, the expected ratio is 3(n − 2)/n, which tends to 3 as n → ∞. For
the clustering problem set all edges to (+) except for one which is set to (−).
The optimal solution pays 1 by clustering all the vertices together. KWIKCLUSTER
pays n − 2 if one of the two vertices incident to the unique (−)-edge is chosen
as pivot in the first step, otherwise the optimal cost of 1, giving an expected ratio
of 3(n − 2)/n. Finding tight examples for the triangle inequality cases as well
as for the aggregation problems remains an open problem.
—Is RANK-AGGREGATION NP-Hard for 3 permutations [Dwork et al. 2001a; Dwork
et al. 2001b]?
—Is CONSENSUS-CLUSTERING NP-Hard for a constant number of clusters
[Wakabayashi 1998; Filkov and Skiena 2003]?
—Can we approximate weighted CORRELATION-CLUSTERING with triangle inequal-
ities, but no probability constraints?
ACKNOWLEDGMENTS. We would like to thank Ravi Kumar and D. Sivakumar for
several discussions on these problems. Thanks also to Shuchi Chawla and Tony
Wirth for extensive discussions on consensus clustering, to Aristides Gionis for
sending us a preprint of their paper [Gionis et al. 2005], to Noga Alon for discussions
on the hardness result, to Warren Schudy for communicating his nice observations
to us, to Anke van Zuylen and Lisa Fleischer for sending us preprints of their recent
derandomization results and for anonymous reviewers.

REFERENCES
AILON, N. 2008. Aggregation of partial rankings, p-ratings and top-m lists. Algorithmica. DOI
10.1007/s00453-008-9211-1.
AILON, N., AND CHARIKAR, M. 2005. Fitting tree metrics: Hierarchical clustering and phylogeny. In Pro-
ceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS) (Pittsburgh,
PA). IEEE Computer Society Press, Los Alamitos, CA, 73–82.

Journal of the ACM, Vol. 55, No. 5, Article 23, Publication date: October 2008.
23:26 N. AILON ET AL.

AILON, N., CHARIKAR, M., AND NEWMAN, A. 2005. Aggregating inconsistent information: Ranking and
clustering. In Proceedings of the 37th Annual Symposium on the Theory of Computing (STOC) (Boston,
MA). ACM, New York, 684–693.
AILON, N., AND MOHRI, M. 2008. An efficient reduction of ranking to classification. In Conference on
Learning Theory (COLT) (Helsinki, Finland).
ALON, N. 2006. Ranking tournaments. SIAM J. Disc. Math. 20, 1, 137–142.
ALON, N., AND SPENCER, J. H. 1992. The Probabilistic Method. Wiley, New York.
ARORA, S., FRIEZE, A., AND KAPLAN, H. 1996. A new rounding procedure for the assignment problem
with applications to dense graph arrangement problems. In Proceedings of the 37th Annual Symposium
on the Foundations of Computer Science (FOCS) (Burlington, VT). IEEE Computer Society Press, Los
Alamitos, CA, 24–33.
BALCAN, M.-F., BANSAL, N., BEYGELZIMER, A., COPPERSMITH, D., LANGFORD, J., AND SORKIN, G. B. 2007.
Robust reductions from ranking to classification. In Proceedings of the Conference on Learning Theory
(COLT). Lecture Notes in Computer Science, vol. 4539. Springer-Verlag, New York, 604–619.
BANG-JENSEN, J., AND THOMASSEN, C. 1992. A polynomial algorithm for the 2-path problem in semi-
complete graphs. SIAM J. Disc. Math. 5, 3, 366–376.
BANSAL, N., BLUM, A., AND CHAWLA, S. 2004. Correlation clustering. Mach. Learn. J. (Special Issue on
Theoretical Advances in Data Clustering) 56, 1–3, 89–113. (Extended abstract appeared in FOCS 2002,
pages 238–247.)
BARTHOLDI, J., TOVEY, C. A., AND TRICK, M. 1989. Voting schemes for which it can be difficult to tell
who won the election. Social Choice Welf. 6, 2, 157–165.
BORDA, J. C. 1781. Mémoire sur les élections au scrutin. Histoire de l’Académie Royale des Sciences.
CAI, M.-C., DENG, X., AND ZANG, W. 2001. An approximation algorithm for feedback vertex sets in
tournaments. SIAM J. Comput. 30, 6, 1993–2007.
CHARIKAR, M., GURUSWAMI, V., AND WIRTH, A. 2003. Clustering with qualitative information. In Pro-
ceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS) (Boston,
MA). IEEE Computer Society Press, Los Alamitos, CA, 524–533.
CHAUDHURI, K., CHEN, K., MIHAESCU, R., AND RAO, S. 2006. On the tandem duplication-random loss
model of genome rearrangement. In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete
Algorithm (SODA’06). ACM, New York, 564–570.
CONDORCET, M.-J. 1785. Éssai sur l’application de l’analyse à la probabilité des décisions rendues à la
pluralité des voix.
COPPERSMITH, D., FLEISCHER, L., AND RUDRA, A. 2006. Ordering by weighted number of wins gives a
good ranking for weighted tournaments. In Proceedings of the 17th Annual ACM-SIAM Symposium on
Discrete Algorithm (SODA’06). ACM, New York, 776–782.
DIACONIS, P., AND GRAHAM, R. 1977. Spearman’s footrule as a measure of disarray. J. Roy. Stat. Soc.,
Ser. B 39, 2, 262–268.
DINUR, I., AND SAFRA, S. 2002. On the importance of being biased. In Proceedings of the 34th Annual
Symposium on the Theory of Compututing (STOC). ACM, New York, 33–42.
DWORK, C., KUMAR, R., NAOR, M., AND SIVAKUMAR, D. 2001a. Rank aggregation methods for the web.
In Proceedings of the 10th International Conference on the World Wide Web (WWW10) (Hong Kong,
China), 613–622.
DWORK, C., KUMAR, R., NAOR, M., AND SIVAKUMAR, D. 2001b. Rank aggregation revisited. Manuscript.
(Available from: [Link]
EVEN, G., NAOR, J. S., SUDAN, M., AND SCHIEBER, B. 1998. Approximating minimum feedback sets and
multicuts in directed graphs. Algorithmica 20, 2, 151–174.
FAGIN, R., KUMAR, R., AND SIVAKUMAR, D. 2003. Efficient similarity search and classification via rank
aggregation. In Proceedings of the 2003 ACM SIGMOD International Conference on Management of
Data (San Diego, CA). ACM, New York, 301–312.
FILKOV, V., AND SKIENA, S. 2003. Integrating microarray data by consensus clustering. In Proceedings of
International Conference on Tools with Artificial Intelligence (ICTAI) (Sacramento, CA). 418–425.
FRIEZE, A., AND KANNAN, R. 1999. Quick approximations to matrices and applications. Combinator-
ica 19, 2, 175–220.
GIONIS, A., MANNILA, H., AND TSAPARAS, P. 2005. Clustering aggregation. In Proceedings of the 21st
International Conference on Data Engineering (ICDE) (Tokyo, Japan).
HÄSTAD, J. 2001. Some optimal inapproximability results. J. ACM 48, 798–859.
KARP, R. M. 1972. Reducibility among combinatorial problems. In Complexity of Computer Computa-
tions. Plenum Press, New York, 85–104.

Journal of the ACM, Vol. 55, No. 5, Article 23, Publication date: October 2008.
Aggregating Inconsistent Information: Ranking and Clustering 23:27

KEMENY, J. G. 1959. Mathematics without numbers. Daedalus 88, 571–591.

KEMENY, J., AND SNELL, J. 1962. Mathematical Models in the Social Sciences. Blaisdell, New York.
(Reprinted by MIT Press, Cambridge, 1972.)
KENYON-MATHIEU, C., AND SCHUDY, W. 2007. How to rank with few errors. In Proceedings of the 39th
Annual ACM Symposium on Theory of Computing (STOC) (New York, NY). ACM, New York, 95–103.
NEWMAN, A. 2000. Approximating the maximum acyclic subgraph. M.S. thesis, Massachusetts Institute
of Technology, Cambridge, MA.
NEWMAN, A., AND VEMPALA, S. 2001. Fences are futile: On relaxations for the linear ordering problem.
In Proceedings of the 8th Conference on Integer Programming and Combinatorial Optimization (IPCO).
333–347.
POTTS, C. N. 1980. An algorithm for the single machine sequencing problem with precedence constraints.
Math. Prog. 13, 78–87.
SEYMOUR, P. 1995. Packing directed circuits fractionally. Combinatorica 15, 281–288.
SPECKENMEYER, E. 1989. On feedback problems in digraphs. Graph Theoretic Concepts in Computer
Science, Lecture Notes in Computer Science, vol. 411, Springer-Verlag, New York, 218–231.
STREHL, A. 2002. PhD dissertation. Ph.D. thesis, University of Texas at Austin.
WAKABAYASHI, Y. 1998. The complexity of computing medians of relations. Resenhas 3, 3, 323–349.
WILLIAMSON, D. P., AND VAN ZUYLEN, A. 2007. Deterministic algorithms for rank aggregation and other
ranking and clustering problems. In Proceedings of the 5th Workshop on Approximation and Online
Algorithms (WAOA).

RECEIVED JANUARY 2006; REVISED MAY 2008; ACCEPTED AUGUST 2008

Journal of the ACM, Vol. 55, No. 5, Article 23, Publication date: October 2008.