2016/04/23 by Deeparnab Chakrabarty, Chakrabarty, Deeparnab, Kirankumar Shiragur +1
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS
paper · pdf · doi:10.48550/arxiv.1604.06918
Remark. (added 9th June, 2016.) After posting the version 1 of our paper, it was brought to our notice that our result is not new. Huang and Ott [HO15], and independently, Page and Solis-Oba [PSO16] also obtain the same result
arxiv created 2016/09/11 · arxiv updated 2016/09/13
In the graph balancing problem the goal is to orient a weighted undirected graph to minimize the maximum weighted in-degree. This special case of makespan minimization is NP-hard to approximate to a factor better than 3/2 even when there are only two types of edge weights. In this note we describe a simple 3/2 approximation for the graph balancing problem with two-edge types, settling this very special case of makespan minimization.