Tight results on minimum entropy set cover

DOI10.1007/s00453-007-9076-8zbMath1139.68056OpenAlexW2169744769MaRDI QIDQ926288

Samuel Fiorini, Gwenaël Joret, Jean Cardinal

Publication date: 27 May 2008

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-007-9076-8

zbMATH Keywords

Greedy algorithmHardness of approximationEntropySet cover

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Approximation algorithms (68W25)

Related Items (10)

Irregular polyomino tiling via integer programming with application in phased array antenna design ⋮ Entropy approximation in lossy source coding problem ⋮ A closest vector problem arising in radiation therapy planning ⋮ A parametric worst-case approach to fairness in cooperative games with transferable utility ⋮ Improved approximation algorithms for low-density instances of the minimum entropy set cover problem ⋮ Minimum Entropy Combinatorial Optimization Problems ⋮ Minimum entropy combinatorial optimization problems ⋮ Minimum entropy orientations ⋮ Independent sets in bounded-degree hypergraphs ⋮ Heapability, Interactive Particle Systems, Partial Orders: Results and Open Problems

Cites Work

• Unnamed Item
• Unnamed Item
• Zero knowledge and the chromatic number
• Geometric algorithms and combinatorial optimization.
• Approximating min sum set cover
• The minimum-entropy set cover problem
• A threshold of ln n for approximating set cover
• A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
• Source coding and graph entropies
• Algorithms and Computation

This page was built for publication: Tight results on minimum entropy set cover