Parallel and serial heuristics for the minimum set cover problem

DOI10.1007/BF00127952MaRDI QIDQ1186830zbMATH OpenFDO

Authors Sreejit Chakravarty, Ajay Shekhawat

Publication date 28 June 1992

Published in The Journal of Supercomputing (Search for Journal in Brave)

zbMATH Keywords

approximation algorithmsoptimization problemsminimum set cover problemparallel heuristics

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99)

Recommendations

• scientific article; zbMATH DE number 8779
• A New Efficient Heuristic for the Minimum Set Covering Problem
• Hybrid heuristics for minimum cardinality set covering problems
• An optimal parallel algorithm for the minimum circle-cover problem
• Experiments with parallel branch-and-bound algorithms for the set covering problem
• A parallel algorithm for approximating the minimum cycle cover
• Exact and heuristic approaches for the set cover with pairs problem
• A hybrid heuristic for the set covering problem
• Parallel approximation for partial set cover
• An efficient heuristic for large set covering problems

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A Greedy Heuristic for the Set-Covering Problem
• Approximation algorithms for combinatorial problems
• On the ratio of optimal integral and fractional covers
• Parallel Merge Sort

Cited in

(5)

• Solving the set cover problem on a supercomputer
• Instance-specific accelerators for minimum covering
• Implementation algorithms for solution of covering problems and analysis of their efficiency
• Design and research of the parallel combinatorial algorithms
• On parallelizing a greedy heuristic for finding small dominant sets

This page was built for publication: Parallel and serial heuristics for the minimum set cover problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1186830)