Norm statistics and the complexity of clustering problems

DOI10.1016/J.DAM.2009.01.003MaRDI QIDQ1026145zbMATH OpenOpenAlexFDO

Authors Beth Novick

Publication date 24 June 2009

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2009.01.003

zbMATH Keywords

clusteringNP-hardnessstring propertyweighted power means

Mathematics Subject Classification ID

Discrete location and assignment (90B80) Clustering in the social and behavioral sciences (91C20)

Review text

For applications to clustering problems, some properties of weighted \(p\)-power means, called ``\(l_p\)-statistics, \(p\geq1\), are considered first. Based on these generalized means, partitions \(B_1,\dots,B_m\) of a set of \(n>m\) scalar observations \(x_1,\dots,x_n\) are determined minimizing a weighted \(q\)-power mean criterion, where \(q\geq1\). Some properties of the resulting partitions, such as the ``string property, known from standard clustering theory are transferred to the present case of power mean estimates. Moreover, the NP-hardness of the optimization problem for finding an optimal partition is discussed. An application is mentioned.

Recommendations

• Size constrained distance clustering: separation properties and some complexity results
• scientific article; zbMATH DE number 2081029
• On complexity of some problems of cluster analysis of vector sequences
• NP-hardness of some max-min clustering problems
• NP-hardness of some quadratic Euclidean 2-clustering problems

Cites work

• A projection method for \(l_ p\) norm location-allocation problems
• Cluster Analysis and Mathematical Programming
• scientific article; zbMATH DE number 3678973 (Why is no real title available?)
• scientific article; zbMATH DE number 44281 (Why is no real title available?)
• scientific article; zbMATH DE number 3617544 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Integer Programming and the Theory of Grouping
• J-MEANS: A new local search heuristic for minimum sum of squares clustering
• On Grouping for Maximum Homogeneity
• Optimal Locations for a Class of Nonlinear, Single-Facility Location Problems on a Network
• Solving thep-Center problem with Tabu Search and Variable Neighborhood Search
• Variable neighborhood search

Cited in

(6)

• Optimal stratification and clustering on the line using the \(L_ 1\)- norm
• On the complexity of redescription mining
• New perspectives on k-support and cluster norms
• Size constrained distance clustering: separation properties and some complexity results
• Exact algorithms for size constrained 2-clustering in the plane
• Statistical properties of convex clustering

Describes a project that uses

Uses Software

• J-MEANS

This page was built for publication: Norm statistics and the complexity of clustering problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1026145)