Greedy packing and series-parallel graphs

Alan J. Hoffman; Alan C. Tucker

doi:10.1016/0097-3165(88)90039-8

Greedy packing and series-parallel graphs

Alan J. Hoffman
, Alan C. Tucker

Applied Mathematics and Statistics

IBM

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

4 Scopus citations

Abstract

We characterize nonnegative matrices A with the following property: for every a ≧ 0, the linear programming problem max(1, y), where Ay ≦ 0, y ≧ 0, is solved by successively maximizing the variables in arbitrary order. The concept of series-parallel graphs is central to the characterization.

Original language	English
Pages (from-to)	6-15
Number of pages	10
Journal	Journal of Combinatorial Theory, Series A
Volume	47
Issue number	1
DOIs	https://doi.org/10.1016/0097-3165(88)90039-8
State	Published - Jan 1988

Access to Document

10.1016/0097-3165(88)90039-8

Cite this

@article{26a542a195124e8497ed01e2ff986397,

title = "Greedy packing and series-parallel graphs",

abstract = "We characterize nonnegative matrices A with the following property: for every a ≧ 0, the linear programming problem max(1, y), where Ay ≦ 0, y ≧ 0, is solved by successively maximizing the variables in arbitrary order. The concept of series-parallel graphs is central to the characterization.",

author = "Hoffman, \{Alan J.\} and Tucker, \{Alan C.\}",

year = "1988",

month = jan,

doi = "10.1016/0097-3165(88)90039-8",

language = "English",

volume = "47",

pages = "6--15",

journal = "Journal of Combinatorial Theory, Series A",

issn = "0097-3165",

number = "1",

}

TY - JOUR

T1 - Greedy packing and series-parallel graphs

AU - Hoffman, Alan J.

AU - Tucker, Alan C.

PY - 1988/1

Y1 - 1988/1

N2 - We characterize nonnegative matrices A with the following property: for every a ≧ 0, the linear programming problem max(1, y), where Ay ≦ 0, y ≧ 0, is solved by successively maximizing the variables in arbitrary order. The concept of series-parallel graphs is central to the characterization.

AB - We characterize nonnegative matrices A with the following property: for every a ≧ 0, the linear programming problem max(1, y), where Ay ≦ 0, y ≧ 0, is solved by successively maximizing the variables in arbitrary order. The concept of series-parallel graphs is central to the characterization.

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

U2 - 10.1016/0097-3165(88)90039-8

DO - 10.1016/0097-3165(88)90039-8

M3 - Article

AN - SCOPUS:38249032488

SN - 0097-3165

VL - 47

SP - 6

EP - 15

JO - Journal of Combinatorial Theory, Series A

JF - Journal of Combinatorial Theory, Series A

IS - 1

ER -

Greedy packing and series-parallel graphs

Abstract

Access to Document

Other files and links

Fingerprint

Cite this