April 23, 2013, 4:00pm
De Dennis Meng, Department of Electrical Engineering, University of Washington
Max-min Cost Flow Problem and Maximizing the Length of Geodesic via Convex Optimization
Abstract: Given a graph with edge weights or a continuous field with metric, we can find the shortest path/geodesic between a source set and destination set. In a variety of applications including network interdiction, geometric optics, landscape design, wild fire suppression, we want to design weights to change the geodesic such that all possible paths connecting the source set and destination set have the same length. In this talk, we consider the problem of optimizing weights to maximize the length of the geodesic. This problem turns out to be a convex optimization problem, and by using duality, the graph problem can be formulated as a network linear program and the discretized continuous problem can be formulated as a second-order cone program. Furthermore, we propose the convex formulation to a related but different problem: maximize the minimum total cost to transport a commodity from sources with assigned supplies to destinations with assigned demands. We show that our convex formulation is linked to the mass transportation prevention problem and traffic congestion problem which have been historically studied in the combinatorial formulation.