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

DOI10.1016/J.IPL.2014.02.006MaRDI QIDQ2446594zbMATH OpenOpenAlexFDO

Authors Cosmin Bonchiş, Gabriel 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

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

Abstract: We study the approximability of instances of the minimum entropy set cover problem, parameterized by the average frequency of a random element in the covering sets. We analyze an algorithm combining a greedy approach with another one biased towards large sets. The algorithm is controled by the percentage of elements to which we apply the biased approach. The optimal parameter choice has a phase transition around average density $e$ and leads to improved approximation guarantees when average element frequency is less than $e$.

Recommendations

• Tight results on minimum entropy set cover
• Tight Results on Minimum Entropy Set Cover
• The minimum entropy submodular set cover problem
• New and improved bounds for the minimum set cover problem
• Automata, Languages and Programming
• The minimum-entropy set cover problem
• A Better-Than-Greedy Approximation Algorithm for the Minimum Set Cover Problem
• scientific article; zbMATH DE number 784428
• Approximating the dense set-cover problem
• Efficient approximation of Min Set Cover by moderately exponential algorithms

Cites work

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

Cited in

(3)

• Tight results on minimum entropy set cover
• Tight Results on Minimum Entropy Set Cover
• The minimum-entropy set cover problem

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2446594)