On some variants of Euclidean k-supplier

DOI10.1016/J.ORL.2022.01.003MaRDI QIDQ2670484zbMATH OpenOpenAlexWikidataFDO

Authors Euiwoong Lee, Viswanath Nagarajan, Lily Wang

Publication date 11 March 2022

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

Full work available at URL https://arxiv.org/abs/2112.01700

zbMATH Keywords

\(k\)-centerapproximation algorithmsclusteringEuclidean spaceshardness of approximationoutliers

Mathematics Subject Classification ID

Operations research, mathematical programming (90-XX)

Recommendations

• The Euclidean k-supplier problem
• The Euclidean \(k\)-supplier problem
• The Euclidean \(k\)-supplier problem in \(I R^2\)
• The Euclidean \(k\)-supplier problem in \(\mathbb R^2\)
• Approximability of the dispersed \(\vec{p}\)-neighbor \(k\)-supplier problem

Cites work

• A Best Possible Heuristic for the k-Center Problem
• A factor 2 approximation algorithm for the generalized Steiner network problem
• A heuristic for the p-center problem in graphs
• A Nearly Linear-Time Approximation Scheme for the Euclidean k-Median Problem
• Algorithms for facility location problems with outliers. (Extended abstract)
• Clustering to minimize the maximum intercluster distance
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Constant approximation for k-median and k-means with outliers via iterative rounding
• Facility Location with Matroid or Knapsack Constraints
• Generalized center problems with outliers
• Geometric algorithms and combinatorial optimization
• scientific article; zbMATH DE number 5764796 (Why is no real title available?)
• Improved approximation algorithms for matroid and knapsack median problems and applications
• On coresets for k-means and k-median clustering
• The complexity of satisfiability problems
• The Euclidean k-supplier problem
• The non-uniform k-center problem

Cited in

(6)

• The Euclidean \(k\)-supplier problem in \(\mathbb R^2\)
• The Euclidean \(k\)-supplier problem in \(I R^2\)
• An approximation algorithm for the parity-constrained k-supplier problem
• Parity-constrained k-supplier problem
• An improved approximation algorithm for the k-supplier problem with parameterized triangle inequality
• An improved two-stage approximation algorithm for the k-supplier problem with parameterized triangle inequality

This page was built for publication: On some variants of Euclidean \(k\)-supplier

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2670484)