Constant Factor Approximation Algorithm for the Knapsack Median Problem

Abstract

We give a constant factor approximation algorithm for the following generalization of the k-median problem. We are given a set of clients and facilities in a metric space. Each facility has a facility opening cost, and we are also given a budget B. The objective is to open a subset of facilities of total cost at most B, and minimize the total connection cost of the clients. This settles an open problem of Krishnaswamy-Kumar-Nagarajan-Sabharwal-Saha. The natural linear programming relaxation for this problem has unbounded integrality gap. Our algorithm strengthens this relaxation by adding constraints which stipulate which facilities a client can get assigned to. We show that after suitably modifying a fractional solution, one can get rich structural properties which allow us to get the desired approximation ratio.