Geometric complexity of some location problems
From MaRDI portal
Given a set of n demand points with weight \(w_ i\), \(i=1,2,...,n\), in the plane, we consider several geometric facility location problems. Specifically we study the complexity of the Euclidean 1-line center problem, discrete 1-point center problem and a competitive location problem. The Euclidean 1-line center problem is to locate a line which minimizes the maximum weighted distance from the line (or the center) to the demand points. The discrete 1-point center problem is to locate one of the demand points so as to minimize the maximum unweighted distance from the point to other demand points. The competitive location problem studied is to locate a new facility point to compete against an existing facility so that a certain objective function is optimized. An \(\Omega\) (n log n) lower bound is proved for these problems under appropriate models of computation. Efficient algorithms for these problems that achieve the lower bound and other related problems are also given.
Recommendations
- Publication:4728245
- On the Complexity of Some Common Geometric Location Problems
- Technical Note—On the Complexity of Some Classes of Location Problems
- A study on two geometric location problems
- The geometry of optimal partitions in location problems
- Parameterized complexity of geodetic set
- Parameterized Complexity of Geodetic Set
- On the complexity of some geometric problems with fixed parameters
- Geometric methods to solve max-ordering location problems
Cites work
- A Note on Locating a Set of Points in a Planar Subdivision
- An efficient algorithm for determining the convex hull of a finite planar set
- Convex hulls of finite sets of points in two and three dimensions
- scientific article; zbMATH DE number 3511563 (Why is no real title available?)
- Linear facility location. Solving extensions of the basic problem
- Linear-Time Algorithms for Linear Programming in R^3 and Related Problems
- On the complexity of computations under varying sets of primitives
- On the complexity of computing the measure of ∪[a i ,b i ]
- On the complexity of locating linear facilities in the plane
- On the Optimality of Some Set Algorithms
- Optimal Point Location in a Monotone Subdivision
- Optimal Search in Planar Subdivisions
- The complexity of problems on probabilistic, nondeterministic, and alternating decision trees
Cited in
(62)- Facility location problems in the plane based on reverse nearest neighbor queries
- Obtaining lower bounds using artificial components
- A study on two geometric location problems
- Computing the minimum Hausdorff distance between two point sets on a line under translation
- Improved complexity bounds for location problems on the real line
- An efficient parallel sorting algorithm
- Locational optimization problems solved through Voronoi diagrams
- Median hyperplanes in normed spaces -- a survey
- Special issue on Locational analysis
- Location of rectilinear center trajectories
- Solving restricted line location problems via a dual interpretation
- On the geometric behaviour of multidimensional location measures
- A comment on a minmax location problem
- Heuristics for parallel machine scheduling with delivery times
- \(k\) best cuts for circular-arc graphs
- A (\(1+{\varepsilon}\))-approximation algorithm for 2-line-center
- Continuous location of dimensional structures.
- Computing an obnoxious anchored segment.
- Sorting weighted distances with applications to objective function evaluations in single facility location problems.
- A near-linear algorithm for the planar segment-center problem
- On computing the closest boundary point on the convex hull
- On the computational complexities of various geography variants
- Bichromatic 2-center of pairs of points
- Minimum perimeter-sum partitions in the plane
- Orthogonal weightet linear \(L_ 1\) and \(L_ \infty\) approximation and applications
- On the planar piecewise quadratic 1-center problem
- On finding widest empty curved corridors
- Minmax-distance approximation and separation problems: geometrical properties
- Locating an obnoxious plane
- The \(p\)-center problem under locational uncertainty of demand points
- Obnoxious facility location: complete service with minimal harm
- On the 2-center problem under convex polyhedral distance function
- A geometric characterisation of the quadratic min-power centre
- Processing an offline insertion-query sequence with applications
- The \((1 | 1)\)-centroid problem in the plane with distance constraints
- On the Complexity of Some Common Geometric Location Problems
- Line Facility Location in Weighted Regions
- ε-Approximations for Multidimensional Weighted Location Problems
- scientific article; zbMATH DE number 3926931 (Why is no real title available?)
- scientific article; zbMATH DE number 3974683 (Why is no real title available?)
- Minimum-area enclosing triangle with a fixed angle
- Technical Note—On the Complexity of Some Classes of Location Problems
- The class cover problem with boxes
- COMPUTING A DOUBLE-RAY CENTER FOR A PLANAR POINT SET
- scientific article; zbMATH DE number 4003525 (Why is no real title available?)
- One-dimensional \(k\)-center on uncertain data
- Linear approximation of simple objects
- New algorithms for facility location problems on the real line
- SOME LOWER BOUNDS ON GEOMETRIC SEPARABILITY PROBLEMS
- Locating an obnoxious line among planar objects
- Processing an Offline Insertion-Query Sequence with Applications
- Conditional Location Problems on Networks and in the Plane
- LABELING POINTS ON A SINGLE LINE
- Linear approximation of simple objects
- Linear approximation of simple objects
- On fixed-parameter solvability of the minimax path location problem
- Fitting a two-joint orthogonal chain to a point set
- The k-centrum straight-line location problem
- Clustering with few disks to minimize the sum of radii
- Planar expropriation problem with non-rigid rectangular facilities
- The maximin line problem with regional demand
- 2-Covered paths by a set of antennas with minimum power transmission range
This page was built for publication: Geometric complexity of some location problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1099951)
