Prune-and-search with limited workspace

DOI10.1016/j.jcss.2014.08.001zbMath1435.90154MaRDI QIDQ473192

Subhas C. Nandy, Minati De, Sasanka Roy

Publication date: 24 November 2014

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2014.08.001

zbMATH Keywords

minimum enclosing circle; in-place algorithms; low-dimensional linear programming; prune-and-search; read-only memory algorithms; space-efficient algorithms

Mathematics Subject Classification ID

68W40: Analysis of algorithms

90C05: Linear programming

90C59: Approximation methods and heuristics in mathematical programming

Related Items

Constant work-space algorithms for facility location problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Space-efficient planar convex hull algorithms
• Selection from read-only memory and sorting with minimum data movement
• A new polynomial-time algorithm for linear programming
• In-place algorithms for computing (Layers of) maxima
• Multi-pass geometric algorithms
• Space-efficient geometric divide-and-conquer algorithms
• Small-dimensional linear programming and convex hulls made easy
• On the ball spanned by balls
• Space-Time Trade-offs for Stack-Based Algorithms
• The Weighted Euclidean 1-Center Problem
• Linear-Time Algorithms for Linear Programming in $R^3 $ and Related Problems
• The Ultimate Planar Convex Hull Algorithm?
• An O(nlogn) randomizing algorithm for the weighted euclidean 1-center problem
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• Linear Programming in Linear Time When the Dimension Is Fixed
• Towards in-place geometric algorithms and data structures