Clique partitioning with value-monotone submodular cost

Garey, 1979 Zuckerman, 2007, Linear degree extractors and the inapproximability of max clique and chromatic number, Theory Comput., 3, 103, 10.4086/toc.2007.v003a006 Bodlaender, 1995, Restrictions of graph partition problems. Part I, Theoret. Comput. Sci., 148, 93, 10.1016/0304-3975(95)00057-4 Gardi, 2009, Mutual exclusion scheduling with interval graphs or related classes. I, Discrete Appl. Math., 157, 19, 10.1016/j.dam.2008.04.016 Baker, 1996, Mutual exclusion scheduling, Theoret. Comput. Sci., 162, 225, 10.1016/0304-3975(96)00031-X Jansen, 2003, The mutual exclusion scheduling problem for permutation and comparability graphs, Inform. and Comput., 180, 71, 10.1016/S0890-5401(02)00028-7 Hansen, 1993, Bounded vertex colorings of graphs, Discrete Math., 111, 305, 10.1016/0012-365X(93)90165-P Bampis, 2010, Bounded max-colorings of graphs, vol. 6506, 353 Finke, 2008, Batch processing with interval graph compatibilities between tasks, Discrete Appl. Math., 156, 556, 10.1016/j.dam.2006.03.039 Boudhar, 2005, Scheduling on a batch processing machine with split compatibility graphs, J. Math. Model. Algorithms, 4, 391, 10.1007/s10852-005-3083-z Boudhar, 2000, Scheduling on a batch machine with job compatibilities, Belg. J. Oper. Res. Stat. Comput. Sci., 40, 69 Nonner, 2010, Capacitated max-batching with interval graph compatibilities, vol. 6139, 176 Cohen, 1991, NP-completeness of graph decomposition problems, J. Complexity, 7, 200, 10.1016/0885-064X(91)90006-J Lonc, 1992, On complexity of some chain and antichain partition problems, vol. 570, 97 Alon, 1983, A note on the decomposition of graphs into isomorphic matchings, Acta Math. Hungar., 42, 221, 10.1007/BF01956769 Demange, 2007, Time slot scheduling of compatible jobs, J. Sched., 10, 111, 10.1007/s10951-006-0003-7 Escoffier, 2006, Weighted coloring: further complexity and approximability results, Inform. Process. Lett., 97, 98, 10.1016/j.ipl.2005.09.013 Murat, 2006, On the probabilistic minimum coloring and minimum k-coloring, Discrete Appl. Math., 154, 564, 10.1016/j.dam.2005.06.007 Bourgeois, 2009, Probabilistic graph-coloring in bipartite and split graphs, J. Comb. Optim., 17, 274, 10.1007/s10878-007-9112-2 Berge, 1989, Minimax relations for the partial q-colorings of a graph, Discrete Math., 74, 3, 10.1016/0012-365X(89)90193-3 Cameron, 1989, A min–max relation for the partial q-colorings of a graph. Part II: Box perfection, Discrete Math., 74, 15, 10.1016/0012-365X(89)90194-5 Alon, 1996, Source coding and graph entropies, IEEE Trans. Inform. Theory, 42, 1329, 10.1109/18.532875 Cardinal, 2012, Minimum entropy combinatorial optimization problems, Theory Comput. Syst., 51, 4, 10.1007/s00224-011-9371-2 T. Fukunaga, M.M. Halldórsson, H. Nagamochi, Robust cost colorings, in: Proceedings of the 19th Annual ACM–SIAM Symposium on Discrete Algorithms, SODA’08, 2008, pp. 1204–1212. Gijswijt, 2007, Clique partitioning of interval graphs with submodular costs on the cliques, RAIRO Oper. Res., 41, 275, 10.1051/ro:2007024 Pemmaraju, 2005, Approximation algorithms for the max-coloring problem, vol. 3580, 1064 Epstein, 2008, On the max coloring problem, vol. 4927, 142 Nonner, 2011, Clique clustering yields a PTAS for max-coloring interval graphs, vol. 6755, 183 de Werra, 2009, Weighted coloring on planar, bipartite and split graphs: Complexity and approximation, Discrete Appl. Math., 157, 819, 10.1016/j.dam.2008.06.013 Lehmann, 2006, Combinatorial auctions with decreasing marginal utilities, Games Econom. Behav., 55, 270, 10.1016/j.geb.2005.02.006 Federgruen, 1992, The joint replenishment problem with general joint cost structures, Oper. Res., 40, 384, 10.1287/opre.40.2.384 Hajiaghayi, 2003, The facility location problem with general cost functions, Networks, 42, 42, 10.1002/net.10080 Körner, 1998, Zero-error information theory, IEEE Trans. Inform. Theory, 44, 2207, 10.1109/18.720537 Cardinal, 2008, Minimum entropy coloring, J. Comb. Optim., 16, 361, 10.1007/s10878-008-9152-2 L. Hyafil, R.L. Rivest, Graph partitioning and constructing optimal decision trees are polynomial complete problems. Rapport de Recherche 33, IRIA-Laboria, Domaine de Voluceau, Rocquencourt, 78150 Le Chesnay, France, 1973. Cited in [1]. Booth, 1976, Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms, J. Comput. System Sci., 13, 335, 10.1016/S0022-0000(76)80045-1 Gilmore, 1964, A characterization of comparability graphs and of interval graphs, Canad. J. Math., 16, 539, 10.4153/CJM-1964-055-5 Ibarra, 2009, The clique-separator graph for chordal graphs, Discrete Appl. Math., 157, 1737, 10.1016/j.dam.2009.02.006 Dijkstra, 1959, A note on two problems in connexion with graphs, Numer. Math., 1, 269, 10.1007/BF01386390 Hochbaum, 1985, Approximation schemes for covering and packing problems in image processing and VLSI, J. ACM, 32, 130, 10.1145/2455.214106