×

Minimum entropy orientations. (English) Zbl 1152.05318

Summary: We study graph orientations that minimize the entropy of the in-degree sequence. We prove that the minimum entropy orientation problem is NP-hard even if the graph is planar, and that there exists a simple linear-time algorithm that returns an approximate solution with an additive error guarantee of 1 bit.

MSC:

05C07 Vertex degrees
05C85 Graph algorithms (graph-theoretic aspects)
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] U. Berenholz, U. Feige, D. Peleg, Improved approximation for min-sum vertex cover, Technical Report MCS06-07, Computer Science and Applied Mathematics, Weizmann Institute of Science, 2006; U. Berenholz, U. Feige, D. Peleg, Improved approximation for min-sum vertex cover, Technical Report MCS06-07, Computer Science and Applied Mathematics, Weizmann Institute of Science, 2006
[2] Cardinal, J.; Fiorini, S.; Joret, G., Minimum entropy coloring, (Proceedings of the 16th International Symposium on Algorithms and Computation. Proceedings of the 16th International Symposium on Algorithms and Computation, ISAAC 2005. Proceedings of the 16th International Symposium on Algorithms and Computation. Proceedings of the 16th International Symposium on Algorithms and Computation, ISAAC 2005, Lecture Notes in Computer Science, vol. 3827 (2005), Springer: Springer Berlin), 819-828 · Zbl 1175.05052
[3] Cardinal, J.; Fiorini, S.; Joret, G., Tight results on minimum entropy set cover, Algorithmica, 51, 1, 49-60 (2008) · Zbl 1139.68056
[4] Cover, T. M.; Thomas, J. A., Elements of Information Theory (2006), Wiley-Interscience · Zbl 1140.94001
[5] Feige, U.; Lovász, L.; Tetali, P., Approximating min sum set cover, Algorithmica, 40, 4, 219-234 (2004) · Zbl 1082.68126
[6] Fukunaga, T.; Halldórsson, M. M.; Nagamochi, H., Robust cost colorings, (Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms. Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’08 (2008), Society for Industrial and Applied Mathematics: Society for Industrial and Applied Mathematics Philadelphia, PA, USA), 1204-1212 · Zbl 1192.90071
[7] Groenevelt, H., Two algorithms for maximizing a separable concave function over a polymatroid feasible region, European J. Oper. Res., 54, 2, 227-236 (1991) · Zbl 0745.90059
[8] Halperin, E.; Karp, R. M., The minimum-entropy set cover problem, Theoret. Comput. Sci., 348, 2-3, 240-250 (2005) · Zbl 1081.94008
[9] Hardy, G. H.; Littlewood, J. E.; Pólya, G., Inequalities, (Cambridge Mathematical Library (1988), Cambridge University Press: Cambridge University Press Cambridge), Reprint of the 1952 edition · Zbl 0634.26008
[10] Hochbaum, D. S., Lower and upper bounds for the allocation problem and other nonlinear optimization problems, Math. Oper. Res., 19, 2, 390-409 (1994) · Zbl 0820.90082
[11] Li, P. C.; Toulouse, M., Variations of the maximum leaf spanning tree problem for bipartite graphs, Inform. Process. Lett., 97, 4, 129-132 (2006) · Zbl 1181.68176
[12] Moore, C.; Robson, J. M., Hard tiling problems with simple tiles, Discrete Comput. Geom., 26, 4, 573-590 (2001) · Zbl 1021.68097
[13] Moriguchi, S.; Shioura, A., On Hochbaum’s proximity-scaling algorithm for the general resource allocation problem, Math. Oper. Res., 29, 2, 394-397 (2004) · Zbl 1082.90099
[14] Schrijver, A., Matroids, trees, stable sets, (Combinatorial Optimization. Polyhedra and Efficiency. Vol. B. Combinatorial Optimization. Polyhedra and Efficiency. Vol. B, Algorithms and Combinatorics, vol. 24 (2003), Springer-Verlag: Springer-Verlag Berlin), (Chapters 39-69)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.