License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.403
URN: urn:nbn:de:0030-drops-47125
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2014/4712/
Go to the corresponding LIPIcs Volume Portal

Swamy, Chaitanya

Improved Approximation Algorithms for Matroid and Knapsack Median Problems and Applications

pdf-format:
29.pdf (0.6 MB)

Abstract

We consider the matroid median problem, wherein we are given a set of facilities with opening costs and a matroid on the facility-set, and clients with demands and connection costs, and we seek to open an independent set of facilities and assign clients to open facilities so as to minimize the sum of the facility-opening and client-connection costs. We give a simple 8-approximation algorithm for this problem based on LP-rounding, which improves upon the 16-approximation by Krishnaswamy et al. We illustrate the power and versatility of our techniques by deriving: (a) an 8-approximation for the two-matroid median problem, a generalization of matroid median that we introduce involving two matroids; and (b) a 24-approximation algorithm for matroid median with penalties, which is a vast improvement over the 360-approximation obtained by Krishnaswamy et al. We show that a variety of seemingly disparate facility-location problems considered in the literature -- data placement problem, mobile facility location, k-median forest, metric uniform minimum-latency UFL -- in fact reduce to the matroid median or two-matroid median problems, and thus obtain improved approximation guarantees for all these problems. Our techniques also yield an improvement for the knapsack median problem.

BibTeX - Entry

@InProceedings{swamy:LIPIcs:2014:4712,
  author =	{Chaitanya Swamy},
  title =	{{Improved Approximation Algorithms for Matroid and Knapsack Median Problems and Applications}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{403--418},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Klaus Jansen and Jos{\'e} D. P. Rolim and Nikhil R. Devanur and Cristopher Moore},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2014/4712},
  URN =		{urn:nbn:de:0030-drops-47125},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.403},
  annote =	{Keywords: Approximation algorithms, LP rounding, facility location, matroid and submodular polyhedra, knapsack constraints}
}

Keywords: Approximation algorithms, LP rounding, facility location, matroid and submodular polyhedra, knapsack constraints
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)
Issue Date: 2014
Date of publication: 04.09.2014

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI