NDLI: Approximation Algorithms for Data Placement Problems

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Baev, Ivan Rajaraman, Rajmohan Swamy, Chaitanya
Copyright Year	2008
Abstract	We develop approximation algorithms for the problem of placing replicated data in arbitrary networks, where the nodes may both issue requests for data objects and have capacity for storing data objects so as to minimize the average data-access cost. We introduce the data placement problem to model this problem. We have a set of caches $\mathcal{F}$, a set of clients $\mathcal{D}$, and a set of data objects $\mathcal{O}$. Each cache i can store at most $u_i$ data objects. Each client $j\in\mathcal{D}$ has demand $d_j$ for a specific data object $o(j)\in\mathcal{O}$ and has to be assigned to a cache that stores that object. Storing an object o in cache i incurs a storage cost of $f_i^o$, and assigning client j to cache i incurs an access cost of $d_jc_{ij}$. The goal is to find a placement of the data objects to caches respecting the capacity constraints, and an assignment of clients to caches so as to minimize the total storage and client access costs. We present a 10-approximation algorithm for this problem. Our algorithm is based on rounding an optimal solution to a natural linear-programming relaxation of the problem. One of the main technical challenges encountered during rounding is to preserve the cache capacities while incurring only a constant-factor increase in the solution cost. We also introduce the connected data placement problem to capture settings where write-requests are also issued for data objects, so that one requires a mechanism to maintain consistency of data. We model this by requiring that all caches containing a given object be connected by a Steiner tree to a root for that object, which issues a multicast message upon a write to (any copy of) that object. The total cost now includes the cost of these Steiner trees. We devise a 14-approximation algorithm for this problem. We show that our algorithms can be adapted to handle two variants of the problem: (a) a k-median variant, where there is a specified bound on the number of caches that may contain a given object, and (b) a generalization where objects have lengths and the total length of the objects stored in any cache must not exceed its capacity.
Starting Page	1411
Ending Page	1429
Page Count	19
File Format	PDF
ISSN	00975397
DOI	10.1137/080715421
e-ISSN	10957111
Journal	SIAM Journal on Computing (SMJCAT)
Issue Number	4
Volume Number	38
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2008-08-27
Access Restriction	Subscribed
Subject Keyword	data placement Approximation methods and heuristics Approximation algorithms linear programming approximation algorithms Analysis of algorithms Discrete location and assignment facility location
Content Type	Text
Resource Type	Article
Subject	Mathematics Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Approximation Algorithms for Metric Facility Location Problems

LP-Based Algorithms for Capacitated Facility Location

Local Search Heuristics for k-Median and Facility Location Problems

Constant-Factor Approximation for Ordered k-Median

Improved Combinatorial Algorithms for Facility Location Problems

An O(loglog n)-Approximation for Submodular Facility Location

Approximation Algorithms for Hard Capacitated $k$-facility Location Problems

An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem

Improved approximation of the general soft-capacitated facility location problem

Approximation Algorithms for Data Placement Problems

Similar Documents

Approximation Algorithms for Metric Facility Location Problems

LP-Based Algorithms for Capacitated Facility Location

Local Search Heuristics for k-Median and Facility Location Problems

Constant-Factor Approximation for Ordered k-Median

Improved Combinatorial Algorithms for Facility Location Problems

An O(loglog n)-Approximation for Submodular Facility Location

Approximation Algorithms for Hard Capacitated $k$-facility Location Problems

An Optimal Bifactor Approximation Algorithm for the Metric Uncapacitated Facility Location Problem

Improved approximation of the general soft-capacitated facility location problem

Approximation Algorithms for Data Placement Problems