𝔖 Bobbio Scriptorium
✦   LIBER   ✦

An approximation algorithm for the edge-dilation k-center problem

✍ Scribed by Jochen Könemann; Yanjun Li; Ojas Parekh; Amitabh Sinha

Publisher
Elsevier Science
Year
2004
Tongue
English
Weight
227 KB
Volume
32
Category
Article
ISSN
0167-6377

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

AnO(log*n) Approximation Algorithm for t
AnO(log*n) Approximation Algorithm for the Asymmetricp-Center Problem
✍ Rina Panigrahy; Sundar Vishwanathan 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 130 KB

The input to the asymmetric p-center problem consists of an integer p and an n = n distance matrix D defined on a vertex set V of size n, where d gives the i j distance from i to j. The distances are assumed to obey the triangle inequality. For a subset S : V the radius of S is the minimum distance

A Constant-Factor Approximation Algorith
A Constant-Factor Approximation Algorithm for the k-Median Problem
✍ Moses Charikar; Sudipto Guha; Éva Tardos; David B. Shmoys 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 165 KB

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 rel

An approximation algorithm for the -leve
An approximation algorithm for the -level stochastic facility location problem
✍ Zhen Wang; Donglei Du; Adriana F. Gabor; Dachuan Xu 📂 Article 📅 2010 🏛 Elsevier Science 🌐 English ⚖ 268 KB

We consider the k-level stochastic facility location problem. For this, we present an LP rounding algorithm that is 3-approximate. This result is achieved by a novel integer linear programming formulation that exploits the stochastic structure.