{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/69328"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/69328","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Flow Optimization in Dynamic and Continuous Networks (Polymatroids, Submodular, Max-Flow Min-Cut)","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.","abstract_html":"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.","abstract_has_math":false,"creators":["Ogier, Richard Gregory"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Electrical Engineering","degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2014,"date_issued":"2014-12-15T19:05:05Z","date_published":"2014-12-15T19:05:05Z","updated_at":"2026-07-22T22:26:00Z","subjects":["Computer Science"],"languages":[],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["(UMI)AAI8600277"],"render_values":[{"text":"(UMI)AAI8600277","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/69328","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Ogier, Richard Gregory"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2014-12-15T19:05:05Z","10000-01-01","1985"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Electrical Engineering"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Computer Science"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/69328","(UMI)AAI8600277"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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.","Made available in DSpace on 2014-12-15T19:05:05Z (GMT). No. of bitstreams: 1 8600277.pdf: 3240469 bytes, checksum: ca4601113be14faabba18275197cf081 (MD5) Previous issue date: 1985","Embargo set by: Seth Robbins for item 69494 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","U of I Only","111 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1985."]},{"key":"dc:title","label":"Title","values":["Flow Optimization in Dynamic and Continuous Networks (Polymatroids, Submodular, Max-Flow Min-Cut)"]}]}],"canonical_facts":{"dc:creator":["Ogier, Richard Gregory"],"dc:date":["2014-12-15T19:05:05Z","10000-01-01","1985"],"dc:description":["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.","Made available in DSpace on 2014-12-15T19:05:05Z (GMT). No. of bitstreams: 1 8600277.pdf: 3240469 bytes, checksum: ca4601113be14faabba18275197cf081 (MD5) Previous issue date: 1985","Embargo set by: Seth Robbins for item 69494 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","U of I Only","111 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1985."],"dc:identifier":["http://hdl.handle.net/2142/69328","(UMI)AAI8600277"],"dc:subject":["Computer Science"],"dc:title":["Flow Optimization in Dynamic and Continuous Networks (Polymatroids, Submodular, Max-Flow Min-Cut)"],"dc:type":["text"],"thesis:degree_discipline":["Electrical Engineering"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:26:00Z"}