Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
1143111 | Operations Research Letters | 2009 | 5 Pages |
Abstract
The integer equal flow problem is an NP-hard network flow problem, in which all arcs in given sets R1,…,RℓR1,…,Rℓ must carry equal flow. We show that this problem is effectively inapproximable, even if the cardinality of each set RkRk is two. When ℓℓ is fixed, it is solvable in polynomial time.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Carol A. Meyers, Andreas S. Schulz,