Improved algorithms for the data placement problem

Conference Paper

Introduction: We study the data placement problem [1, 3], where the goal is to place certain data objects (with possible replication) in fixed capacity caches in a network to optimize latency of access. The locations of the caches are given and each cache has capacities both on the number of objects it can store and the number of users it can serve. Each user has a demand for a specific object. The end objective is to optimize the average user latency of accessing the objects. We present a constant approximation, while blowing up the cache capacities by a constant factor. This improves the previous results, which either ignore the bound on the number of users [1], or which need to blow up the capacities by a logarithmic factor [3]. Our solution technique involves writing an integer program for this problem and rounding its linear relaxation. We note that our result is the best possible that can be obtained by LP rounding. The problem is MAX-SNP hard as shown in [1], and the linear program has unbounded integrality gap unless we relax the capacity constraints [5]. Our basic technique is to separate the rounding into two stages: Opening Objects: In this stage, we consider each object separately, and open copies in the network. We ignore the interaction of this object with other objects due to the cache capacity constraints. We use the capacitated facility location rounding from [5]. Packing Objects: In this stage, we pack the objects into the cache so that cache capacity constraints are satisfied. We use the GAP rounding from [4].

Duke Authors

Cited Authors

  • Guha, S; Munagala, K

Published Date

  • January 1, 2002

Published In

  • Proceedings of the Annual Acm Siam Symposium on Discrete Algorithms

Volume / Issue

  • 06-08-January-2002 /

Start / End Page

  • 106 - 107

International Standard Book Number 10 (ISBN-10)

  • 089871513X

Citation Source

  • Scopus