Absolute \(o(\log m)\) error in approximating random set covering: an average case analysis
type: Item
instance of: scholarly article
title: Absolute \(o(\log m)\) error in approximating random set covering: an average case analysis
zbMATH Open document ID: 1177.68254
author: Orestis A. Telelis
author: V. Zissimopoulos
published in: Information Processing Letters
publication date: 2009-12-04T00:00:00Z
Mathematics Subject Classification ID: 68W20
zbMATH DE Number: 5642337
zbMATH Keywords: random set covering
zbMATH Keywords: algorithms
zbMATH Keywords: statistical analysis
MaRDI profile type: Publication
full work available at URL: j.ipl.2005.02.009
OpenAlex ID: W1993664762
cites work: A Greedy Heuristic for the Set-Covering Problem
cites work: A threshold of ln n for approximating set cover
cites work: Q5541610
cites work: Preserving approximation in the min-weighted set cover problem
cites work: Approximation algorithms for combinatorial problems
cites work: On the ratio of optimal integral and fractional covers
cites work: Q4228498
cites work: Evaluation of reliability bounds by set covering models.
cites work: Q3824115
DOI: 10.1016/J.IPL.2005.02.009
description: scientific article; zbMATH DE number 5642337