Publication

Approximating k-median via pseudo-approximation

2013
Conference Papers

Abstract

We present a novel approximation algorithm for k-median that achieves an approximation guarantee of 1 + √3 + ε, improving upon the decade-old ratio of 3+ε. Our approach is based on two components, each of which, we believe, is of independent interest. First, we show that in order to give an α-approximation algorithm for k-median, it is sufficient to give a pseudo- approximation algorithm that finds an α-approximate solu- tion by opening k+O(1) facilities. This is a rather surprising result as there exist instances for which opening k + 1 facil- ities may lead to a significant smaller cost than if only k facilities were opened. Second, we give such a pseudo-approximation algorithm with α = 1+ √3+ε. Prior to our work, it was not even known whether opening k + o(k) facilities would help improve the approximation ratio. Copyright 2013 ACM.

Official source

https://infoscience.epfl.ch/entities/publication/9fbe7b6a-0594-4d04-9b57-879bb7f19190

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

2013
Conference Papers

Abstract

Official source

https://infoscience.epfl.ch/entities/publication/9fbe7b6a-0594-4d04-9b57-879bb7f19190

About this result

Related concepts (25)

Approximation algorithm

In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems (in particular NP-hard problems) with provable guarantees on the distance of the returned solution to the optimal one. Approximation algorithms naturally arise in the field of theoretical computer science as a consequence of the widely believed P ≠ NP conjecture. Under this conjecture, a wide class of optimization problems cannot be solved exactly in polynomial time.

Median

In statistics and probability theory, the median is the value separating the higher half from the lower half of a data sample, a population, or a probability distribution. For a data set, it may be thought of as "the middle" value. The basic feature of the median in describing data compared to the mean (often simply described as the "average") is that it is not skewed by a small proportion of extremely large or small values, and therefore provides a better representation of the center.

Geometric median

In geometry, the geometric median of a discrete set of sample points in a Euclidean space is the point minimizing the sum of distances to the sample points. This generalizes the median, which has the property of minimizing the sum of distances for one-dimensional data, and provides a central tendency in higher dimensions. It is also known as the 1-median, spatial median, Euclidean minisum point, or Torricelli point. The geometric median is an important estimator of location in statistics, where it is also known as the L1 estimator (after the L1 norm).

Related publications (2)

Approximating k-median via pseudo-approximation

Chat with Graph Search

MPTCP is not Pareto-Optimal: Performance Issues and a Possible Solution

A Value Ordering Heuristic for Local Search in Distributed Resource Allocation