Structured Partitioning Problems

From MaRDI portal





In many important combinatorial optimization problems, an optimal partition into groups needs to be determined for a finite collection of objects, each of which is characterized by a single attribute. The cost of a given partition is often separable in the groups and the group cost often depends on the cardinality and some aggregate measure of the attribute values in the group, e.g., the sum or the maximum element. The objective of this paper is to identify a nested set of simple conditions for the group cost function under which an optimal partition may be determined by increasingly simple, efficient algorithms that exploit increasingly stronger structural properties of this partition.











This page was built for publication: Structured Partitioning Problems

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