Algorithms for storage allocation based on client preferences

Tami Tamir () and Benny Vaksendiser ()
Additional contact information
Tami Tamir: The Interdisciplinary Center
Benny Vaksendiser: The Interdisciplinary Center

Journal of Combinatorial Optimization, 2010, vol. 19, issue 3, No 4, 304-324

Abstract: Abstract We consider a packing problem arising in storage management of Video on Demand (VoD) systems. The system consists of a set of video files (movies) and several servers (disks), each having a limited storage capacity, C, and a limited bandwidth (load capacity), L. The goal in the storage allocation problem is to assign the video files to the servers and the bandwidth to the clients. The induced class-constrained packing problem was studied in the past assuming each client provides a single request for a single movie. This paper considers a more general and realistic model—in which each client ranks all the movies in the system. Specifically, for each client j and movie i, it is known how much client j is willing to pay in order to watch movie i. The goal is to maximize the system’s profit. Alternatively, the client might provide a ranking of the movies and the goal is to maximize the lexicographic profile of the solution. We prove that the problem is NP-complete and present approximation algorithms and heuristics for systems with a single or multiple disks. For a single disk we present an (1−1/e)-approximation algorithm that is extended for systems with storage costs, and for k-round broadcasting, in which each client might be serviced multiple times. For multiple disks we present a (C−1)(e−1)/Ce-approximation algorithm, two heuristics for determining the storage allocation, and an optimal bandwidth-allocation algorithm. In our simulation of a VoD system, we compared the performance of the suggested heuristics for systems with variable parameters and clients with variable preference distributions. We focused on systems in which client preferences and payment are power-law distributed: a few movies are very popular and clients are willing to pay significantly more for watching them. Our results can be applied to other packing and subset selection problems in which clients provide preferences over the elements.

Keywords: Algorithms; Class-constrained packing; Approximation; Heuristics (search for similar items in EconPapers)
Date: 2010
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-009-9259-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:19:y:2010:i:3:d:10.1007_s10878-009-9259-0

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-009-9259-0

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().