How to compute least infeasible flows |
| |
Authors: | S Thomas McCormick |
| |
Institution: | (1) Faculty of Commerce and Business Administration, University of British Columbia, V6T 1Z2 Vancouver, BC, Canada |
| |
Abstract: | It is well-known how to use maximum flow to decide when a flow problem with demands, lower bounds, and upper bounds is infeasible.
Less well-known is how to compute a flow that is least infeasible. This paper considers many possible ways to define “least
infeasible” and shows how to compute optimal flows for each definition. For each definition it also gives a dual characterization
in terms of cuts, a polynomial routine for recognizing that type of least infeasible flow, and relates that definition to
dual cut canceling min-cost flow network algorithms.
This research was partially supported by an NSERC Operating Grant, an NSERC Grant for Research Abroad, and a UBC Killam Faculty
Study Leave Fellowship. Parts of this research were done while the author was visiting Laboratoire ARTEMIS IMAG at Université
Joseph Fourier de Grenoble, France. |
| |
Keywords: | Network flows Min-cost flow Cut canceling |
本文献已被 SpringerLink 等数据库收录! |
|