| Article ID: | iaor2005729 |
| Country: | Netherlands |
| Volume: | 32 |
| Issue: | 6 |
| Start Page Number: | 540 |
| End Page Number: | 546 |
| Publication Date: | Nov 2004 |
| Journal: | Operations Research Letters |
| Authors: | Bar-Yehuda Reuven, Rawitz Dror |
| Keywords: | programming: integer |
We present local ratio interpretations of known algorithms for minimum s–t cut and the assignment problem. Our interpretations are the first application of local ratio with negative weights. These interpretations lead to primal–dual analyses that are based on new IP formulations.