Article ID: | iaor201112943 |
Volume: | 18 |
Issue: | 4 |
Start Page Number: | 449 |
End Page Number: | 453 |
Publication Date: | Jul 2011 |
Journal: | International Transactions in Operational Research |
Authors: | Vasko Francis J, Gorman Patrick, Kunkel Jeffrey D |
Keywords: | heuristics, graphs |
Rappos and Thompson use a set covering formulation and a commercial software package to solve the problem of trying to minimize the number of data sets that have to be read in retrieving all new housing benefit (HB) data entries for a fixed period of time. In this paper, we show that determining the minimum number of data sets that have to be read in retrieving all new HB data entries for a fixed period of time can be solved by finding a minimum size clique cover for an interval graph. Since it is well-known that a greedy algorithm finds a guaranteed minimum size clique cover for an interval graph, this approach will be more efficient than a set covering approach. Finally, it is obvious that this interval graph formulation and greedy algorithm solution approach is applicable to other data retrieval problems.