Optimal Integer and Fractional Covers: A Sharp Bound on Their Ratio.

Abstract

The ratio of the values of optimal integer and fractional solutions to a set covering problem was shown by Johnson and Lovasz to be bounded by B(d) = 1 + ln(d), where d is the largest column sum.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 01, 1981
Accession Number
ADA104829

Entities

People

  • Egon Balas

Organizations

  • Carnegie Mellon University

Tags

DTIC Thesaurus Topics

  • Coefficients
  • Contracts
  • Coverings
  • Governments
  • Guarantees
  • Inequalities
  • Intervals
  • Linear Programming
  • Mathematics
  • Military Research
  • Pennsylvania
  • Republic
  • Schools
  • Scientists
  • Sequences
  • Universities

Readers

  • Graph Algorithms and Convex Optimization.