Generalized center problems with outliers

DOI10.1145/3338513MaRDI QIDQ4972687zbMATH OpenOpenAlexWikidataFDO

Authors Deeparnab Chakrabarty, Maryam Negahbani

Publication date 25 November 2019

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1805.02217, https://drops.dagstuhl.de/opus/volltexte/2018/9034/

zbMATH Keywords

approximation algorithmsclusteringk-center problem

Mathematics Subject Classification ID

Approximation algorithms (68W25) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Abstract: We study the $mathcalF$-center problem with outliers: given a metric space $(X,d)$, a general down-closed family $mathcalF$ of subsets of $X$, and a parameter $m$, we need to locate a subset $SinmathcalF$ of centers such that the maximum distance among the closest $m$ points in $X$ to $S$ is minimized. Our main result is a dichotomy theorem. Colloquially, we prove that there is an efficient $3$-approximation for the $mathcalF$-center problem with outliers if and only if we can efficiently optimize a poly-bounded linear function over $mathcalF$ subject to a partition constraint. One concrete upshot of our result is a polynomial time $3$-approximation for the knapsack center problem with outliers for which no (true) approximation algorithm was known.

Recommendations

• Generalized center problems with outliers
• Approximation schemes for clustering with outliers
• Approximation schemes for clustering with outliers

Cites work

• A Best Possible Heuristic for the k-Center Problem
• A lottery model for center-type problems with outliers
• Achieving anonymity via clustering
• Algorithms for facility location problems with outliers. (Extended abstract)
• Approximating capacitated \(k\)-median with \((1 + \epsilon)k\) open facilities
• Budgeted matching and budgeted matroid intersection via the gasoline puzzle
• Clustering to minimize the maximum intercluster distance
• Easy and hard bottleneck location problems
• Geometric algorithms and combinatorial optimization.
• scientific article; zbMATH DE number 1445293 (Why is no real title available?)
• LP-based algorithms for capacitated facility location
• Matching is as easy as matrix inversion
• Multi-budgeted matchings and matroid intersection via dependent rounding
• New approaches to multi-objective optimization
• On uniform capacitated \(k\)-median beyond the natural LP relaxation
• Optimum Distribution of Switching Centers in a Communication Network and Some Related Graph Theoretic Problems
• Optimum Locations of Switching Centers and the Absolute Centers and Medians of a Graph
• Random pseudo-polynomial algorithms for exact matroid problems
• The complexity of restricted spanning tree problems
• The heterogeneous capacitated \(k\)-center problem
• The non-uniform k-center problem

Cited in

(16)

• A technique for obtaining true approximations for \(k\)-center with covering constraints
• Approximation algorithms for clustering with dynamic points
• On some variants of Euclidean \(k\)-supplier
• A Lottery Model for Center-Type Problems With Outliers
• A lottery model for center-type problems with outliers
• Generalized center problems with outliers
• Deterministic \(o(1)\)-approximation algorithms to 1-center clustering with outliers
• A technique for obtaining true approximations for k-center with covering constraints
• Robust \(k\)-center with two types of radii
• Robust \(k\)-center with two types of radii
• Connected k-center and k-diameter clustering
• A constant-factor approximation for pairwise fair k-center clustering
• Fault-tolerant k-supplier with outliers
• Approximation algorithms for continuous clustering and facility location problems
• Techniques for generalized colorful k-center problems
• Revisiting priority k-center: fairness and outliers

This page was built for publication: Generalized center problems with outliers

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