On the Complexity of Some Common Geometric Location Problems
From MaRDI portal
Publication:3318110
DOI10.1137/0213014zbMath0534.68032MaRDI QIDQ3318110
Kenneth J. Supowit, Nimrod Megiddo
Publication date: 1984
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0213014
68Q25: Analysis of algorithms and problem complexity
Related Items
3-PIERCING OF d-DIMENSIONAL BOXES AND HOMOTHETIC TRIANGLES, Fast heuristics for large scale covering-location problems, Dynamic and static algorithms for optimal placement of resources in a tree, A faster algorithm for the two-center decision problem, On the asymptotics of trimmed best \(k\)-nets, A simple heuristic for the p-centre problem, A continuous location-allocation problem with zone-dependent fixed cost, Demand point aggregation for planar covering location models, The directional \(p\)-median problem: definition, complexity, and algorithms, An optimal approximation algorithm for the rectilinear m-center problem, New relaxation-based algorithms for the optimal solution of the continuous and discrete \(p\)-center problems, The multi-facility location-allocation problem with polyhedral barriers, Location problems, A heuristic for the p-center problem in graphs, Geometric optimization and the polynomial hierarchy, Geometric optimization and \(D^ P\)-completeness, Polynomial algorithms for restricted Euclidean p-centre problems, A study on two geometric location problems, Complexity of the repeaters allocating problem, On the covering multiplicity of lattices, Minimizing the sum of diameters efficiently, The slab dividing approach to solve the Euclidean \(P\)-center problem, Linear time algorithms for the weighted tailored 2-partition problem and the weighted 2-center problem under \(l_ \infty\)-distance, Hierarchically specified unit disk graphs, Heuristic solution of the multisource Weber problem as a \(p\)-median problem, K-center and K-median problems in graded distances, A new assignment rule to improve seed points algorithms for the continuous \(k\)-center problem, On the complexity of two circle connecting problems, A theory for memory-based learning, On the complexity of some basic problems in computational convexity. I. Containment problems, On the choice of aggregation points for continuous \(p\)-median problems: A case for the gravity centre, 2-medians in trees with pos/neg weights, A polynomial-time optimization algorithm for a rectilinear partitioning problem with applications in VLSI design automation., The searching over separators strategy to solve some NP-hard problems in subexponential time, Minimal link visibility paths inside a simple polygon, A heuristic algorithm for minimax sensor location in the plane, Fuzzy facility location-allocation problem under the Hurwicz criterion, A simple linear algorithm for computing rectilinear 3-centers, A linear time algorithm for approximate 2-means clustering, On the complexity of some geometric problems in unbounded dimension, Parallel collision detection between moving robots for practical motion planning, Stabbing Convex Polygons with a Segment or a Polygon, The Planar k-Means Problem is NP-Hard, On alternativep-center problems, A fast algorithm for locating supplying center on a lattice
