On the Complexity of Some Common Geometric Location Problems
From MaRDI portal
Publication:3318110
DOI10.1137/0213014zbMath0534.68032OpenAlexW2133962824MaRDI 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
Related Items (only showing first 100 items - show all)
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 ⋮ Computing the Center of Uncertain Points on Tree Networks ⋮ A PROBABILISTIC ℓ1 METHOD FOR CLUSTERING HIGH-DIMENSIONAL DATA ⋮ The continuous \(p\)-centre problem: an investigation into variable neighbourhood search with memory ⋮ A mixed breadth-depth first strategy for the branch and bound tree of Euclidean \(k\)-center problems ⋮ On the complexity of some geometric problems in unbounded dimension ⋮ Fuzzy facility location-allocation problem under the Hurwicz criterion ⋮ The Discrete and Mixed Minimax 2-Center Problem ⋮ Computing the Rectilinear Center of Uncertain Points in the Plane ⋮ Linear Time Approximation Schemes for Geometric Maximum Coverage ⋮ Topological stability of kinetic \(k\)-centers ⋮ On alternativep-center problems ⋮ COMPUTING k CENTERS OVER STREAMING DATA FOR SMALL k ⋮ A voltage drop limited decentralized electric power distribution network ⋮ Discrete facility location in machine learning ⋮ \(k\)-median: exact recovery in the extended stochastic ball model ⋮ A faster algorithm for the constrained minimum covering circle problem to expedite solving p‐center problems in an irregularly shaped area with holes ⋮ A Variational Inequality-Based Location-Allocation Algorithm for Locating Multiple Interactive Facilities ⋮ Min-Max-Min Optimization with Smooth and Strongly Convex Objectives ⋮ Linearization of Euclidean norm dependent inequalities applied to multibeam satellites design ⋮ Finding geometric facilities with location privacy ⋮ A trajectory based heuristic for the planar \(p\)-median problem ⋮ Geometric p-Center Problems with Centers Constrained to Two Lines ⋮ The Mixed Center Location Problem ⋮ Approximating the discrete center line segment in linear time ⋮ Polynomial approximate discretization of geometric centers in high-dimensional Euclidean space ⋮ A planar facility location-allocation problem with fixed and/or variable cost structures for rural electrification ⋮ The board packing problem ⋮ The two-center problem of uncertain points on a real line ⋮ Unnamed Item ⋮ The Coverage Problem by Aligned Disks ⋮ The \(p\)-center problem under locational uncertainty of demand points ⋮ Online hitting of unit balls and hypercubes in \(\mathbb{R}^d\) using points from \(\mathbb{Z}^d\) ⋮ Mathematical Programming Formulations and Algorithms for Discrete k-Median Clustering of Time-Series Data ⋮ The coverage problem by aligned disks ⋮ Approximability of the dispersed \(\vec{p}\)-neighbor \(k\)-supplier problem ⋮ The capacitated facility location-allocation problem under uncertain environment ⋮ The planar hub location problem: a probabilistic clustering approach ⋮ Parameterized \(k\)-clustering: tractability island ⋮ Stabbing Convex Polygons with a Segment or a Polygon ⋮ THE ALIGNED K-CENTER PROBLEM ⋮ Unnamed Item ⋮ Ant colony optimization for finding medians of weighted graphs ⋮ Parallel collision detection between moving robots for practical motion planning ⋮ FREE-FORM SURFACE PARTITION IN 3-D ⋮ Hierarchically specified unit disk graphs ⋮ A new local search for continuous location problems ⋮ A solution algorithm for non-convex mixed integer optimization problems with only few continuous variables ⋮ Solving a bi-objective transportation location routing problem by metaheuristic algorithms ⋮ A simple linear algorithm for computing rectilinear 3-centers ⋮ ALMOST OPTIMAL SOLUTIONS TO k-CLUSTERING PROBLEMS ⋮ Fair redistricting is hard ⋮ The Planar k-Means Problem is NP-Hard ⋮ 3-PIERCING OF d-DIMENSIONAL BOXES AND HOMOTHETIC TRIANGLES ⋮ Fast heuristics for large scale covering-location problems ⋮ Deployment optimization of multi-hop wireless networks based on substitution graph ⋮ Clustering with Internal Connectedness ⋮ Online unit covering in Euclidean space ⋮ On the Number and Arrangement of Sensors for the Multiple Covering of Bounded Plane Domains ⋮ Speeding up Dynamic Programming in the Line-Constrained k-median ⋮ Improved starting solutions for the planar p-median problem ⋮ An ADMM-based location-allocation algorithm for nonconvex constrained multi-source Weber problem under gauge ⋮ Computing the Line-Constrained k-center in the Plane for Small k ⋮ Covering a set of line segments with a few squares ⋮ Covering a set of line segments with a few squares ⋮ Using injection points in reformulation local search for solving continuous location problems ⋮ A heuristic algorithm for constrained multi-source location problem with closest distance under gauge: the variational inequality approach ⋮ ON PLANAR MEDIANOID COMPETITIVE LOCATION PROBLEMS WITH MANHATTAN DISTANCE ⋮ Generating good starting solutions for the p-median problem in the plane ⋮ On interval and circular-arc covering problems ⋮ The incorporation of fixed cost and multilevel capacities into the discrete and continuous single source capacitated facility location problem ⋮ An O(n log n)-Time Algorithm for the k-Center Problem in Trees ⋮ Multi-facility green Weber problem ⋮ Heuristics for Location Models ⋮ A linear time algorithm for approximate 2-means clustering ⋮ An $O(n\log n)$-Time Algorithm for the $k$-Center Problem in Trees ⋮ Competitive location in cognitive radio networks ⋮ A fast algorithm for locating supplying center on a lattice ⋮ Bounded fan-out \(m\)-center problem ⋮ Online unit clustering and unit covering in higher dimensions ⋮ The mixed center location problem ⋮ A theory for memory-based learning ⋮ A randomized algorithm for online unit clustering ⋮ On the complexity of some basic problems in computational convexity. I. Containment problems ⋮ Scaling and compressing melodies using geometric similarity measures ⋮ Stop location design in public transportation networks: covering and accessibility objectives ⋮ On the choice of aggregation points for continuous \(p\)-median problems: A case for the gravity centre ⋮ Information-theoretic feature selection with discrete \(k\)-median clustering ⋮ Preclustering algorithms for imprecise points ⋮ A heuristic for the p-center problem in graphs ⋮ A two-level off-grid electric distribution problem on the continuous space ⋮ Advanced greedy randomized adaptive search procedure for the obnoxious \(p\)-median problem ⋮ Geometric optimization and the polynomial hierarchy ⋮ Geometric optimization and \(D^ P\)-completeness ⋮ Location equilibria for a continuous competitive facility location problem under delivered pricing ⋮ A distance-limited continuous location-allocation problem for spatial planning of decentralized systems ⋮ When centers can fail: a close second opportunity ⋮ A genetic algorithm for the uncapacitated single allocation planar hub location problem
This page was built for publication: On the Complexity of Some Common Geometric Location Problems
