How to compute least infeasible flows

How to compute least infeasible flows

0.00 Avg rating0 Votes
Article ID: iaor1999862
Country: Netherlands
Volume: 78
Issue: 2
Start Page Number: 179
End Page Number: 194
Publication Date: Aug 1997
Journal: Mathematical Programming
Authors:
Keywords: networks, programming: network
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.

Reviews

Required fields are marked *. Your email address will not be published.