Abstract:

Given a graph G=(V,E) we are to schedule the edge set such that no two
edges incident on the same vertex are scheduled at the same time. We
consider two variants of this problem where the objective is to minimize
the average completion time of the edges or the vertices.

I will describe combinatorial algorithms for these two problems.

 * Edge variant: improved \sqrt{2}-approximation for bipartite graphs.
 * Vertex variant: fast 3-approximation for general graphs.

(Joint work with Rajiv Gandhi)