Brown Bag Seminar - February 15, 2005
Speaker: Fabio Tardella
Affiliation: Department of Mathematics for Economics Finance and Insurance, University of Rome "La Sapienza"
Title: Submodular function minimization in Zn and searching in Monge arrays
Time: 12:00 - 1:00 PM
Location: RUTCOR Building - Lounge, Rutgers University, Busch
Campus, Piscataway, NJ
Abstract:
The theory and applications of submodular function minimization on
(a sublattice of) the 0-1 hypercube has been thoroughly investigated in
the last three decades. However, submodularity does appear and is usefully
exploited in more general settings, possibly with different names.
We consider the problem of minimizing a submodular function on a
sublattice of Zn and we establish and use connections among
this problem, the problem of searching in a multidimensional Monge array
(arising in Computer Science and Computational Geometry), and submodular
pseudo-Boolean function minimization.
In particular, we obtain the first algorithm for minimizing a submodular
function on a sublattice S of Zn a with time complexity
polynomial in the length of a maximal chain of S, and we use it to construct
a polynomial algorithm (regarded as a "major improvement'' by Aggarwal and
Park) for the problem of searching in a multidimensional Monge array.
We then show that submodular function minimization in Zn can be
applied to solve efficiently some linear and nonlinear IPs that include
Hochbaum's "monotone" IPs with two or three variables per inequality, and
can be used to establish polinomiality for the problem of minimizing a
linear function on (extensions of) Fujishige's Ternary Submodular
Polyhedra.
Joint work with Maurice Queyranne.
Back to Seminars Page.
Back to RUTCOR homepage.
| 
