The maximum k-colorable subgraph (MkCS) problem is to find an induced k-colorable subgraph with maximum cardinality in a given graph. This paper is an in-depth analysis of the MkCS problem that considers various semidefinite programming relaxations, including their theoretical and numerical comparisons. To simplify these relaxations, we exploit the symmetry arising from permuting the colors, as well as the symmetry of the given graphs when applicable. We also show how to exploit invariance under permutations of the subsets for other partition problems and how to use the MkCS problem to derive bounds on the chromatic number of a graph. Our numerical results verify that the proposed relaxations provide strong bounds for the MkCS problem and that those outperform existing bounds for most of the test instances. Summary of Contribution: The maximum k-colorable subgraph (MkCS) problem is to find an induced k-colorable subgraph with maximum cardinality in a given graph. The MkCS problem has a number of applications, such as channel assignment in spectrum sharing networks (e.g., Wi-Fi or cellular), very-large-scale integration design, human genetic research, and so on. The MkCS problem is also related to several other optimization problems, including the graph partition problem and the max-k-cut problem. The two mentioned problems have applications in parallel computing, network partitioning, floor planning, and so on. This paper is an in-depth analysis of the MkCS problem that considers various semidefinite programming relaxations, including their theoretical and numerical comparisons. Further, our analysis relates the MkCS results with the stable set and the chromatic number problems. We provide extended numerical results that verify that the proposed bounding approaches provide strong bounds for the MkCS problem and that those outperform existing bounds for most of the test instances. Moreover, our lower bounds on the chromatic number of a graph are competitive with existing bounds in the literature.

We consider the minimum makespan problem for n tasks and two unrelated parallel selfish machines. Let R n be the best approximation ratio of randomized monotone scale-free algorithms. This class contains the most efficient algorithms known for truthful scheduling on two machines. We propose a new M i n − M a x formulation for R n , as well as upper and lower bounds on R n based on this formulation. For the lower bound, we exploit pointwise approximations of cumulative distribution functions (CDFs). For the upper bound, we construct randomized algorithms using distributions with piecewise rational CDFs. Our method improves upon the existing bounds on R n for small n . In particular, we obtain almost tight bounds for n = 2 showing that | R 2 − 1.505996| < 10 − 6 .