An efficient algorithm for solving a special class of LP's
type: Item
instance of: scholarly article
title: An efficient algorithm for solving a special class of LP's
zbMATH Open document ID: 0589.65053
DOI: 10.1007/BF02252513
author: B. George
published in: Computing
publication date: 1986-01-01T00:00:00Z
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.
Mathematics Subject Classification ID: 65K05
Mathematics Subject Classification ID: 90C05
zbMATH DE Number: 3947543
zbMATH Keywords: 0-1 matrix
zbMATH Keywords: Manhattan Skyline matrix
zbMATH Keywords: \(O(nm+n\,\log \,n)\) algorithm
MaRDI profile type: Publication
cites work: A Weighted Selection Algorithm for Certain Tree-Structured Linear Programs
cites work: Flows in Arborescences
cites work: Totally-Balanced and Greedy Matrices
full work available at URL: https://doi.org/10.1007/bf02252513
OpenAlex ID: W403475137
description: scientific article; zbMATH DE number 3947543