Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
The subset assignment problem for data placement in caches
Ghandeharizadeh S., Irani S., Lam J. Algorithmica80 (7):2201-2220,2018.Type:Article
Date Reviewed: Mar 6 2019

This paper gives an approximation algorithm for the subset assignment problem (SAP). Given a set of n items of varying sizes, a set of d bins of varying capacities, and a cost c(p,S) associated for each item p and subset S of bins, the objective of SAP is to place the items in the bins at minimal cost. An item may be assigned to more than one bin. Also, there is a cost to not assigning an item to any bin.

For the application that motivated this problem, n is very large and d is very small. Also, the capacities of the bins are much larger than the capacities of the items. If we allow fractional assignments in which at most d items are fractionally assigned, then we get an LP relaxation of SAP in n2d variables, one for each (p,S). To guarantee a solution in which all bins are filled to capacity, for each bin a new item p is introduced, that is, c(p) = 0 and c(p,S) = ∞. The problem has a basic feasible solution guaranteed by the empty set option. Given a feasible solution, the algorithm uses a series of steps called augmentations to improve the cost of the feasible solution. If an assignment is not a basic feasible solution, the RESTORE algorithm makes it a basic feasible solution without increasing the cost. The overall complexity is shown to be O(C(3d,d) poly(d)n logn log(nC) log(Z)), where Z is the maximum size of any item and C is the maximum cost of any (p,S).

This paper makes an important contribution to the area of approximation algorithms for combinatorial optimization, building on ideas developed earlier for the minimum cost flows on bipartite graphs. Besides the significance of this contribution to a practical problem and an intricate complexity analysis, the authors have also established interesting generalizations of certain results in the minimum cost flow problem (lemma 1).

Reviewer:  Krishnaiyan Thulasiraman Review #: CR146459 (1905-0186)
Bookmark and Share
 
Algorithms (I.1.2 )
 
 
General (F.2.0 )
 
 
General (G.2.0 )
 
Would you recommend this review?
yes
no
Other reviews under "Algorithms": Date
Standard bases and some computations in rings of power series
Becker T. Journal of Symbolic Computation 10(2): 165-178, 1990. Type: Article
Dec 1 1992
Real zeroes of polynomials
Collins G. (ed), Loos R., Springer-Verlag New York, Inc., New York, NY, 1983. Type: Book (9780387817767)
Jun 1 1985
Fast parallel absolute irreducibility testing
Kaltofen E. (ed) Journal of Symbolic Computation 1(1): 57-68, 1985. Type: Article
Apr 1 1989
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy