User menu

A Note On Some Computationally Difficult Set Covering Problems

Bibliographic reference Avis, D.. A Note On Some Computationally Difficult Set Covering Problems. In: Mathematical Programming, Vol. 18, no. 2, p. 138-145 (1980)
Permanent URL http://hdl.handle.net/2078.1/60713
  1. V. Chvátal, “Hard knapsack problems”,Journal of Operations Research, to appear.
  2. V. Chvátal, “A greedy heuristic for the set covering problem”, Publication No. 284, Département d'Informatique et de Recherche Opérationnelle, Université de Montréal, Montréal (1978).
  3. V. Chvátal, “Determining the stability number of a graph”,SIAM Journal on Computing 6 (1977) 643–662.
  4. S.A. Cook and R.A. Reckhow, “On the Lengths of Proofs in the Propositional Calculus”,Proceedings of 6th Annual ACM Symposium on Theory of Computing (1974) 135–148.
  5. R. Fulkerson, G. Nemhauser and L. Trotter, “Two computationally difficult set covering problems that arise in computing the 1-width of incidence matrices of Steiner triple systems”,Mathematical Programming Study 2 (1974) 72–81.
  6. R. Garfinkel and G. Nemhauser,Integer programming (Wiley, New York, 1969).
  7. A. Geoffrion, “An improved implicit enumeration approach for integer programming”,Journal of Operations Research 17 (1969) 437–454.
  8. M. Hall Jr.,Combinatorial theory (Blaisdell Company, Waltham, MA, 1967).
  9. C.E. Lemke, H.M. Salkin and K. Spielberg, “Set covering by single branch enumeration with linear programming subproblems”,Journal of Operations Research 19 (1971) 998–1022.
  10. C. McDiarmid, “Determining the chromatic number of a graph”,SIAM Journal on Computing 8 (1979) 1–14.