On the complexity of locating linear facilities in the plane
From MaRDI portal
Publication:1837617
DOI10.1016/0167-6377(82)90039-6zbMath0507.90025OpenAlexW2027402472WikidataQ29397008 ScholiaQ29397008MaRDI QIDQ1837617
Publication date: 1982
Published in: Operations Research Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0167-6377(82)90039-6
computational complexityNP-completenessNP-hardness in the strong senselinear facility location in the planep-line centrep-line median
Related Items
Approximating finite weighted point sets by hyperplanes, The two-line center problem from a polar view: a new algorithm and data structure, A two-phase heuristic for the bottleneck \(k\)-hyperplane clustering problem, Geometric complexity of some location problems, Unique Covering Problems with Geometric Sets, Online exploration outside a convex obstacle, On the complexity of polyhedral separability, On fair covering and hitting problems, Committee polyhedral separability: complexity and polynomial approximation, The role of optimization in some recent advances in data-driven decision-making, On fixed-parameter solvability of the minimax path location problem, A parameterized algorithm for the hyperplane-cover problem, A (\(1+{\varepsilon}\))-approximation algorithm for 2-line-center, Bottleneck Convex Subsets: Finding k Large Convex Sets in a Point Set, The parameterized complexity of stabbing rectangles, Minmax-distance approximation and separation problems: geometrical properties, On the approximability of covering points by lines and related problems, Continuous location of dimensional structures., Bottleneck convex subsets: finding \(k\) large convex sets in a point set, Computational complexity of combinatorial optimization problems induced by collective procedures in machine learning, Computational complexity of recognition learning procedures in the class of piecewise-linear committee decision rules, Stabbing Convex Polygons with a Segment or a Polygon, Approximation algorithms for hitting objects with straight lines, The computational complexity and approximability of a series of geometric covering problems, FPT-ALGORITHMS FOR MINIMUM-BENDS TOURS, Cutting polygons into small pieces with chords: Laser-based localization, Turning Big Data Into Tiny Data: Constant-Size Coresets for $k$-Means, PCA, and Projective Clustering, Geometric hitting set for segments of few orientations, Digital Straightness, Circularity, and Their Applications to Image Analysis, Traversing a set of points with a minimum number of turns, APPROXIMATING 3D POINTS WITH CYLINDRICAL SEGMENTS, On guarding the vertices of rectilinear domains, Triangulating with high connectivity., Hitting and Piercing Rectangles Induced by a Point Set, On a minimum linear classification problem, Rainbow polygons for colored point sets in the plane, Combinatorial optimization problems related to the committee polyhedral separability of finite sets, On Covering Points with Minimum Turns, Minimum-link watchman tours, Soft computing methods for multiobjective location of garbage accumulation points in smart cities, Mathematical Programming Formulations for the Bottleneck Hyperplane Clustering Problem, Locational optimization problems solved through Voronoi diagrams, Median hyperplanes in normed spaces -- a survey, Special issue on Locational analysis, Location of rectilinear center trajectories, Exact multi-covering problems with geometric sets, CONTINUOUS SURVEILLANCE OF POINTS BY ROTATING FLOODLIGHTS, On Optimal Polyline Simplification Using the Hausdorff and Fréchet Distance, Shortcut sets for the locus of plane Euclidean networks, Approximability of guarding weak visibility polygons
Cites Work
