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
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, Heuristics for a continuous multi-facility location problem with demand regions, New heuristic algorithms for solving the planar \(p\)-median problem, A survey of healthcare facility location, A new heuristic for solving the \(p\)-median problem in the plane, Computing \(k\)-centers of uncertain points on a real line, An adaptive perturbation-based heuristic: an application to the continuous \(p\)-centre problem, The directional \(p\)-median problem: definition, complexity, and algorithms, Polynomial algorithms for restricted Euclidean p-centre problems, Capacitated location allocation problem with stochastic location and fuzzy demand: a hybrid algorithm, A study on two geometric location problems, Biologically inspired parent selection in genetic algorithms, General network design: a unified view of combined location and network design problems, An agent-based framework for modeling and solving location problems, Solving the planar \(p\)-Median problem by variable neighborhood and concentric searches, Covering points by disjoint boxes with outliers, Incorporating neighborhood reduction for the solution of the planar \(p\)-median problem, Quantifying spatial misallocation in centrally provided public goods, Prepositioning supplies in preparation for disasters, A guided reactive GRASP for the capacitated multi-source Weber problem, Recovery guarantees for exemplar-based clustering, The continuous single source location problem with capacity and zone-dependent fixed cost: models and solution approaches, Covering moving points with anchored disks, An improved data stream algorithm for clustering, Accelerating the convergence in the single-source and multi-source Weber problems, Research on gateway deployment of WMN based on maximum coupling subgraph and PSO algorithm, The connected disk covering problem, Solving a continuous local access network design problem with a stabilized central column generation approach, An optimal approximation algorithm for the rectilinear m-center problem, The planar \(k\)-means problem is NP-hard, On the complexity of the \((r|p)\)-centroid problem in the plane, \(k\)-balanced center location problem: a new multi-objective facility location problem, Optimization of two-stage location-routing-inventory problem with time-windows in food distribution network, Complexity of the repeaters allocating problem, Dynamic and static algorithms for optimal placement of resources in a tree, One-dimensional \(k\)-center on uncertain data, Graph summarization with quality guarantees, On the covering multiplicity of lattices, New local searches for solving the multi-source Weber problem, Near-linear time approximation schemes for geometric maximum coverage, Solving a two-stage stochastic capacitated location-allocation problem with an improved PSO in emergency logistics, A faster algorithm for the two-center decision problem, Speeding up the optimal method of Drezner for the \(p\)-centre problem in the plane, Minimizing the sum of diameters efficiently, 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, Computing the center of uncertain points on tree networks, Boolean autoencoders and hypercube clustering complexity, Local search algorithms for the red-blue median problem, 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, Faster balanced clusterings in high dimension, Modelling gateway placement in wireless networks: geometric \(k\)-centres of unit disc graphs, On the asymptotics of trimmed best \(k\)-nets, Planar multifacility location problems with tree structure and finite dominating sets, A generalized Weiszfeld method for the multi-facility location problem, A multi-dimensional shooting algorithm for the two-facility location-allocation problem with dense demand, The continuous single-source capacitated multi-facility Weber problem with setup costs: formulation and solution methods, Speeding up dynamic programming in the line-constrained \(k\)-median, A note on computing the center of uncertain data on the real line, The big cube small cube solution method for multidimensional facility location problems, A continuous analysis framework for the solution of location-allocation problems with dense demand, Allocation search methods for a generalized class of location-allocation problems, Near-optimal large-scale k-medoids clustering, 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, Aggregation error for location models: Survey and analysis, A simple heuristic for the p-centre problem, Solving probabilistic multi-facility Weber problem by vector quantization, Maximizing the ratio of cluster split to cluster diameter without and with cardinality constraints, An elliptical cover problem in drone delivery network design and its solution algorithms, A new assignment rule to improve seed points algorithms for the continuous \(k\)-center problem, 2-medians in trees with pos/neg weights, Facility reallocation on the line, A polynomial-time optimization algorithm for a rectilinear partitioning problem with applications in VLSI design automation., Location problems, On the planar two-center problem and circular hulls, On the complexity of two circle connecting problems, A continuous location-allocation problem with zone-dependent fixed cost, Demand point aggregation for planar covering location models, 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
