English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In the Geometric Median problem with outliers, we are given a finite set ofpoints in d-dimensional real space and an integer m, the goal is to locate anew point in space (center) and choose m of the input points to minimize thesum of the Euclidean distances from the center to the chosen points. Thisproblem can be solved "almost exactly" in polynomial time if d is fixed andadmits an approximation scheme PTAS in high dimensions. However, the complexityof the problem was an open question. We prove that, if the dimension of spaceis not fixed, Geometric Median with outliers is strongly NP-hard, does notadmit approximation schemes FPTAS unless P=NP, and is W[1]-hard with respect tothe parameter m. The proof is done by a reduction from the Independent Setproblem. Based on a similar reduction, we also get the NP-hardness of closelyrelated geometric 2-clustering problems in which it is required to partition agiven set of points into two balanced clusters minimizing the cost of medianclustering. Finally, we study Geometric Median with outliers in $\ell_\infty$space and prove the same complexity results as for the Euclidean problem.

On the Complexity of the Geometric Median Problem with Outliers