Compact location problems

DOI10.1016/S0304-3975(96)00304-0zbMath0902.90114MaRDI QIDQ1391322

S. S. Ravi, Madhav V. Marathe, Sven O. Krumke, Hartmut Noltemeier, Venkatesh Radhakrishnan

Publication date: 22 July 1998

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

NP-hard; facility location; near-optimal solutions; minimizing the average distance; minimizing the diameter; minimizing the variance

Mathematics Subject Classification ID

90B80: Discrete location and assignment

Related Items

Communication-aware processor allocation for supercomputers: Finding point sets of small average distance, An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints, Optimal shape of a blob

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A simple heuristic for the p-centre problem
• Clustering to minimize the maximum intercluster distance
• Analytical models for locating undesirable facilities
• Iterated nearest neighbors and finding minimal polytopes
• Improved non-approximability results
• An O(log k) approximation algorithm for the k minimum spanning tree problem in the plane
• Finding k points with minimum diameter and related problems
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• On k-Nearest Neighbor Voronoi Diagrams in the Plane
• Obnoxious Facility Location on Graphs
• An Analysis of Several Heuristics for the Traveling Salesman Problem
• Bicriteria Network Design Problems
• How to Allocate Network Centers
• Heuristic and Special Case Algorithms for Dispersion Problems
• Spanning Trees—Short or Small
• Static and dynamic algorithms for k-point clustering problems