An efficient algorithm for solving a special class of LP's (Q1074311)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: An efficient algorithm for solving a special class of LP's |
scientific article; zbMATH DE number 3947543
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | An efficient algorithm for solving a special class of LP's |
scientific article; zbMATH DE number 3947543 |
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
