An efficient algorithm for solving a special class of LP's

DOI10.1007/BF02252513MaRDI QIDQ1074311zbMATH OpenOpenAlexFDO

Authors B. George

Publication date 1986

Published in Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf02252513

zbMATH Keywords

0-1 matrix\(O(nm+n\,\log \,n)\) algorithmManhattan Skyline matrix

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Linear programming (90C05)

Review text

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.

Recommendations

• An O(n log n)-algorithm for solving a special class of linear programs
• An algorithm for solving a structured class of linear programming problems
• scientific article; zbMATH DE number 916038
• A Strongly Polynomial Algorithm for a Special Class of Linear Programs
• scientific article; zbMATH DE number 724217

Cites work

• A Weighted Selection Algorithm for Certain Tree-Structured Linear Programs
• Flows in Arborescences
• Totally-Balanced and Greedy Matrices

Cited in

(6)

• On the efficient use of the architecture of a small computer for LP algorithms
• An algorithm for solving a structured class of linear programming problems
• scientific article; zbMATH DE number 5000797 (Why is no real title available?)
• Efficient algorithms for three variants of the LPF table
• scientific article; zbMATH DE number 5022963 (Why is no real title available?)
• An O(n log n)-algorithm for solving a special class of linear programs

This page was built for publication: An efficient algorithm for solving a special class of LP's

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1074311)