Good Clusterings Have Large Volume

References

• Aloise D, Deshpande A, Hansen P, Popat P (2009) NP-hardness of Euclidean sum-of-squares clustering. Machine Learn. 75(2):245–249.Crossref, Google Scholar
• Anderes E, Borgwardt S, Miller J (2016) Discrete Wasserstein barycenters: Optimal transport for discrete data. Math. Methods Oper. Res. 84(2):389–409.Crossref, Google Scholar
• Aurenhammer F (1987) Power diagrams: Properties, algorithms and applications. SIAM J. Comput. 16(1):78–96.Crossref, Google Scholar
• Aurenhammer F, Hoffmann F, Aronov B (1998) Minkowski-type theorems and least-squares clustering. Algorithmica 20(1):61–76.Crossref, Google Scholar
• Aviran S, Lev-Tov N, Onn S, Rothblum UG (2002) Vertex characterization of partition polytopes of bipartitions and of planar point sets. Discrete Appl. Math. 124(1):1–15.Crossref, Google Scholar
• Balinski M, Russakoff A (1974) On the assignment polytope. SIAM Rev. 16(4):516–525.Crossref, Google Scholar
• Barnes ER, Hoffman AJ, Rothblum UG (1992) Optimal partitions having disjoint convex and conic hulls. Math. Programming 54(1):69–86.Crossref, Google Scholar
• Bennett KP, Mangasarian OL (1992) Multicategory discrimination via linear programming. Optim. Methods Software 3(1–3):27–39.Crossref, Google Scholar
• Berkhin P (2002) Survey of clustering data mining techniques. Technical report, Accrue Software, San Jose, CA.Google Scholar
• Bonifas N, Di Summa M, Eisenbrand F, Hähnle N, Niemeier M (2014) On sub-determinants and the diameter of polyhedra. Discrete Comput. Geometry 52(1):102–115.Crossref, Google Scholar
• Borgwardt S (2010) A combinatorial optimization approach to constrained clustering. Dissertation, Technische Universität München, München, Germany.Google Scholar
• Borgwardt S (2015) On soft power diagrams. J. Math. Model. Algorithms Oper. Res. 14(2):173–196.Crossref, Google Scholar
• Brieden A, Gritzmann P (2012) On optimal weighted balanced clusterings: Gravity bodies and power diagrams. SIAM J. Discrete Math. 26(2):415–434.Crossref, Google Scholar
• Cousins B (2015) Volume computation of convex bodies. MATLAB Function. Accessed June 2017, http://www.mathworks.com/matlabcentral/fileexchange/43596-volume-computation-of-convex-bodies.Google Scholar
• De Loera JA, Kim ED (2014) Combinatorics and geometry of transportation polytopes: An update. Barg A, Musin OR, eds. Discrete Geometry and Algebraic Combinatorics, Contemporary Mathematics, vol. 625 (American Mathematical Society, Providence, RI), 37–76.Google Scholar
• Doignon JP, Regenwetter M (1997) An approval-voting polytope for linear orders. J. Math. Psych. 41(2):171–188.Crossref, Google Scholar
• Fukuda K, Onn S, Rosta V (2003) An adaptive algorithm for vector partitioning. J. Global Optim. 25(3):305–319.Crossref, Google Scholar
• Gao B, Hwang FK, Li WCW, Rothblum UG (1999) Partition polytopes over 1-dimensional points. Math. Programming 85(2):335–362.Crossref, Google Scholar
• Gill J, Linusson S (2009) The k-assignment polytope. Discrete Optim. 6(2):148–161.Crossref, Google Scholar
• Gottlieb ES, Rao MR (1990) The generalized assignment problem: Valid inequalities and facets. Math. Programming 46(1):31–52.Crossref, Google Scholar
• Grötschel M, Wakabayashi Y (1990) Facets of the clique partitioning polytope. Math. Programming 47(1):367–387.Crossref, Google Scholar
• Guralnick R, Perkinson D (2006) Permutation polytopes and indecomposable elements in permutation groups. J. Combin. Theory Ser. A 113(7):1243–1256.Crossref, Google Scholar
• Happach F (2016) Stable clusterings and the cones of outer normals. Master’s thesis, Technische Universität München, München, Germany.Google Scholar
• Hwang FK, Onn S, Rothblum UG (1998) Representations and characterizations of vertices of bounded-shape partition polytopes. Linear Algebra Appl. 278(1):263–284.Crossref, Google Scholar
• Jain AK, Murty MN, Flynn PJ (1999) Data clustering—A review. ACM Comput. Surveys 31(3):264–323.Crossref, Google Scholar
• Kalman A (2014) Newton polytopes of cluster variables. Dissertation, University of California, Berkeley, Berkeley.Google Scholar
• Lloyd SP (1982) Least squares quantization in PCM. IEEE Trans. Inform. Theory 28(2):129–137.Crossref, Google Scholar
• MacQueen JB (1967) Some methods of classification and analysis of multivariate observations. Proc. Fifth Berkeley Sympos. Math. Statist. Probab. (University of California Press, Berkeley), 281–297.Google Scholar
• Mahajan M, Nimbhorkar P, Varadarajan K (2012) The planar k-means problem is NP-hard. Theoret. Comput. Sci. 442:13–21.Crossref, Google Scholar
• Nemhauser GL, Wolsey LA (1999) Integer and Combinatorial Optimization (John Wiley & Sons, New York).Google Scholar
• Onn S (1993) Geometry, complexity, and combinatorics of permutation polytopes. J. Combin. Theory Ser. A 64(1):31–49.Crossref, Google Scholar
• Schrijver A (1986) Theory of Linear and Integer Programming (John Wiley & Sons, New York).Google Scholar
• Suck R (1992) Geometric and combinatorial properties of the polytope of binary choice probabilities. Math. Soc. Sci. 23(1):81–102.Crossref, Google Scholar
• Suck R (1997) Polytopes in measurement and data analysis. Review of Lectures on polytopes, by Günther M. Ziegler. J. Math. Psych. 41(3):299–303.Crossref, Google Scholar
• Vattani A (2011) k-Means requires exponentially many iterations even in the plane. Discrete Comput. Geometry 45(4):596–616.Crossref, Google Scholar
• von Luxburg U (2010) Clustering stability: An overview. Foundations Trends Machine Learn. 2(3):235–274.Google Scholar
• Xu R, Wunsch D (2005) Survey of clustering algorithms. IEEE Trans. Neural Networks 16(3):645–678.Crossref, Google Scholar
• Ziegler GM (1995) Lectures on Polytopes, Graduate Texts in Mathematics, vol. 152 (Springer, New York).Crossref, Google Scholar