Using an interval graph approach to efficiently solve the housing benefit data retrieval problem

Using an interval graph approach to efficiently solve the housing benefit data retrieval problem

0.00 Avg rating0 Votes
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: , ,
Keywords: heuristics, graphs
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.