We discuss modern applied problems of discrete optimization at a mathematical level, and for one of them, clustering points in multidimensional real space, we examine in detail the algorithm for solving it. A characteristic feature of these problems is the large size of the initial data, often represented by matrices with tens of thousands of rows and tens of thousands of columns. This leads to problems of processing large amounts of data in the context of a complex computational algorithm; moreover, it is often essential to obtain a reasonably accurate solution to the problem quickly, so the question of the algorithm complexity is of fundamental importance. Solving such a clustering problem leads to difficult mathematical problems: removing hidden parameters; identifying significant features; switching to optimal and informationally significant point coordinates; specific representation (manifold maps) of the vertices of a weighted graph; selection of a function depending on the current clustering of vertices, the maximization of which leads to the desired clustering; for each cluster, selection of features that individually characterize it; and, finally, reduction of the dimensionality of the source data.
Lyubetsky et al. (Mon,) studied this question.