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 (4)

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

This page was built for publication: On the Fractional Solution to the Set Covering Problem