Approximation algorithms for maximum dispersion

DOI10.1016/S0167-6377(97)00034-5zbMath0888.90144OpenAlexW1990605847MaRDI QIDQ1375119

Shlomi Rubinstein, Arie Tamir, Refael Hassin

Publication date: 1997

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0167-6377(97)00034-5

zbMATH Keywords

facility locationapproximation algorithmsmaximum dispersionbounded performance guarantees

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Discrete location and assignment (90B80)

Related Items

Complexity of finding dense subgraphs, An improved approximation algorithm for the metric maximum clustering problem with given cluster sizes, Iterated tabu search for the maximum diversity problem, Result diversification by multi-objective evolutionary algorithms with theoretical guarantees, An improved analysis for a greedy remote-clique algorithm using factor-revealing LPs, Two dimensional maximum weight matching using Manhattan topology, Finding connected \(k\)-subgraphs with high density, Finding Connected Dense $$k$$-Subgraphs, Integer point sets minimizing average pairwise \(L_{1}\) distance: What is the optimal shape of a town?, Away from each other, Obtaining approximately optimal and diverse solutions via dispersion, An Improved Analysis of Local Search for Max-Sum Diversification, Truthful Mechanisms for Matching and Clustering in an Ordinal World, The densest \(k\)-subgraph problem on clique graphs, A linear time approximation scheme for computing geometric maximum \(k\)-star, Dispersing and grouping points on planar segments, Heuristic solution approaches for the maximum minsum dispersion problem, Weakly Submodular Function Maximization Using Local Submodularity Ratio., Maximum dispersion problem in dense graphs, A constant approximation algorithm for the densest \(k\)-subgraph problem on chordal graphs, Min sum clustering with penalties, Upper bounds and exact algorithms for \(p\)-dispersion problems, Unnamed Item, Measuring diversity. A review and an empirical analysis, Computational geometric aspects of rhythm, melody, and voice-leading, Threshold-based preprocessing for approximating the weighted dense \(k\)-subgraph problem, Max-min dispersion on a line, The equitable dispersion problem, Approximation algorithms for the metric maximum clustering problem with given cluster sizes., Maximization problems of balancing submodular relevance and supermodular diversity, Approximating the maximum quadratic assignment problem, A hybrid metaheuristic method for the maximum diversity problem

Cites Work

• Unnamed Item
• Computational aspects of the maximum diversity problem
• Time bounds for selection
• A class of bounded approximation algorithms for graph partitioning
• Obnoxious Facility Location on Graphs
• An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs
• An Analysis of the Greedy Heuristic for Independence Systems
• Heuristic and Special Case Algorithms for Dispersion Problems
• Facility dispersion and remote subgraphs
• Greedily finding a dense subgraph