An efficient algorithm for solving a special class of LP's (Q1074311): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
| Property / cites work | |||
| Property / cites work: A Weighted Selection Algorithm for Certain Tree-Structured Linear Programs / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Flows in Arborescences / rank | |||
Normal rank | |||
| Property / cites work | |||
| Property / cites work: Totally-Balanced and Greedy Matrices / rank | |||
Normal rank | |||
Revision as of 13:41, 17 June 2024
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
