Abstract

The data migration problem is as follows. Given a graph G=(V,E) we want to schedule the edges in E such that no two adjacent edges are scheduled at the same time. We consider two variants of this problem where our objective is to minimize the average completion time of either the edges or the vertices. I will describe combinatorial algorithms for these problems:

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