Minimum entropy combinatorial optimization problems

DOI10.1007/s00224-011-9371-2zbMath1259.90109arXiv1008.2928OpenAlexW2900417484MaRDI QIDQ693045

Samuel Fiorini, Jean Cardinal, Gwenaël Joret

Publication date: 7 December 2012

Published in: Theory of Computing Systems (Search for Journal in Brave)

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

zbMATH Keywords

entropygraph coloringapproximation algorithmsNP-hardnessset cover

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (3)

Improved approximation algorithms for low-density instances of the minimum entropy set cover problem ⋮ Clique partitioning with value-monotone submodular cost ⋮ On the entropy of couplings

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A Mathematical Theory of Communication
• Greed is good: Approximating independent sets in sparse and bounded-degree graphs
• Entropy splitting for antiblocking corners and perfect graphs
• Tight results on minimum entropy set cover
• Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
• Minimum entropy coloring
• The maximum k-colorable subgraph problem for chordal graphs
• On the sum coloring problem on interval graphs
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Approximating min sum set cover
• A short proof of the NP-completeness of minimum sum interval coloring
• Minimum entropy orientations
• The minimum-entropy set cover problem
• Clique partitioning of interval graphs with submodular costs on the cliques
• A threshold of ln n for approximating set cover
• Minimum Entropy Combinatorial Optimization Problems
• An Efficient Test for Circular-Arc Graphs
• The Complexity of Coloring Circular Arcs and Chords
• Locality in Distributed Graph Algorithms
• Graph Classes: A Survey
• On zero-error source coding with decoder side information
• Zero-error information theory
• Source coding and graph entropies
• An Efficient Algorithm for Partial Order Production
• “Rent-or-Buy” Scheduling and Cost Coloring Problems
• Computational Science – ICCS 2005

This page was built for publication: Minimum entropy combinatorial optimization problems