Flow Optimization in Dynamic and Continuous Networks (Polymatroids, Submodular, Max-Flow Min-Cut)
Ogier, Richard Gregory
This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.
Permalink
https://hdl.handle.net/2142/69328
Description
Title
Flow Optimization in Dynamic and Continuous Networks (Polymatroids, Submodular, Max-Flow Min-Cut)
Author(s)
Ogier, Richard Gregory
Issue Date
1985
Department of Study
Electrical Engineering
Discipline
Electrical Engineering
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
Computer Science
Abstract
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.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
