Files in this item



application/pdf8600277.pdf (3MB)Restricted to U of Illinois
(no description provided)PDF


Title:Flow Optimization in Dynamic and Continuous Networks (Polymatroids, Submodular, Max-Flow Min-Cut)
Author(s):Ogier, Richard Gregory
Department / Program:Electrical Engineering
Discipline:Electrical Engineering
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(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.
Issue Date:1985
Description:111 p.
Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1985.
Other Identifier(s):(UMI)AAI8600277
Date Available in IDEALS:2014-12-15
Date Deposited:1985

This item appears in the following Collection(s)

Item Statistics