An efficient algorithm for solving a special class of LP's (Q1074311)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | An efficient algorithm for solving a special class of LP's |
scientific article |
Statements
An efficient algorithm for solving a special class of LP's (English)
0 references
1986
0 references
We consider LP's of the form max\(\{\) cx\(| \ell \leq Ax\leq b\), \(L\leq x\leq U\}\) where l,b,L,U are nonnegative and A is a 0-1 matrix which looks like ''Manhattan Skyline'', i.e. the support of each row is contained in the support of every subsequent row. An O(nm\(+n \log n)\) algorithm is presented for solving the problem.
0 references
0-1 matrix
0 references
Manhattan Skyline matrix
0 references
\(O(nm+n\,\log \,n)\) algorithm
0 references
