Minimum entropy combinatorial optimization problems
From MaRDI portal
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
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)- On the entropy of couplings
- Clique partitioning with value-monotone submodular cost
- Improved approximation algorithms for low-density instances of the minimum entropy set cover problem
- The minimum-entropy set cover problem
- Minimum entropy combinatorial optimization problems
- Minimum entropy orientations
- 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)
