Robust cost colorings

ABSTRACT

We consider graph coloring problems where the cost of a coloring is the sum of the costs of the colors, and the cost of a color is a monotone concave function of the total weight of the class. This models resource allocation problems where the cost of a resource depends on the use of the resource. The specific case of interval graphs is of special interest as multi-criteria interval scheduling. We give an algorithm for all perfect graphs that yields a robust coloring: a particular solution that simultaneously approximates all concave functions. For graphs with uniform weights, we show how to modify the solution to approximate any monotone cost function. We complement these results with a number of hardness results and some exact algorithms on restricted classes of graphs.

REFERENCES

• 1: N. Alon and A. Orlitsky. Source coding and graph entropies. IEEE Trans. Inform. Theory, 25(4):1329--1339, 1996.
• 2: E. M. Arkin , E. B. Silverberg, Scheduling jobs with fixed start and end times, Discrete Applied Mathematics, v.18 n.1, p.1-8, Nov. 1987 [doi>10.1016/0166-218X(87)90037-0 ]
• 3: Yossi Azar , Amir Epstein, Convex programming for scheduling unrelated parallel machines, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060639]
• 4: Yossi Azar , Leah Epstein , Yossi Richter , Gerhard J. Woeginger, All-norm approximation algorithms, Journal of Algorithms, v.52 n.2, p.120-133, August 2004 [doi>10.1016/j.jalgor.2004.02.003]
• 5: Hans L. Bodlaender , Klaus Jansen, Restrictions of graph partition problems. Part I, Theoretical Computer Science, v.148 n.1, p.93-109, Aug. 21, 1995 [doi>10.1016/0304-3975(95)00057-4 ]
• 6: K. Cameron. Antichain sequences. Order, 2:249--255, 1985.
• 7: J. Cardinal, S. Fiorini, and G. Joret. Minimum entropy coloring. In ISAAC, 2005.
• 8: Kedar Dhamdhere , Vineet Goyal , R. Ravi , Mohit Singh, How to Pay, Come What May: Approximation Algorithms for Demand-Robust Covering Problems, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.367-378, October 23-25, 2005 [doi>10.1109/SFCS.2005.42]
• 9: J. Edmonds. Maximum matching and a polyhedron with 0,1-vertices. J. Res. Nat. Bur. Standards Sect. B, 69:125--130, 1965.
• 10: Bruno Escoffier , Jérôme Monnot , Vangelis Th. Paschos, Weighted coloring: further complexity and approximability results, Information Processing Letters, v.97 n.3, p.98-103, 14 February 2006 [doi>10.1016/j.ipl.2005.09.013]
• 11: Uriel Feige, Approximating Maximum Clique by Removing Subgraphs, SIAM Journal on Discrete Mathematics, v.18 n.2, p.219-225, 2005 [doi>10.1137/S089548010240415X]
• 12: Uriel Feige , Joe Kilian, Zero knowledge and the chromatic number, Journal of Computer and System Sciences, v.57 n.2, p.187-199, Oct. 1998 [doi>10.1006/jcss.1998.1587 ]
• 13: A. Frank. On chain and antichain families of a partially ordered set. J. Combin. Theory Series B, 29:176--184, 1980.
• 14: T. Fukunaga, M. Halldórsson, and H. Nagamochi. "Rent-or-Buy" scheduling and cost coloring problems. In FSTTCS, December 2007.
• 15: D. Gijswijt, V. Jost, and M. Queyranne. Clique partitioning of interval graphs with submodular costs on the cliques. Technical report, EGRES Technical Report 2006--14, www.cs.elte.hu/egres, 2006.
• 16: A. Goel and A. Meyerson. Simultaneous optimization via approximate majorization for concave profits or convex costs. Algorithmica, 44:301--323, 2006.
• 17: M. Hajiaghayi, M. Mahdian, and V. S. Mirrokni. The facility location problem with general cost functions. Networks, 42:42--47, 2003.
• 18: Magnús M. Hallórsson, A still better performance guarantee for approximate graph coloring, Information Processing Letters, v.45 n.1, p.19-23, Jan. 25, 1993 [doi>10.1016/0020-0190(93)90246-6 ]
• 19: M. M. Halldórsson and G. Kortsarz. Tools for multi-coloring with applications to planar graphs and partial k-trees. J. Algorithms, 42(2):334--366, 2002.
• 20: G. H. Hardy, J. E. Littlewood, and G. Polya. Some simple inequalities satisfied by convex functions. Messenger Mathematics, 58:145--152, 1929.
• 21: Refael Hassin , Shlomi Rubinstein, Robust Matchings, SIAM Journal on Discrete Mathematics, v.15 n.4, p.530-537, 2002 [doi>10.1137/S0895480198332156]
• 22: A. W. Kolen, J. K. Lenstra, C. H. Papadimitriou, and F. C. Spieksma. Interval scheduling: A survey. Naval Research Logistics, 54:530--543, 2007.
• 23: Cécile Murat , Vangelis Th. Paschos, On the probabilistic minimum coloring and minimum k-coloring, Discrete Applied Mathematics, v.154 n.3, p.564-586, 1 March 2006 [doi>10.1016/j.dam.2005.06.007]
• 24: S. V. Pemmaraju and R. Raman. Approximation algorithms for the max-coloring problem. In ICALP, pages 1064--1075, 2005.
• 25: Chaitanya Swamy , David B. Shmoys, Approximation algorithms for 2-stage stochastic optimization problems, ACM SIGACT News, v.37 n.1, March 2006 [doi>10.1145/1122480.1122493]
• 26: Mihalis Yannakakis , Fanica Gavril, The maximum k-colorable subgraph problem for chordal graphs, Information Processing Letters, v.24 n.2, p.133-137, January 1987 [doi>10.1016/0020-0190(87)90107-4 ]
• 27: David Zuckerman, Linear degree extractors and the inapproximability of max clique and chromatic number, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132612]