Integer equal flows

Carol A. Meyers; Andreas S. Schulz

doi:10.1016/j.orl.2009.03.006

Integer equal flows

Carol A. Meyers
, Andreas S. Schulz

Lawrence Livermore National Laboratory
Massachusetts Institute of Technology

Research output: Contribution to journal › Article › peer-review

15 Scopus citations

Abstract

The integer equal flow problem is an NP-hard network flow problem, in which all arcs in given sets R₁, ..., R_ℓ must carry equal flow. We show that this problem is effectively inapproximable, even if the cardinality of each set R_k is two. When ℓ is fixed, it is solvable in polynomial time.

Original language	English
Pages (from-to)	245-249
Number of pages	5
Journal	Operations Research Letters
Volume	37
Issue number	4
DOIs	https://doi.org/10.1016/j.orl.2009.03.006
State	Published - Jul 2009
Externally published	Yes

Keywords

Approximability
Computational complexity
Equal flows
Network optimization

Access to Document

10.1016/j.orl.2009.03.006

Cite this

@article{a7113cf45c444426adeef69a0a622edf,

title = "Integer equal flows",

abstract = "The integer equal flow problem is an NP-hard network flow problem, in which all arcs in given sets R1, ..., Rℓ must carry equal flow. We show that this problem is effectively inapproximable, even if the cardinality of each set Rk is two. When ℓ is fixed, it is solvable in polynomial time.",

keywords = "Approximability, Computational complexity, Equal flows, Network optimization",

author = "Meyers, \{Carol A.\} and Schulz, \{Andreas S.\}",

year = "2009",

month = jul,

doi = "10.1016/j.orl.2009.03.006",

language = "English",

volume = "37",

pages = "245--249",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier B.V.",

number = "4",

}

TY - JOUR

T1 - Integer equal flows

AU - Meyers, Carol A.

AU - Schulz, Andreas S.

PY - 2009/7

Y1 - 2009/7

N2 - The integer equal flow problem is an NP-hard network flow problem, in which all arcs in given sets R1, ..., Rℓ must carry equal flow. We show that this problem is effectively inapproximable, even if the cardinality of each set Rk is two. When ℓ is fixed, it is solvable in polynomial time.

AB - The integer equal flow problem is an NP-hard network flow problem, in which all arcs in given sets R1, ..., Rℓ must carry equal flow. We show that this problem is effectively inapproximable, even if the cardinality of each set Rk is two. When ℓ is fixed, it is solvable in polynomial time.

KW - Approximability

KW - Computational complexity

KW - Equal flows

KW - Network optimization

UR - https://www.scopus.com/pages/publications/67449149686

U2 - 10.1016/j.orl.2009.03.006

DO - 10.1016/j.orl.2009.03.006

M3 - Article

AN - SCOPUS:67449149686

SN - 0167-6377

VL - 37

SP - 245

EP - 249

JO - Operations Research Letters

JF - Operations Research Letters

IS - 4

ER -

Integer equal flows

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this