𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A Constant-Factor Approximation Algorithm for the k-Median Problem

✍ Scribed by Moses Charikar; Sudipto Guha; Éva Tardos; David B. Shmoys

Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
165 KB
Volume
65
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

✦ Synopsis

We present the first constant-factor approximation algorithm for the metric k-median problem. The k-median problem is one of the most wellstudied clustering problems, i.e., those problems in which the aim is to partition a given set of points into clusters so that the points within a cluster are relatively close with respect to some measure. For the metric k-median problem, we are given n points in a metric space. We select k of these to be cluster centers and then assign each point to its closest selected center. If point j is assigned to a center i, the cost incurred is proportional to the distance between i and j. The goal is to select the k centers that minimize the sum of the assignment costs. We give a 6 2 3 -approximation algorithm for this problem. This improves upon the best previously known result of O(log k log log k), which was obtained by refining and derandomizing a randomized O(log n log log n)-approximation algorithm of Bartal.

📜 SIMILAR VOLUMES

A Constant-Factor Approximation Algorith
A Constant-Factor Approximation Algorithm for thek-MST Problem
✍ Avrim Blum; R Ravi; Santosh Vempala 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 186 KB

Given an undirected graph with nonnegative edge costs and an integer k, the k-MST problem is that of finding a tree of minimum cost on k nodes. This problem is known to be NP-hard. We present a simple approximation algorithm that finds a solution whose cost is less than 17 times the cost of the opti

Constant Ratio Approximation Algorithms
Constant Ratio Approximation Algorithms for the Rectangle Stabbing Problem and the Rectilinear Partitioning Problem
✍ Daya Ram Gaur; Toshihide Ibaraki; Ramesh Krishnamurti 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 114 KB

We provide constant ratio approximation algorithms for two NP-hard problems, the rectangle stabbing problem and the rectilinear partitioning problem. In the rectangle stabbing problem, we are given a set of rectangles in two-dimensional space, with the objective of stabbing all rectangles with the m

A branch-and-price algorithm for the cap
A branch-and-price algorithm for the capacitated p-median problem
✍ Alberto Ceselli; Giovanni Righini 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 178 KB 👁 1 views

## Abstract The capacitated __p__‐median problem is the variation of the well‐known __p__‐median problem in which a demand is associated to each user, a capacity is associated to each candidate median, and the total demand of the users associated to the same median must not exceed its capacity. We

A Polylogarithmic Approximation Algorith
A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
✍ Naveen Garg; Goran Konjevod; R. Ravi 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 130 KB

The group Steiner tree problem is a generalization of the Steiner tree problem where we are given several subsets (groups) of vertices in a weighted graph, and the goal is to find a minimum-weight connected subgraph containing at least one vertex from each group.The problem was introduced by Reich a

An improved algorithm for the minmax reg
An improved algorithm for the minmax regret median problem on a tree
✍ Igor Averbakh; Oded Berman 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 116 KB 👁 1 views

## Abstract We consider the 1‐median problem with uncertain weights for nodes. Specifically, for each node, only an interval estimate of its weight is known. It is required to find a “minmax regret” location, that is, to minimize the worst‐case loss in the objective function that may occur because