Improved approximation algorithms for low-density instances of the minimum entropy set cover problem

DOI10.1016/j.ipl.2014.02.006zbMath1284.68656arXiv1207.7134OpenAlexW1994940028MaRDI QIDQ2446594

Cosmin Bonchiş, Gabriel I. Istrate

Publication date: 17 April 2014

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

Full work available at URL: https://arxiv.org/abs/1207.7134

zbMATH Keywords

entropyapproximation algorithmsset cover

Mathematics Subject Classification ID

Measures of information, entropy (94A17) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Statistical aspects of information-theoretic topics (62B10)

Cites Work

• Heuristic algorithms in computational molecular biology
• Minimum entropy combinatorial optimization problems
• Tight results on minimum entropy set cover
• An analysis of the greedy algorithm for the submodular set covering problem
• Incremental cost sharing: Characterization by coalition strategy-proofness
• Minimum entropy orientations

This page was built for publication: Improved approximation algorithms for low-density instances of the minimum entropy set cover problem