Flow Optimization in Dynamic and Continuous Networks (Polymatroids, Submodular, Max-Flow Min-Cut)

The main problem studied in this thesis is that of comparing a minimum-delay time-varying routing assignment in a dynamic network where the node demands and link capacities are deterministic functions of time, and where the commodity being routed is represented by continuous variables. A single node is designated to be the destination, and a (tau)-maximum flow is defined to be a routing assignment which maximizes the amount of commodity reaching the destination before time (tau). The key discovery used to solve the problem is that a routing assignment has minimum delay if and only if it is a (tau)-maximum flow for all (tau). When the capacities are constant or piecewise-constant, this discovery and the well-known max-flow min-cut theorem are used to divide the problem into two smaller problems. The result is a polynomial algorithm which finds a minimum-delay routing assignment by solving a series of static maximum-flow problems. In order to apply the above ideas to dynamic networks with continuously-varying capacities, a continuous network is defined whose flows and capacities are additive set functions, and a generalization of the max-flow min-cut theorem is proved. An even more general version of this theorem is proved for continuous network models whose capacities are submodular set functions. Various applications are considered, including the finite polymatroid networks of Lawler.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Electrical Engineering

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2014

Author dc:creator

• Ogier, Richard Gregory

• Computer Science

Identifier

(UMI)AAI8600277

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/69328