The week's pick
Random Articles
Reseach Article
Big Step Greedy Heuristic for Maximum Coverage Problem
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 125 - Number 7 |
| Year of Publication: 2015 |
| Authors: Drona Pratap Chandu |
10.5120/ijca2015905954
|
Drona Pratap Chandu . Big Step Greedy Heuristic for Maximum Coverage Problem. International Journal of Computer Applications. 125, 7 ( September 2015), 19-24. DOI=10.5120/ijca2015905954
Abstract
This paper proposes a greedy heuristic called Big step greedy heuristic and investigates its application to compute approximate solution for maximum coverage problem. Greedy algorithms construct the solution in multiple steps, the classical greedy algorithm for maximum coverage problem, in each step selects one set that contains the greatest number of uncovered elements. The Big step greedy heuristic, in each step selects p (1 <= p <= k) sets such that the union of selected p sets contains the greatest number of uncovered elements by evaluating all the possible p-combinations of given sets. When p=k Big step greedy algorithm behaves like an exact algorithm that computes optimal solution by evaluating all possible k-combinations of the given sets. When p=1 it behaves like the classical greedy algorithm. The Big step greedy heuristic can be combined with local search methods to compute better approximate solution.
References
- Karp, R.M., "Reducibility Among Combinatorial Problems", Complexity of Computer Computations, Plenum Press (1972).
- Tal Grossman, Avishai Wool, "Computational experience with approximation algorithms for the set
- covering problem", European journal of operational research 101, 81-92 (1997).
- Dorit S. Hochbaum, Anu Pathria "Analysis of the Greedy Approach in Problems of Maximum k-Coverage", Naval Research Logistics, Vol. 45, 615-627 (1998).
- Chvatal, V. "A Greedy Heuristic for the Set-Covering Problem", Mathematics of Operations Research, 4(3), 223-235 (1979).
- Johnson, D.S., "Approximation algorithms for combinatorial problems", Journal of Computer System Science 9,256-278 (1974).
- Lovasz L, "On the ratio of optimal integral and fractional cover", Discrete Mathematics, 13,383-390 (1975).
- Haouari, M., Chaouachi, J.S., "A probabilistic greedy search algorithm for combinatorial optimization with application to the set covering problem", Journal of the Operational Research Society 53, 792-799 (2002).
- Vasko, F.J., Wilson, G.R., "An efficient heuristic for large set covering problems" Naval Research Logistics Quarterly 31, 163-171 (1984).
- Feo, T., Resende, M.G.C., "A probabilistic heuristic for a computationally difficult set covering problem", Operations Research Letters 8, 67-71 (1989).
- Aickelin, U., "An indirect genetic algorithm for set covering problems", Journal of the Operational Research Society 53, 1118-1126 (2002).
- Beasley, J.E., Chu, P.C., "A genetic algorithm for the set covering problem", European Journal of Operational Research 94, 392-404 (1996).
- ] Fernando C. Gomes, Claudio N. Meneses, Panos M. Pardalos,Gerardo Valdisio R. Viana, "Experimental Analysis of Approximation Algorithms for the Vertex Cover and Set Covering Problems", Computers & Operations Research, 33, 3520-3534 (2006) .
- T. A. Feo and M. G. C. Resende., "Greedy randomized adaptive search procedures. Journal of Global Optimization", 6, 109-133, (1995).
- DePuy, G.W., Whitehouse, G.E., Moraga, R.J., "Using the meta-raps approach to solve combinatorial problems", In Proceedings of the 2002 Industrial Engineering Research Conference, vol. 19, p. 21 (2002).
- DePuy, G.W., Moraga, R.J., Whitehouse, G., 'Meta-RaPS: A simple and effective approach for solving the traveling salesman problem", Transportation Research Part E: Logistics and Transportation Review 41 (2), 115-130 (2005).
- G. Lan, G. W. DePuy, and G. E.Whitehouse, "An effective and simple heuristic for the set covering problem," European Journal of Operational Research, vol. 176, no. 3, pp. 1387-1403 (2007).
- Mauricio G.C. Resende, "Computing Approximate Solutions of the Maximum Covering Problem with GRASP", Journal of Heuristics, Vol 4, Issue 2, 161-177 (1998).
Index Terms
Keywords