Maximum dispersion and geometric maximum weight cliques
type: Item
instance of: scholarly article
title: Maximum dispersion and geometric maximum weight cliques
zbMATH Open document ID: 1095.68082
author: Sándor P. Fekete
author: Henk Meijer
published in: Algorithmica
publication date: 2004-09-22T00:00:00Z
full work available at URL: https://depositonce.tu-berlin.de/handle/11303/15964
review text: We consider a facility location problem, where the objective is to ``disperser'' number of facilities, i.e., select a given number \(k\) of locations from a discrete set of \(n\) candidates, such that the average distance between selected locations is maximized. In particular, we present algorithmic results for the case where vertices are represented by points in \(d\)-dimensional space, and edge weights correspond to rectilinear distances. Problems of this type have been considered before, with the best result being an approximation algorithm with performance ratio 2. For the case where \(k\) is fixed, we establish a linear-time algorithm that finds an optimal solution. For the case where \(k\) is part of the input, we present a polynomial-time approximation scheme.
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 90B80
Mathematics Subject Classification ID: 90C35
zbMATH DE Number: 2101909
zbMATH Keywords: polynomial-time approximation scheme
MaRDI profile type: Publication
OpenAlex ID: W2745300566
DOI: 10.1007/S00453-003-1074-X
Recommended article: Q2753733
Recommended article: Maximum dispersion problem in dense graphs
Recommended article: On the Maximum Weight Clique Problem
Recommended article: Clustered maximum weight clique problem: algorithms and empirical analysis
Recommended article: Finding cliques of maximum weight on a generalization of permutation graphs
Recommended article: Distributed algorithms for maximum cliques
Recommended article: The maximum number of cliques in dense graphs
Recommended article: A new upper bound for the maximum weight clique problem
Recommended article: Extended and discretized formulations for the maximum clique problem
Recommended article: Q4817244
description: scientific article; zbMATH DE number 2101909