Paper Info
Title
Deterministic algorithms for rank aggregation and other ranking and clustering problems
Abstract
We consider ranking and clustering problems related to the aggregation of inconsistent information. Ailon, Charikar, and Newman [1] proposed randomized constant factor approximation algorithms for these problems. Together with Hegde and Jain, we recently proposed deterministic versions of some of these randomized algorithms [2]. With one exception, these algorithms required the solution of a linear programming relaxation. In this paper, we introduce a purely combinatorial deterministic pivoting algorithm for weighted ranking problems with weights that satisfy the triangle inequality; our analysis is quite simple. We then shown how to use this algorithm to get the first deterministic combinatorial approximation algorithm for the partial rank aggregation problem with performance guarantee better than 2. In addition, we extend our approach to the linear programming based algorithms in Ailon et al. [1] and Ailon [3]. Finally, we show that constrained rank aggregation is not harder than unconstrained rank aggregation.
Year
DOI
Venue
2007
10.1007/978-3-540-77918-6_21
WAOA
Keywords
Field
DocType
deterministic algorithm,randomized algorithm,linear programming,deterministic version,rank aggregation,partial rank aggregation problem,deterministic combinatorial approximation algorithm,approximation algorithm,combinatorial deterministic,unconstrained rank aggregation,clustering problem,linear programming relaxation,linear program,satisfiability,triangle inequality
Approximation algorithm,Randomized algorithm,Aggregation problem,Combinatorics,Mathematical optimization,Ranking,Computer science,Algorithm,Linear programming,Triangle inequality,Linear programming relaxation,Cluster analysis
Conference
Volume
ISSN
ISBN
4927
0302-9743
3-540-77917-5
Citations 
PageRank 
References 
33
1.90
10
Authors
2
Name
Order
Citations
PageRank
Anke Van Zuylen129122.10
David P. Williamson23564413.34