Aggregating inconsistent information

DOI10.1145/1060590.1060692zbMath1192.90252OpenAlexW2167372977WikidataQ57534949 ScholiaQ57534949MaRDI QIDQ5901110

Nir Ailon, Moses Charikar, Alantha Newman

Publication date: 16 August 2010

Published in: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1060590.1060692

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Directed graphs (digraphs), tournaments (05C20)

Related Items

Feedback arc set in bipartite tournaments is NP-complete, Aggregation of partial rankings, \(p\)-ratings and top-\(m\) lists, Feedback arc set problem in bipartite tournaments, Algorithms and kernels for \textsc{Feedback Set} problems in generalizations of tournaments, Hardness of fully dense problems, A survey on the linear ordering problem for weighted or unweighted tournaments, Cluster editing problem for points on the real line: a polynomial time algorithm, Efficient clustering of large uncertain graphs using neighborhood information, Heuristic stability: a permutation disarray measure, A polynomial kernel for \textsc{Feedback Arc Set} on bipartite tournaments, Correlation Clustering with Constrained Cluster Sizes and Extended Weights Bounds, Comparing multiagent systems research in combinatorial auctions and voting, Improved Algorithms for Bicluster Editing, Unnamed Item, Fixed-Parameter Algorithms for Kemeny Scores, Unnamed Item, Statistical ranking and combinatorial Hodge theory, Simple Iterative Heuristics for Correlation Clustering, Quasi-hamiltonian paths in semicomplete multipartite digraphs, Experiments with Kemeny ranking: What works when?, Ensemble clustering using semidefinite programming with applications, Preference-based learning to rank, Comparing and aggregating partially resolved trees, Kernels for feedback arc set in tournaments, On the approximation of correlation clustering and consensus clustering, Lower and upper bounds for the linear arrangement problem on interval graphs, Voting Procedures, Complexity of, Clustering with Local Restrictions, Cost-optimal constrained correlation clustering via weighted partial maximum satisfiability, An updated survey on the linear ordering problem for weighted or unweighted tournaments, Unnamed Item, A note on the inapproximability of correlation clustering, A randomized approximation algorithm for computing bucket orders, NP-hardness results for the aggregation of linear orders into median orders, Computer science and decision theory, Fixed-parameter algorithms for cluster vertex deletion, A note on generalized rank aggregation, Closest 4-leaf power is fixed-parameter tractable, Fixed-Parameter Algorithms for Cluster Vertex Deletion, A more effective linear kernelization for cluster editing, On the complexity of crossings in permutations, Aggregation and decision making using ranked data, Problems and conjectures concerning connectivity, paths, trees and cycles in tournament-like digraphs, Socially desirable approximations for dodgson’s voting rule, Tournaments and Semicomplete Digraphs