Maximum Dispersion and Geometric Maximum Weight Cliques: A Summary of Key Findings

Title: Maximum Dispersion and Geometric Maximum Weight Cliques: A Summary of Key Findings

Researchers: Sándor P. Fekete, Henk Meijer, and others

Purpose: The researchers aimed to find optimal solutions to a facility location problem, where the objective is to disperse facilities evenly among a set of locations. They focused on maximizing the average distance between selected locations, a problem known as the Remote Clique problem.

Methodology: The researchers considered a graph representation of the problem, with vertices representing points in n-dimensional space and edge weights corresponding to rectilinear distances. They proposed algorithms to find optimal solutions for fixed k and k as part of the input, achieving linear-time algorithms and a polynomial-time approximation scheme, respectively.

Results: The researchers presented new algorithms and performance bounds for the problem. For the case where k is fixed, they developed a linear-time algorithm that finds an optimal solution. For the case where k is part of the input, they provided a polynomial-time approximation scheme.

Implications: These results contribute to the understanding and solution of facility location problems, particularly those involving dispersion and maximizing average distance. The research has implications for various fields, including operations research, computer science, and urban planning, where optimizing facility locations is crucial.

Link to Article: https://arxiv.org/abs/0310037v1 Authors: arXiv ID: 0310037v1