Deterministic Pivoting Algorithms for Constrained Ranking and Clustering Problems

References

• Agrawal M., Kayal N., Saxena N. PRIMES is in P. Ann. Math. (2004) 160(2):781–793Crossref, Google Scholar
• Ailon N. Aggregation of partial rankings, p-ratings and top-m lists. Proc. 18th Annual ACM-SIAM Sympos. Discrete Algorithms (SODA '07) (2007) 415–424Google Scholar
• Ailon N., Charikar M. Fitting tree metrics: Hierarchical clustering and phylogeny. Proc. 46th Annual IEEE Sympos. Foundations Comput. Sci. (FOCS '05) (2005) 73–82Crossref, Google Scholar
• Ailon N., Charikar M., Newman A. Aggregating inconsistent information: Ranking and clustering. J. ACM (2008) 55(5):1–27Crossref, Google Scholar
• Alon N. Ranking tournaments. SIAM J. Discret. Math. (2006) 20(1):137–142Crossref, Google Scholar
• Alon N., Spencer J. H. The probabilistic method. Wiley-Interscience Series in Discrete Mathematics and Optimization (2000) 2nd ed.(Wiley-Interscience [John Wiley & Sons], New York) Google Scholar
• Arora S., Frieze A. M., Kaplan H. A new rounding procedure for the assignment problem with applications to dense graph arrangement problems. Proc. 37th Annual IEEE Sympos. Foundations Comput. Sci. (FOCS '96) (1996) 21–30Crossref, Google Scholar
• Arrow K. J.Social Choice and Individual Values. Cowles Commission Monograph No. 12 (1951) (John Wiley & Sons, Inc., New York) Google Scholar
• Asuncion A., Newman D. J. UCI machine learning repository. (2007) . School of Information and Computer Science, University of California, Irvine. http://www.ics.uci.edu/∼mlearn/MLRepository.htmGoogle Scholar
• Bansal N., Blum A., Chawla S. Correlation clustering. Machine Learn. (2004) 56(1–3):89–113Crossref, Google Scholar
• Bartholdi J. J., Tovey C. A., Trick M. A. Voting schemes for which it can be difficult to tell who won the election. Soc. Choice Welfare (1989) 6:157–165Crossref, Google Scholar
• Charbit P., Thomassé S., Yeo A. The minimum feedback arc set problem is NP-hard for tournaments. Combin. Probab. Comput. (2007) 16(1):1–4Crossref, Google Scholar
• Charikar M., Guruswami V., Wirth A. Clustering with qualitative information. Proc. 44th Annual IEEE Sympos. Foundations Comput. Sci. (FOCS '03) (2003) 524–533Crossref, Google Scholar
• Conitzer V. Computing Slater rankings using similarities among candidates. Proc. 21st National Conf. Artificial Intelligence (AAAI'06) (2006) Google Scholar
• Coppersmith D., Fleischer L., Rudra A. Ordering by weighted number of wins gives a good ranking for weighted tournaments. Proc. 17th Annual ACM-SIAM Sympos. Discrete Algorithms (SODA '06) (2006) 776–782Crossref, Google Scholar
• Dwork C., Kumar R., Naor M., Sivakumar D. Rank aggregation methods for the Web. Proc. 10th Internat. Conf. World Wide Web (WWW '01) (2001) 613–622Crossref, Google Scholar
• Erdős P., Spencer J. Probabilistic methods in combinatorics. Probability and Mathematical Statistics (1974) 17(Academic Press [subsidiary of Harcourt Brace Jovanovich Publishers], New York and London) Google Scholar
• Even G., Naor J., Schieber B., Sudan M. Approximating minimum feedback sets and multicuts in directed graphs. Algorithmica (1998) 20(2):151–174Crossref, Google Scholar
• Fagin R., Kumar R., Mahdian M., Sivakumar D., Vee E. Comparing partial rankings. SIAM J. Discrete Math. (2006) 20(3):628–648Crossref, Google Scholar
• Filkov V., Skiena S. Integrating microarray data by consensus clustering. Proc. 15th IEEE Internat. Conf. Tools Artificial Intelligence (ICTAI '03) (2003) 418–425Crossref, Google Scholar
• Frieze A. M., Kannan R. Quick approximation to matrices and applications. Combinatorica (1999) 19(2):175–220Crossref, Google Scholar
• Gionis A., Mannila H., Tsaparas P. Clustering aggregation. ACM Trans. Knowledge Discovery Data (2007) 1(1):4Crossref, Google Scholar
• Goder A., Filkov V. Consensus clustering algorithms: Comparison and refinement. Proc. Workshop Algorithm Engrg. Experiments. (ALENEX '08) (2008) Crossref, Google Scholar
• Harb B., Kannan S., McGregor A. Approximating the best-fit tree under Lp norms. Approximation, Randomization and Combinatorial Optimization (2005) 3624(Springer, Berlin) 123–133Lecture Notes in Computer ScienceCrossref, Google Scholar
• Hegde R., Jain K. Personal communication. Google Scholar
• Karp R. M. Reducibility among combinatorial problems. Complexity of Computer Computations, Proc. Sympos. (1972) IBM Thomas J. Watson Research Center, Yorktown Heights, NY(Plenum, New York) 85–103Crossref, Google Scholar
• Kemeny J. G. Mathematics without numbers. Daedalus (1959) 88:575–591Google Scholar
• Kenyon-Mathieu C., Schudy W. How to rank with few errors. Proc. 39th Annual ACM Sympos. Theory Comput. (STOC '07) (2007) 95–103Crossref, Google Scholar
• Křivánek M., Morávek J. NP-hard problems in hierarchical-tree clustering. Acta Inform. (1986) 23(3):311–323Crossref, Google Scholar
• Modha D., Spangler S. Feature weighting in k-means clustering. Machine Learn. (2003) 52(3):217–237Crossref, Google Scholar
• Modha D. S., Spangler W. S. Clustering hypertext with applications to Web searching. Proc. 11th ACM Hypertext Hypermedia (HYPERTEXT '00) (2000) 143–152Crossref, Google Scholar
• Seymour P. D. Packing directed circuits fractionally. Combinatorica (1995) 15(2):281–288Crossref, Google Scholar
• Wakabayashi Y. The complexity of computing medians of relations. Resenhas (1998) 3(3):323–349Google Scholar
• Van Zuylen A., Williamson D. P. Deterministic algorithms for rank aggregation and other ranking and clustering problems. 5th International Workshop on Approximation and Online Algorithms (WAOA'07) (2008) 4927(Springer, Berlin) 260–273Lecture Notes in Computer ScienceCrossref, Google Scholar
• Van Zuylen A., Hegde R., Jain K., Williamson D. P. Deterministic pivoting algorithms for constrained ranking and clustering problems. Proc. 18th Annual ACM-SIAM Sympos. Discrete Algorithms (SODA '07) (2007) 405–414Google Scholar