Batch processing with interval graph compatibilities between tasks

We analyze batch-scheduling problems that arise in connection with certain industrial applications. The models concern processing on a single max-batch machine with the additional feature that the tasks of the same batch have to be compatible. Compatibility is a symmetric binary relation—the compatible pairs are described with an undirected “compatibility graph”, which is often an interval graph according to some natural practical conditions that we present. We consider several models with varying batch capacities, processing times or compatibility graphs. We summarize known results, and present a min-max formula and polynomial time algorithms.     

Bounded max-colorings of graphs

In a bounded max-coloring of a vertex/edge weighted graph, each color class is of cardinality at most b and of weight equal to the weight of the heaviest vertex/edge in this class. The bounded max-vertex/edge-coloring problems ask for such a coloring minimizing the sum of all color classes' weights. These problems generalize the well known max-coloring problems by taking into account the number of available resources (i.e., the cardinality of color classes) in practical applications. In this paper we present complexity results and approximation algorithms for the bounded max-coloring problems on general graphs, bipartite graphs and trees.     

A note on selective line-graphs and partition colorings

We extend a one-to-one correspondence between the set of all colorings of any graph and the set of all stable sets of an auxiliary graph, from graphs to partitioned graphs. This correspondence has an application to Selective Coloring and to Selective Max-Coloring.     

Clique partitioning with value-monotone submodular cost

We consider the problem of partitioning a graph into cliques of bounded cardinality. The goal is to find a partition that minimizes the sum of clique costs where the cost of a clique is given by a set function on the nodes. We present a general algorithmic solution based on solving the problem variant without the cardinality constraint. We obtain constant factor approximations depending on the solvability of this relaxation for a large class of submodular cost functions which we call value-monotone submodular functions. For special graph classes we give optimal algorithms.