Minimum entropy combinatorial optimization problems

DOI10.1007/S00224-011-9371-2MaRDI QIDQ693045zbMATH OpenOpenAlexFDO

Authors Jean Cardinal, Samuel Fiorini, 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

entropyapproximation algorithmsgraph coloringNP-hardnessset cover

Mathematics Subject Classification ID

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

Abstract: We survey recent results on combinatorial optimization problems in which the objective function is the entropy of a discrete distribution. These include the minimum entropy set cover, minimum entropy orientation, and minimum entropy coloring problems.

Recommendations

• Minimum entropy combinatorial optimization problems
• Tight Results on Minimum Entropy Set Cover
• Tight results on minimum entropy set cover
• Minimum entropy orientations
• The minimum entropy submodular set cover problem

Cites work

• scientific article; zbMATH DE number 5764868 (Why is no real title available?)
• scientific article; zbMATH DE number 3769624 (Why is no real title available?)
• scientific article; zbMATH DE number 193053 (Why is no real title available?)
• scientific article; zbMATH DE number 780788 (Why is no real title available?)
• scientific article; zbMATH DE number 6469191 (Why is no real title available?)
• A Mathematical Theory of Communication
• A short proof of the NP-completeness of minimum sum interval coloring
• A threshold of ln n for approximating set cover
• An Efficient Test for Circular-Arc Graphs
• An efficient algorithm for partial order production
• Approximating min sum set cover
• Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Clique partitioning of interval graphs with submodular costs on the cliques
• Computational Science – ICCS 2005
• Entropy splitting for antiblocking corners and perfect graphs
• Graph Classes: A Survey
• Greed is good: Approximating independent sets in sparse and bounded-degree graphs
• Locality in Distributed Graph Algorithms
• Minimum entropy coloring
• Minimum entropy combinatorial optimization problems
• Minimum entropy orientations
• On the sum coloring problem on interval graphs
• On zero-error source coding with decoder side information
• Source coding and graph entropies
• The Complexity of Coloring Circular Arcs and Chords
• The maximum k-colorable subgraph problem for chordal graphs
• The minimum-entropy set cover problem
• Tight results on minimum entropy set cover
• Zero-error information theory
• “Rent-or-Buy” Scheduling and Cost Coloring Problems

Cited in

(7)

• Minimum entropy combinatorial optimization problems
• 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
• Minimum entropy orientations
• The minimum-entropy set cover problem
• Minimal Entropy Approximations and Optimal Algorithms

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

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