A linear time approximation scheme for computing geometric maximum \(k\)-star

DOI10.1007/s10898-012-9867-6zbMath1268.90121OpenAlexW2119607953MaRDI QIDQ1942028

Jia Wang, Shiyan Hu

Publication date: 25 March 2013

Published in: Journal of Global Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10898-012-9867-6

zbMATH Keywords

approximationfacility dispersiongeometric maximum \(k\)-starlinear time approximation scheme

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Discrete location and assignment (90B80)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation algorithms for a \(k\)-line center
• The discrete p-dispersion problem
• Approximation algorithms for maximum dispersion
• Time bounds for selection
• A linear-time approximation scheme for maximum weight triangulation of convex polygons
• Maximum dispersion and geometric maximum weight cliques
• Facility dispersion problems under capacity and cost constraints
• Faster core-set constructions and data-stream algorithms in fixed dimensions
• The maximal dispersion problem and the ``first point outside the neighbourhood heuristic
• Approximation Algorithms for Dispersion Problems
• Approximating extent measures of points
• An Analysis of Network Location Problems with Distance Constraints
• Comparison Of Four Models For dispersing Facilities
• A Linear-Time Approximation Scheme for TSP in Undirected Planar Graphs with Edge-Weights
• Obnoxious Facility Location on Graphs
• Heuristic and Special Case Algorithms for Dispersion Problems
• The dense \(k\)-subgraph problem
• Approximation of geometric dispersion problems

This page was built for publication: A linear time approximation scheme for computing geometric maximum \(k\)-star