Approximation algorithm for resource allocation problems with time dependent penalties

Abstract

The Resource Allocation Problem with Time Dependent Penalties (RAPTP) is a variant of uncapacitated resource allocation problems generally referred as uncapacitated facility allocation problems or uncapacitated facility location problem (UFLP). Work done in this paper is motivated by the work of Du, Lu and Xu [7] in which authors considered facility location problems with submodular penalties and presented a 3-approximation primal dual algorithm. This paper considers that each unallocated demand point adds to penalty that increases as time passes and is thus represented by function x(ti,pi) where ti and pi are elapse time and priority of demand point di. As this problem has been considered for emergency service allocation, all demand points should be allocated to some facility or resource within some stipulated time limit beyond which it may lose its purpose. Thus penalty incurred by a demand point is considered till that threshold value only. Thus it is assumed that penalty contribution by a demand point remains constant after a specified threshold value. By exploiting the properties of time dependent penalties, a 4-approximation primal-dual algorithm is proposed which is based on LP framework, and is the first constant-factor approximation algorithm for RAPTP.