Selected Topics in Large Scale Discrete Optimization


OPTIMAL CONECTED PARTITIONS OF GRAPHS

Bruno Simeone

Dipartimento di Statistica, Probabilità e Statistische Applicate, Università La Sapienza, Roma, Italy

DATES: April 9, 15, 21, 28 and May 5

TIME: 3-4 PM

DIMACS Center, CoRE Building, Room 431, Rutgers University

Refreshments will be served at 2:30 PM

Now with slide show!

Back to TUTORIALS main page



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.



Friday, April 9, 1999: Efficient path equipartition: trimming the dynamic programming network (With slide Show!)

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.

Thursday, April 15, 1999: Exact and approximate reedy algorithms for optimal tree partitioning (With slide Show!)

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.

Wednesday, April 21, 1999: Shifting algorithms for tree partitioning, and the Aboveness Property (With slide Show!)

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.

Wednesday, April 28, 1999: How to make a polynomial movie out of pseudo-polynomially many frames:  shifting algorithms for continouos tree partitioning (With slide Show!)

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.

Wednesday, May 5, 1999: Connected k-partitions in k-connected graphs: a topological approach (With slide Show!)

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.