Placeholder for forthcoming answer before question gets inadvertently closed. Editing currently in progress.

I think what is wanted is a k-means algorithm or something similar for optimizing the cost. Let's look at it in terms of packing books.

I am able to order k boxes for packing my (long) shelf of n books. Many aspects of my order have low cost, but one aspect which I want to optimize is space-height. So when I pack books in a box, they should all be about the same height; I can pad or adjust for depth and width cheaply, but I need to get the height optimally arranged for my order of boxes.

How do I organize the books? I arrange them in order from smallest to largest height, then I make divisions into k groups of equal numbers to start. Then I compute the cost of ordering k boxes for this grouping as a threshold. Then for each book which is the tallest or shortest in the group, I shift it from one stack to an adjoining stack, and recompute my cost function. If I lower the cost by moving the book, the book gets assigned to the new stack.

I iterate this (moving an end book from one stack to an adjacent stack) among the k stacks until I achieve a satisfactory optimum. This is not quite a k-means clustering algorithm, but it shows the basic idea.

For the stated problem, it might be useful to go one of two ways: have the cost function (aA+bE

I think what is wanted is a k-means algorithm or something similar for optimizing the cost. Let's look at it in terms of packing books.

I am able to order k boxes for packing my (long) shelf of n books. Many aspects of my order have low cost, but one aspect which I want to optimize is space-height. So when I pack books in a box, the books should all be about the same height; I can pad or adjust for depth and width cheaply, but I need to get the height optimally arranged for my order of boxes.

How do I organize the books? I arrange them in order from smallest to largest height, then I make divisions into k groups of equal numbers of books to start. Then I compute the cost of ordering k boxes for this grouping as a threshold. Then for each book which is the tallest or shortest in the group, I shift it from one stack to an adjoining stack, and recompute my cost function. If I lower the cost by moving the book, the book gets assigned to the new stack.

I iterate this (moving an end book from one stack to an adjacent stack) among the k stacks until I achieve a satisfactory optimum. This is not quite a k-means clustering algorithm, but it shows the basic idea.

For the stated problem, it might be useful to go one of two ways: have the cost function (aA+bB+cC) be the "height" of the book that is the value to do the k-means clustering, or (since the original algorithm worked on grouping n-dimensional data points into clusters) work on grouping the triples into clusters, and then applying the cost function and massage the clusters for improved solutions.

I do not claim that this is the best or most efficient algorithm for this problem. However, k-means clustering seems to be the natural approach (even though a local sup, not a mean or average, is wanted).

Gerhard "Applying Himself To Applied Math" Paseman, 2018.08.18.

Placeholder for forthcoming answer before question gets inadvertently closed. Editing currently in progress.

Placeholder for forthcoming answer before question gets inadvertently closed. Editing currently in progress.

I think what is wanted is a k-means algorithm or something similar for optimizing the cost. Let's look at it in terms of packing books.

I am able to order k boxes for packing my (long) shelf of n books. Many aspects of my order have low cost, but one aspect which I want to optimize is space-height. So when I pack books in a box, they should all be about the same height; I can pad or adjust for depth and width cheaply, but I need to get the height optimally arranged for my order of boxes.

How do I organize the books? I arrange them in order from smallest to largest height, then I make divisions into k groups of equal numbers to start. Then I compute the cost of ordering k boxes for this grouping as a threshold. Then for each book which is the tallest or shortest in the group, I shift it from one stack to an adjoining stack, and recompute my cost function. If I lower the cost by moving the book, the book gets assigned to the new stack.

I iterate this (moving an end book from one stack to an adjacent stack) among the k stacks until I achieve a satisfactory optimum. This is not quite a k-means clustering algorithm, but it shows the basic idea.

For the stated problem, it might be useful to go one of two ways: have the cost function (aA+bE