CFP last date
20 January 2025
Call for Paper
February Edition
IJCA solicits high quality original research papers for the upcoming February edition of the journal. The last date of research paper submission is 20 January 2025

Submit your paper
Know more
The week's pick
Responsive image
SFLA-Based Line Balancing and Task Optimization in Master-Slave Controlled Hanger Transportation Systems for Garment Production

Duc Hoang Nguyen
Random Articles
Reseach Article

Big Step Greedy Heuristic for Maximum Coverage Problem

by Drona Pratap Chandu
journal cover thumbnail

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

@article{ 10.5120/ijca2015905954,
author = { Drona Pratap Chandu },
title = { Big Step Greedy Heuristic for Maximum Coverage Problem },
journal = { International Journal of Computer Applications },
issue_date = { September 2015 },
volume = { 125 },
number = { 7 },
month = { September },
year = { 2015 },
issn = { 0975-8887 },
pages = { 19-24 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume125/number7/22444-2015905954/ },
doi = { 10.5120/ijca2015905954 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T23:15:23.796171+05:30
%A Drona Pratap Chandu
%T Big Step Greedy Heuristic for Maximum Coverage Problem
%J International Journal of Computer Applications
%@ 0975-8887
%V 125
%N 7
%P 19-24
%D 2015
%I Foundation of Computer Science (FCS), NY, USA
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
  1. Karp, R.M., "Reducibility Among Combinatorial Problems", Complexity of Computer Computations, Plenum Press (1972).
  2. Tal Grossman, Avishai Wool, "Computational experience with approximation algorithms for the set
  3. covering problem", European journal of operational research 101, 81-92 (1997).
  4. Dorit S. Hochbaum, Anu Pathria "Analysis of the Greedy Approach in Problems of Maximum k-Coverage", Naval Research Logistics, Vol. 45, 615-627 (1998).
  5. Chvatal, V. "A Greedy Heuristic for the Set-Covering Problem", Mathematics of Operations Research, 4(3), 223-235 (1979).
  6. Johnson, D.S., "Approximation algorithms for combinatorial problems", Journal of Computer System Science 9,256-278 (1974).
  7. Lovasz L, "On the ratio of optimal integral and fractional cover", Discrete Mathematics, 13,383-390 (1975).
  8. 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).
  9. Vasko, F.J., Wilson, G.R., "An efficient heuristic for large set covering problems" Naval Research Logistics Quarterly 31, 163-171 (1984).
  10. Feo, T., Resende, M.G.C., "A probabilistic heuristic for a computationally difficult set covering problem", Operations Research Letters 8, 67-71 (1989).
  11. Aickelin, U., "An indirect genetic algorithm for set covering problems", Journal of the Operational Research Society 53, 1118-1126 (2002).
  12. Beasley, J.E., Chu, P.C., "A genetic algorithm for the set covering problem", European Journal of Operational Research 94, 392-404 (1996).
  13. ] 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 &amp; Operations Research, 33, 3520-3534 (2006) .
  14. T. A. Feo and M. G. C. Resende., "Greedy randomized adaptive search procedures. Journal of Global Optimization", 6, 109-133, (1995).
  15. 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).
  16. 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).
  17. 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).
  18. 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

Computer Science
Information Sciences

Keywords

Big step Greedy Maximum coverage problem Algorithm Approximation

Powered by PhDFocusTM