Combination of parallel machine scheduling and vertex cover

This paper studies a combination of parallel machine scheduling and the vertex cover problem. Given some weighted vertices in an undirected graph, a set of vertices is called a vertex cover if for each edge at least one endpoint belongs to this set. Our problem is to schedule a set of weighted vertices on m identical parallel machines such that the set of vertices is a vertex cover and the makespan is minimized. We develop an approximation algorithm based on the local ratio method and the LPT rule, and prove that it is a -approximation algorithm.