Minimum entropy combinatorial optimization problems

DOI10.1007/S00224-011-9371-2zbMATH Open1259.90109arXiv1008.2928OpenAlexW2900417484MaRDI QIDQ693045FDOQ693045

Samuel Fiorini, Jean Cardinal, Gwenaël Joret

Publication date: 7 December 2012

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

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.

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)

Cites Work

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

Cited In (5)

• 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
• 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)