Absolute \(o(\log m)\) error in approximating random set covering: an average case analysis

DOI10.1016/J.IPL.2005.02.009zbMath1177.68254OpenAlexW1993664762MaRDI QIDQ1041744

Orestis A. Telelis, Vassilios Zissimopoulos

Publication date: 4 December 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2005.02.009

zbMATH Keywords

algorithmsstatistical analysisrandom set covering

Mathematics Subject Classification ID

Randomized algorithms (68W20)

Related Items (1)

A new approach for solving set covering problem using jumping particle swarm optimization method

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Preserving approximation in the min-weighted set cover problem
• Approximation algorithms for combinatorial problems
• On the ratio of optimal integral and fractional covers
• Evaluation of reliability bounds by set covering models.
• A threshold of ln n for approximating set cover
• A Greedy Heuristic for the Set-Covering Problem

This page was built for publication: Absolute \(o(\log m)\) error in approximating random set covering: an average case analysis