Improved algorithms for the data placement problem

ABSTRACT

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].

REFERENCES

• 1: Ivan D. Baev , Rajmohan Rajaraman, Approximation algorithms for data placement in arbitrary networks, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.661-670, January 07-09, 2001, Washington, D.C., United States
• 2: Jyh-Han Lin , Jeffrey Scott Vitter, e-approximations with minimum packing constraint violation (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.771-782, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129787]
• 3: Adam Meyerson , Kamesh Munagala , Serge Plotkin, Web caching using access statistics, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.354-363, January 07-09, 2001, Washington, D.C., United States
• 4: David B. Shmoys , Éva Tardos, Scheduling unrelated machines with costs, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.448-454, January 25-27, 1993, Austin, Texas, United States
• 5: David B. Shmoys , Éva Tardos , Karen Aardal, Approximation algorithms for facility location problems (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.265-274, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258600]