Compact location problems

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

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

Publication date: 22 July 1998

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

Full work available at URL: https://doi.org/10.1016/s0304-3975(96)00304-0

zbMATH Keywords

NP-hardfacility locationnear-optimal solutionsminimizing the average distanceminimizing the diameterminimizing the variance

Mathematics Subject Classification ID

Discrete location and assignment (90B80)

Related Items (5)

Integer point sets minimizing average pairwise \(L_{1}\) distance: What is the optimal shape of a town? ⋮ Optimal shape of a blob ⋮ Communication-aware processor allocation for supercomputers: Finding point sets of small average distance ⋮ An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints ⋮ A competitive strategy for distance-aware online shape allocation

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

This page was built for publication: Compact location problems