×

zbMATH — the first resource for mathematics

A probabilistic heuristic for a computationally difficult set covering problem. (English) Zbl 0675.90073
The authors present a probabilistic set covering heuristic based on a greedy approach of Chvatal. Computational tests are discussed with instances of set covering problems that arise from Steiner triple systems by their incidence matrices.
Reviewer: J.Terno

MSC:
90C27 Combinatorial optimization
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05B07 Triple systems
65K05 Numerical mathematical programming methods
PDF BibTeX Cite
Full Text: DOI
References:
[1] Avis, D., A note on some computationally difficult set covering problems, Mathematical programming, 18, 138-145, (1980) · Zbl 0429.90047
[2] Balas, E.; Ho, A., Set covering algorithms using cutting planes, heuristics and subgradient optimization: A computational study, Mathematical programming study, 12, 37-60, (1980) · Zbl 0435.90074
[3] Bard, J.F.; Feo, T.A., Minimizing the acquisition cost of flexible manufacturing equipment, ()
[4] Bard, J.F.; Feo, T.A., Operations sequencing in discrete parts manufacturing, () · Zbl 0666.90041
[5] Chv√°tal, V., A greedy heuristic for the set covering problem, Mathematics of operations research, 4, 233-235, (1979) · Zbl 0443.90066
[6] Feo, T.A.; Bard, J.F., A network approach to flight scheduling and maintenance base planning, ()
[7] Fulkerson, D.R.; Nemhauser, G.L.; Trotter, L.E., Two computationally difficult set covering problems that arise in computing the 1-width of incidence matrices of Steiner triple systems, Mathematical programming study, 2, 72-81, (1974) · Zbl 0353.90060
[8] Garey, M.R.; Johnson, D.S., Computers and intractability: A guide to the theory of NP-completeness, (1979), Freeman and Company New York · Zbl 0411.68039
[9] Geoffrion, A.M., An improved implicit enumeration approach for integer programming, Operations research, 17, 437-454, (1969) · Zbl 0174.20801
[10] Hall, M., Combinatorial theory, (1967), Blaisdell Company Waltham, MA · Zbl 0196.02401
[11] Hart, J.P.; Shogan, A.W., Semi-greedy heuristics: an empirical study, Operations research letters, 6, 107-114, (1987) · Zbl 0615.90082
[12] Karmarkar, N.; Ramakrishnan, K.G.; Resende, M.G.C., Private communication, (1988), AT&T Bell Laboratories Murray Hill, NJ
[13] Ramakrishnan, K.G., Private communication, (1987), AT&T Bell Laboratories Murray Hill, NJ
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.