The minimum-entropy set cover problem

DOI10.1016/j.tcs.2005.09.015zbMath1081.94008OpenAlexW2048568229MaRDI QIDQ2581268

Richard M. Karp, Eran Halperin

Publication date: 9 January 2006

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2005.09.015

zbMATH Keywords

greedy algorithmminimum entropy principlepolynomial time approximation scheme

Mathematics Subject Classification ID

Measures of information, entropy (94A17) Combinatorial aspects of packing and covering (05B40)

Related Items (7)

Irregular polyomino tiling via integer programming with application in phased array antenna design ⋮ Entropy approximation in lossy source coding problem ⋮ Tight results on minimum entropy set cover ⋮ Minimum Entropy Combinatorial Optimization Problems ⋮ Minimum entropy combinatorial optimization problems ⋮ Minimum entropy orientations ⋮ Heapability, Interactive Particle Systems, Partial Orders: Results and Open Problems

Cites Work

• Unnamed Item
• Unnamed Item
• A microscopic study of minimum entropy search in learning decomposable Markov networks
• The hardness of approximation: Gap location
• A threshold of ln n for approximating set cover
• A Greedy Heuristic for the Set-Covering Problem
• On the hardness of approximating minimization problems
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques

This page was built for publication: The minimum-entropy set cover problem