Partitions. Optimality and clustering. Vol. II: Multi-parameter. (Q2842220)

For the first volume, see [the first two authors, Partitions. Optimality and clustering. Volume I: Single-parameter. Series on Applied Mathematics 19. Hackensack, NJ: World Scientific (2012; Zbl 1244.90003)].NEWLINENEWLINE This is the 2nd volume of\ a book on optimal partition problems. A \(p\)-partition of a finite set \(\mathcal{A}\)\ is a family of \(p\) pairwise disjoint subsets of \(\mathcal{A}\)\ whose union is \(\mathcal{A}.\) An optimal \( p\)-partition problem consists of computing the extrema of a given (objective) function \(F:\Pi \rightarrow \mathbb{R}\) defined on a familly \( \Pi \) of \(p\)-partitions of \(\mathcal{A}\). Volume I deals with those optimal partition problems in which the elements of \(\Pi \) can be described by means of one parameter, in which case \(\mathcal{A}\) can be replaced by the set \( \mathcal{N}=\left\{ 1,\dots,n\right\}\), where \(n\) represents the cardinality of \(\mathcal{A}.\) Volume II is the multiparameter counterpart of Volume I, i.e., it assumes that \(\mathcal{A\subset }\mathbb{R}^{d}\) for some \(d\geq 2\). In this general framework the elements of \(\mathcal{A}\) are indexed as \( A^{1},\dots,A^{n}\), where we may have \(A^{i}=A^{j}\) for any \(i\neq j\). Two desirable properties of \(\mathcal{A}\) are distictness and genericity: a finite set \(\mathcal{A}\) is distinct when \(A^{i}\neq A^{j}\) for \(i\neq j\), and it is generic, whenever any subset of \(d+1\) elements of \(\mathcal{A}\) is affinely independent. This volume also considers partitions containing the empty set.NEWLINENEWLINEChapter 1 is devoted to the sum-partition problem. To each \(p\)-partition \( \pi =\left( \pi _{1},\dots,\pi _{p}\right) \in \Pi \) is associated a matrix \( A_{\pi }\in \mathbb{R}^{d\times p}\) whose columns are the sums of the vectors belonging to each element of the partition, i.e., \( \sum_{A\in \pi _{1}}A,\dots,\sum_{A\in \pi _{p}}A\in \mathbb{R}^{d}\). Then, the optimal partition problem corresponding to a given function \(f:\mathbb{R}^{d\times p}\rightarrow \mathbb{R}\) consists of maximizing the real-valued mapping \(F\) such that \(F\left( \pi \right) =f\left( A_{\pi }\right) \) for \(\pi =\left( \pi _{1},\dots\pi _{p}\right) \in \Pi \). Under suitable assumptions, this problem is reformulated as the maximization of a linear functional on the convex hull of the columns of \( A_{\pi }\), say \(\text{conv}A_{\pi }\) (the so-called partition polytope), \( \pi \in \Pi \). This is a linear programming problem to be solved with some enumeration technique.NEWLINENEWLINEChapter 2 considers two particular types of sum-partition problems. In the constrained-shape sum-partition problem the function \(f\) satisfies convex-like properties, e.g. edge-quasiconvexity. The key concepts for this problem are those of separable and almost-separable partitions. Two sets \( C,D\in \mathbb{R}^{p}\) are separable (almost-separable) if there exists a vector \(w\in \mathbb{R}^{p}\) such that \(w^{T}c<w^{T}d\) \(\forall c\in C,\,\forall d\in D\) (\(\forall c\in C,\,\forall d\in D\) such that \(c\neq d\), respectively). A \(p\)-partition \(\pi =\left( \pi _{1},\dots,\pi _{p}\right) \in \Pi \) is separable (almost-separable), whenever \(\text{conv}A_{\pi _{i}}\) and \(\text{conv}A_{\pi _{j}}\) are separable (almost-separable, respectively), when \(i\neq j\). These problems are reducible to generalized transportation problems by representing the partition polytopes as projections of generalized transportation-polytopes. A single-size problem consists of a sum-partition problem where some single element has a prescribed size. The treatment of this problem is similar to the one given to the constrained-shape one, but now the main tool is the concept of cone-separable partition. Two sets \(C,D\in \mathbb{R}^{p}\) are cone-separable if there exists a vector \(w\in \mathbb{R}^{p}\) such that \( w^{T}c<0<w^{T}d\) \(\forall c\in C\diagdown \left\{ 0\right\}\, ,\forall d\in D\diagdown \left\{ 0\right\} \). Accordingly, a \(p\)-partition \(\pi =\left( \pi _{1},\dots\pi _{p}\right) \in \Pi \) is cone-separable, whenever the sets of colunns of \(A_{\pi _{i}}\) and \(A_{\pi _{j}}\) (or, equivalently, their convex conical hulls \(\text{cone}A_{\pi _{i}}\) and \(\text{cone}A_{\pi _{j}}\) )\ are cone-separable, when \(i\neq j\). The cone-separable partitions can be enumerated under different assumptions.NEWLINENEWLINEChapter 3, on partitions over multiparameter spaces, deals with optimal partition problems which cannot be classified as sum-partition ones, so that the polyhedral approach in Chapters 1 and 2 does not apply. This chapter can be seen as an extension of Chapters 6 and 7 in Volume I, also making use of the combinatorial approach.NEWLINENEWLINEChapter 4 is focused on clustering problems where a function \(F\) involving distances between the vectors \(A^{i}\), \(i=1,\dots,n\), for each partition \(\pi =\left( \pi _{1},\dots\pi _{p}\right) \in \Pi \) is to be minimized. This chapter can be seen as an extension to the multiparameter setting of the results and methods of Section 5.4 and Chapter 7 of Volume 1.NEWLINENEWLINEChapters 1--4 extend the partition models of Volume I to the general framework of multiparameter spaces. In Chapter 5 of Volume II, the set \( \mathcal{N}=\left\{ 1,\dots,n\right\} \mathcal{\;}\) is divided a priori into subsets \(\mathcal{N}_{u}\), \(u=1,\dots t\), which are formed by different types of elements of \(\mathcal{N}\). Partitioning each \(\mathcal{N}_{u}\), we get a multipartition of \(\mathcal{N}\). The methodology of this chapter is a suitable adaptation to the one used in Volume I.NEWLINENEWLINEFinally, Chapter 6 shows the application of the results and methods gathered by the authors in Chapters 1--5 to a collection of optimal partition problems introduced in Section 1.4 of Volume I, namely: assembly of systems, group testing, circuit card library, clustering, abstraction of finite state machines, multischeduling problems, cache assignment, the blood analyzer problem, joint replenishment of inventories, statistical hypothesis testing, nearest neighbor assignment, graph partitions, traveling salesman problems, vehicle routing problems, division property problems, and the consolidation of farm lands.NEWLINENEWLINEThis advanced book presents recent theoretical developments as well as classical and new methods. It also contains some illustrative examples, but not exercises or problems to be solved by the reader. This book, which will become a reference for the researchers in the field, could also be useful in master and doctoral courses.