Aggregating inconsistent information: Ranking and clustering Export

@article{ailon2008aggregation, 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 disagreement 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 approximation 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.}, address = {New York, NY, USA}, author = {Ailon, Nir and Charikar, Moses and Newman, Alantha}, citeulike-article-id = {4342176}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=1411509.1411513}, citeulike-linkout-1 = {http://dx.doi.org/10.1145/1411509.1411513}, doi = {10.1145/1411509.1411513}, issn = {0004-5411}, journal = {J. ACM}, keywords = {aggregation, cluster, information, rank, ranking}, number = {5}, pages = {1--27}, posted-at = {2009-04-17 11:50:47}, priority = {2}, publisher = {ACM}, title = {Aggregating inconsistent information: Ranking and clustering}, url = {http://dx.doi.org/10.1145/1411509.1411513}, volume = {55}, year = {2008} }

TY - JOUR ID - ailon2008aggregation L3 - citeulike-article-id:4342176 N2 - 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 disagreement 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 approximation 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. IS - 5 JF - J. ACM SN - 0004-5411 AD - New York, NY, USA EP - 27 TI - Aggregating inconsistent information: Ranking and clustering PB - ACM VL - 55 SP - 1 KW - aggregation KW - cluster KW - information KW - rank KW - ranking AU - Ailon, Nir AU - Charikar, Moses AU - Newman, Alantha PY - 2008/// UR - http://dx.doi.org/10.1145/1411509.1411513 ER -