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

Publikation: Beitrag in Fachzeitschrift › Artikel › Begutachtung

15 Zitate (Scopus)

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.

Originalsprache	Englisch
Seiten (von - bis)	245-249
Seitenumfang	5
Fachzeitschrift	Operations Research Letters
Jahrgang	37
Ausgabenummer	4
DOIs	https://doi.org/10.1016/j.orl.2009.03.006
Publikationsstatus	Veröffentlicht - Juli 2009
Extern publiziert	Ja

Zugriff auf Dokument

10.1016/j.orl.2009.03.006

Andere Dateien und Links

Verknüpfung zur Publikation in Scopus

Dieses zitieren

@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

Zugriff auf Dokument

Andere Dateien und Links

Fingerprint

Dieses zitieren