Worst Case Analysis of a Class of Set Covering Heuristics.

Abstract

The Set Covering problem is notoriously hard to solve and is, in fact, NP-complete. A good heuristic algorithm that gives a close approximation to the optimum is therefore desirable. Chvatal found the tight worst case bound of the greedy heuristic commonly considered in the literature. In this paper, we investigate the worst case behavior of a general class of heuristic algorithms. These worst case bounds are found to be dominated by that of the greedy heuristic.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jun 01, 1979
Accession Number
ADA097761

Entities

People

  • Andrew C. Ho

Organizations

  • Carnegie Mellon University

Tags

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Coefficients
  • Coverings
  • Governments
  • Literature
  • Mathematics
  • Notation
  • Numbers
  • Pennsylvania
  • Real Numbers
  • Schools
  • Sequences
  • Two Dimensional
  • Universities

Fields of Study

  • Computer science

Readers

  • Operations Research