Parallel linear programming in fixed dimension almost surely in constant time

DOI10.1145/174652.174661zbMath0807.90080OpenAlexW2032802723MaRDI QIDQ4299014

Noga Alon, Nimrod Megiddo

Publication date: 1 March 1995

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.31.4797

zbMATH Keywords

probabilistic parallel algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Linear programming (90C05) Parallel numerical computation (65Y05) Computational methods for problems pertaining to operations research and mathematical programming (90-08) Distributed algorithms (68W15)

Related Items (2)

A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs ⋮ Prefix graphs and their applications

This page was built for publication: Parallel linear programming in fixed dimension almost surely in constant time