This cycle of seminars will be devoted to the
following general class of combinatorial optimization problems. Given
an undirected graph with n vertices, find a connected partition of its
vertex-set into a prescribed number p of classes (that is, each class
must induce a connected subgraph) that minimizes a given function of
the partition. Problems in this class arise in many applications in
the areas of Operations Research, Computer Science, Statistics,
Engineering, and even Geology and Botany. In particular, we shall
focus on equipartition and clustering problems on graphs. The
complexity of these problems depends, of course, on the nature both of
the graph and of the objective function. Finding optimal connected
partitions can be often done in strongly polynomial time if the graph
is a path, whereas it is almost invariably NP-hard for arbitrary
graphs even when p = 2. The case of trees is borderline and hence
quite interesting from the complexity viewpoint. The current state of
complexity results will be surveyed. The above class of problems lends
itself to a variety of solution strategies, including dynamic
programming, greedy and shifting algorithms, cutting planes, and
heuristics. Each seminar will focus on one of these strategies. We
shall also point out some surprising connections with theoretical
computer science and pure mathematics, including lattices, posets,
fixed points, combinatorial topology, Schur-convexity, submodularity,
and probability theory. Many of the results presented here are the
outcome of the speaker's joint research work with R. Becker, P.
Hansen, B. Jaumard, M. Lucertini, Y. Perl, and others.
In the first part of this opening talk we introduce the following general class of combinatorial optimization problems (which will be the subject of the present cycle of seminars). Given an undirected graph with n vertices,find a connected partition of its vertex-set into a prescribed number p of classes (that is, each class must induce a connected subgraph) that minimizes a given function of the partition. Special attention is paid to equipartition and clustering problems on graphs. Applications in Operations Research, Computer Science, Statistics, Engineering, and Natural Sciences will be briefly surveyed.
The second part is devoted to optimal partitioning
problems on paths. While a simple O (p*n**2) dynamic programming
algorithm is available for most objective functions of practical
significance, obtaining faster algorithms is often nontrivial and
sometimes it leads to unexpected connections with some branches of
pure mathematics. Using in different ways the idea of "trimming" the
dynamic programming network one obtains an O(p*n) algorithm for path
equipartition in the L1-norm, an expected O(n*n) algorithm for the
L2-norm, and an O(n) algorithm for certain clustering problems on
paths. Results about "getting connectedness for free" for special
classes of objective functions will also be presented.
The most useful techniques available for the exact
solution in polynomial time - when this is possible - of optimal
connected partitioning problems on trees are Greedy algorithms,
Shifting ones, and Dynamic Programming. The present talk will be
devoted to Greedy algorithms. These procedures, when the tree is a
star, find optimal solutions of equipartition problems for ALL
meaningful (i.e., Schur-convex) objective functions. In the case of
general trees, they still provide optimal solutions for certain
specific equipartition or clustering objective functions. Sometimes
-for example, for most uniform path partitioning - they work only
after a suitable pre-processing phase. In fact, studying certain
associated semimodular and locally boolean lattices, we show that the
Church-Rosser Property holds for the pre-processing phase. This has
important consequences both on the correctness and on the complexity
of such phase. Finally, one can obtain bounds on the worst-case
performance of greedy algorithms for certain NP-hard equipartition or
clustering problems on trees by exploiting the submodularity of their
objective functions.
Shifting algorithms, whose prototypes were developed by Perl, Schach and Becker in the early 80's, are a class of elegant polynomial-time procedures for the exact solution of certain connected partitioning problems on trees. At the beginning, all p-1 cuts of the initial partition sit on a dummy edge atop the root. At each iteration, one cut is down-shifted in order to improve the worst component (this move does not necessarily result in an improvement of the objective function). After that, one or more side-shifts of other cuts may be needed in order to maintain a certain Star Property - a necessary condition for a partition to be optimal. Although shifting algorithms are very simple to describe, their proof of correctness is far from being trivial and ultimately rests on the so-called Aboveness Property. Partition P' is said to be "above" partition P if P can be obtained from P' by a sequence of down-shifts of cuts. The main result is that at each iteration the current partition generated by a shifting algorithm is above some optimal partition (Aboveness Property). A "Bolzano-Weierstrass" argument shows that an optimal partition must be obtained at some point (although the algorithm may stop later). Broad classes of objective functions for which down-shifting algorithms and down-and-side-shifting ones work, respectively, were pointed out by Becker and Perl. We also describe a shifting algorithm for path equipartition in the Chebyshev norm, for which we prove a generalization of the Aboveness Property. Finally, we describe two shifting approximate algorithms for grid max-min equipartition, an NP-hard problem. We prove that one of them is asymptotically exact if certain pathologies do not occur during its execution.
Shifting algorithms, whose prototypes were developed
by Perl, Schach and Becker in the early 80's, are a class of elegant
polynomial-time procedures for the exact solution of certain connected
partitioning problems on trees. At the beginning, all p-1 cuts of the
initial partition sit on a dummy edge atop the root. At each
iteration, one cut is down-shifted in order to improve the worst
component (this move does not necessarily result in an improvement of
the objective function). After that, one or more side-shifts of other
cuts may be needed in order to maintain a certain Star Property - a
necessary condition for a partition to be optimal. Although shifting
algorithms are very simple to describe, their proof of correctness is
far from being trivial and ultimately rests on the so-called Aboveness
Property. Partition P' is said to be "above" partition P if P can be
obtained from P' by a sequence of down-shifts of cuts. The main result
is that at each iteration the current partition generated by a
shifting algorithm is above some optimal partition (Aboveness
Property). A "Bolzano-Weierstrass" argument shows that an optimal
partition must be obtained at some point (although the algorithm may
stop later). Broad classes of objective functions for which
down-shifting algorithms and down-and-side-shifting ones work,
respectively, were pointed out by Becker and Perl. We also describe a
shifting algorithm for path equipartition in the Chebyshev norm, for
which we prove a generalization of the Aboveness Property. Finally, we
describe two shifting approximate algorithms for grid max-min
equipartition, an NP-hard problem. We prove that one of them is
asymptotically exact if certain pathologies do not occur during its
execution.
In this talk we discuss the following problem. A joint-and-bar tree is a tree
embedded in the plane so that its vertices are small disjoint discs (joints)
and its edges are euclidean segments (bars). One wants to place a given number
p-1 of cuts in suitably chosen points along the edges (an edge may carry zero,
one, or several cuts) so as to maximize the smallest length of the p components
obtained in this way. After proving the existence of an optimal partition for
arbitrary real edge-lengths, we restrict our attention to trees with rational
edge-lengths. Under this assumption, we exhibit a pseudopolynomial reduction of
the above problem to a Discrete Max-min tree partitioning problem, which is
then
solved by the well-known shifting algorithm of Perl and Schach. The resulting
algorithm for the continuous problem is pseudopolynomial. However, we show that
the moves of the discrete algorithm (down-shifts of edges) can be grouped into
a polynomial number of stages in such a way that the transition from the
beginning to the end of each stage can be performed in polynomial time. In this
way, we are able to achieve (strongly) polynomial complexity. The resulting
algorithm can be viewed as an "animated movie" whose "frames" are the single
moves of the discrete shifting algorithm. Interestingly, concurrence arises in
the continuous shifting algorithm: several edges may be down-shifted at the
same time, although with different speeds. The correctness of the continuos
algorithm is inherited from that of the discrete algorithm via simulation: each
"move" of the former can be simulated by a sequence of moves in the latter.
Similar ideas can be applied to other combinatorial optimization problems,
e.g., continuous location on trees and network flows.
This talk - the last of the series - is devoted to connected partitions of arbitrary graphs. Connectivity requirements give rise to a system of exponentially many set covering constraints ( although one can show that O(n**2) variables and O(n**2) constraints suffice for trees). A row generation algorithm, based on this formulation, for max-split clustering of arbitrary graphs will be described. Exact optimal partitions have been obtained for instances up to 400 nodes.
A heuristic for general graphs and arbitrary (but graph-independent) objective functions will also be presented. Such heuristic alternates tree partitioning stages, where one solves (exactly or approximately) an optimal partitioning problem on a given spanning tree of the graph; and tree updating stages, where one moves from the current spanning tree to a better one. Finally, we discuss unweighted equipartition of graphs. An important result in this area states that if the graph is k-connected, there exists always a connected k-partition in which the components have prescribed cardinalities (in particular, if n is a multiple of k, one in which all cardinalities are equal to n/k). We shall sketch two proofs of this result: an elementary one due to Gyori, and a topological one due to Lovasz.
Return to the LSDO tutorial topics page