How to compute least infeasible flows
McCormick, S. Thomas

Data: 1997
Resum: 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. .
Drets: Tots els drets reservats.
Llengua: Anglès
Document: Article ; recerca ; Versió publicada
Matèria: Network flows ; Min-cost flow ; Cut canceling
Publicat a: Mathematical Programming, vol. 78 n. 2 (1997) p. 179-194, ISSN 0025-5610



16 p, 999.8 KB
 Accés restringit a la UAB

El registre apareix a les col·leccions:
Articles > Articles de recerca
Articles > Articles publicats

 Registre creat el 2006-03-13, darrera modificació el 2023-06-03



   Favorit i Compartir