๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Parallel and serial heuristics for the minimum set cover problem

โœ Scribed by Sreejit Chakravarty; Ajay Shekhawat

Publisher
Springer US
Year
1992
Tongue
English
Weight
695 KB
Volume
5
Category
Article
ISSN
0920-8542

No coin nor oath required. For personal study only.

โœฆ Synopsis

We present a theoretical analysis and an experimental evaluation of four serial heuristics and four parallel heuristics for the minimum set cover problem. The serial heuristics trade off run time with the quality of the solution. The parallel heuristics are derived from one of the serial heuristics. These heuristics show considerable speedup when the number of processors is increased. The quality of the solution computed by the heuristics does not degrade with an increase in the number of processors.

๐Ÿ“œ SIMILAR VOLUMES

Simple Lagrangian heuristic for the set
Simple Lagrangian heuristic for the set covering problem
โœ Salim Haddadi ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 353 KB

In this paper a simple Lagrangian heuristic is proposed for the set covering problem. It is based on simple and classica1 ideas: Lagrangian duality, greedy heuristic for the set covering problem, subgradient optimization and redundant covers. The main interesting point of the paper lies in the fact