Research

I like to work on some real-life problem which can be abstracted to some nice algorithmic problem, and which can be solved using the existing or new techniques in theoretical computer science. I hope this will lead to some reasonable solutions for the original problem. My interests are in the problems arising in the fields of combinatorial optimization, parallel and distributed systems, and machine learning.

For my PhD I am working on a generalized graph coloring problem which we call as the problem of component coloring of graphs. During my M.Tech. I worked on improving branch and price algorithms for one dimensional cutting stock problem. The project report is available here.

Component Coloring of Graphs

We introduce a generalization of the well known graph (vertex) coloring problem, which we call the component coloring of graphs. For a given graph with weights on vertices in (0,1], the problem is to color the vertices using minimum number of colors such that the total weight of any monochromatic component does not exceed 1. In the unweighted version of the problem, the size of a monochromatic component must not exceed some constant C.

The problem is harder than the vertex coloring problem. Consider the following example graph. It has a maximum clique of size 4. So it needs at least 4 colors. On the left we show a coloring using 4 colors. However, for component coloring with C=2, one would expect that 4/2=2 colors were enough. But it requires 3 colors as shown on the right.

Example of Component Coloring

The problem has direct application in scheduling communication on optical WDM (wavelength division multiplexing) networks using the light-trails technology. The scheduling problem on path networks and ring networks are analogous to the component coloring problem on interval graphs and circular-arc graphs respectively. So we focus on these two classes of graphs. The weighted problem is NP-hard even for the subclass of proper interval graphs. The unweighted problem is NP-hard on circular-arc graphs but the complexity for interval graphs is not known. 

We give a linear time algorithm for the unweighted problem on proper interval graphs. For the weighted problem on a graph of p nodes with the corresponding interval (circular-arc) representation with n endpoints, we give an algorithm that uses O(w+log(n)) colors where w is the weight of the maximum clique and hence a lower bound. We also show a input instance for which Ω(w + log(n)/loglog(n)) colors are needed. 

We also consider an online version, in which the vertices arrive and depart dynamically, and must be colored without modifying the previously colored vertices. For this case we give an online algorithm which has competitive ratio Θ(log(n)). We show that this is optimal in the sense that every on-line algorithm has competitive ratio Ω(log(n)). We also give another online algorithm that is greedy and appears to do well in simulations (for the classes of graphs we consider), but which has competitive ratio between Ω(log^2(n)/loglog(n)) and O(log^2(n)). We also present detailed simulations of both our online algorithms.

Comments