zbMATH — the first resource for mathematics

Deterministic pivoting algorithms for constrained ranking and clustering problems. (English) Zbl 1216.68343
Summary: We consider ranking and clustering problems related to the aggregation of inconsistent information, in particular, rank aggregation, (weighted) feedback arc set in tournaments, consensus and correlation clustering, and hierarchical clustering. In [N. Ailon, M. Charikar and A. Newman, in: Proceedings of the 37th annual ACM symposium on theory of computing (STOC). New York, NY: Association for Computing Machinery (ACM), 684–693 (2005; Zbl 1192.90252); N. Ailon and M. Charikar, in: Proceedings of the 46th annual IEEE symposium on foundations of computer science (FOCS). Los Alamitos, CA: IEEE Computer Society Press, 73–82 (2005); N. Ailon, in: Proceedings of the 18th annual ACM-SIAM symposium on discrete algorithms (SODA). New York, NY: Association for Computing Machinery (ACM); Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM), 415–424 (2007)], the authors proposed randomized constant factor approximation algorithms for these problems, which recursively generate a solution by choosing a random vertex as “pivot” and dividing the remaining vertices into two groups based on the pivot vertex. In this paper, we answer an open question in these works by giving deterministic approximation algorithms for these problems. The analysis of our algorithms is simpler than the analysis of the randomized algorithms. In addition, we consider the problem of finding minimum-cost rankings and clusterings that must obey certain constraints (e.g., an input partial order in the case of ranking problems), which were introduced by R. Hegde and K. Jain (2006, personal communication). We show that the first type of algorithms we propose can also handle these constrained problems. In addition, we show that in the case of a rank aggregation or consensus clustering problem, if the input rankings or clusterings obey the constraints, then we can always ensure that the output of any algorithm obeys the constraints without increasing the objective value of the solution.

68W25 Approximation algorithms
05C20 Directed graphs (digraphs), tournaments
68W40 Analysis of algorithms
91B12 Voting theory
Full Text: DOI