On the Fractional Solution to the Set Covering Problem

DOI10.1137/0604023zbMath0518.90055OpenAlexW2066503336MaRDI QIDQ3668305

Dorit S. Hochbaum

Publication date: 1983

Published in: SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0604023

zbMATH Keywords

gapset coveringlinear programming relaxationworst case analysisfractional optimal valuezero- one optimal value

Mathematics Subject Classification ID

Fractional programming (90C32) Linear programming (90C05) Permutations, words, matrices (05A05) Boolean programming (90C09)

Related Items

Randomized approximation of bounded multicovering problems, Matchings and covers in hypergraphs, A unified approximation algorithm for node-deletion problems, Bibliography on domination in graphs and some basic definitions of domination parameters

Cites Work

• A Greedy Heuristic for the Set-Covering Problem
• Approximation Algorithms for the Set Covering and Vertex Cover Problems