Generalized Center Problems with Outliers

Thread View: gwene.acm.algorithms.transactions

1 messages

[T] Back to Threads [V] Tree View [G] Group Articles

1 total messages Started by unknown Mon, 08 Jul 2019 02:00

#435

Author: unknown
Date: Mon, 08 Jul 2019 02:00

1 lines
687 bytes

Deeparnab Chakrabarty, Maryam Negahbani<br /><br />We study the ℱ-center problem with outliers: Given a metric space (X,d), a general down-closed family ℱ of subsets of X, and a parameter m, we need to locate a subset S ∈ ℱ 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 ℱ-center problem with outliers if and only if we can efficiently optimize a poly-bounded linear function over ℱ subject to a partition constraint.
<p><a href="http://dl.acm.org/citation.cfm?id338513">Link</a>

Thread Navigation

This is a paginated view of messages in the thread with full content displayed inline.

Messages are displayed in chronological order, with the original post highlighted in green.

Use pagination controls to navigate through all messages in large threads.

Back to All Threads