Prune-and-search with limited workspace

DOI10.1016/J.JCSS.2014.08.001zbMATH Open1435.90154OpenAlexW2062651144MaRDI QIDQ473192FDOQ473192

Authors: Minati De, Subhas C. Nandy, 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

Recommendations

• Minimum enclosing circle with few extra variables
• Constant work-space algorithms for facility location problems
• Selection from read-only memory with limited workspace
• Selection from read-only memory with limited workspace
• Fast and optimal parallel multidimensional search in PRAMs with applications to linear programming and related problems

zbMATH Keywords

minimum enclosing circlein-place algorithmslow-dimensional linear programmingprune-and-searchread-only memory algorithmsspace-efficient algorithms

Mathematics Subject Classification ID

Linear programming (90C05) Approximation methods and heuristics in mathematical programming (90C59) Analysis of algorithms (68W40)

Cites Work

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

Cited In (4)

• Knowledge Discovery in Inductive Databases
• Minimum enclosing circle with few extra variables
• Slicing an ear using prune-and-search
• Constant work-space algorithms for facility location problems

This page was built for publication: Prune-and-search with limited workspace

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