The Taub Faculty of Computer Science Events and Talks

We consider the Graph Balancing problem, where we are given an undirected multigraph with edge weights and orientation costs. The goal is to find an orientation of the edges that minimizes the worst weighted incoming degree of a vertex (also known as makespan) while minimizing the total orientation cost. Graph Balancing is an interesting special case of the well-known Generalized Assignment Problem (GAP), which is perhaps one of the most famous and extensively studied problems in scheduling theory. In this work we focus on bi-criteria algorithms for Graph Balancing that consider the tradeoff between makespan and the total orientation cost. While a 2-approximation with respect to the makespan with no loss in the total orientation cost is known [Shmoys-Tardos ??], the problem of achieving an approximation better than 2 with respect to the makespan with orientation costs was not studied. We achieve the following results: (1) we show that using known approaches to Graph Balancing any approximation better than 2 with respect to the makespan must lose in the orientation cost; (2) we present an algorithm that achieves a bounded tradeoff between makespan and orientation cost; and (3) we consider extensions of Graph Balancing that include hyperedges and unrelated weights and present improved algorithms for these problems. To the best of our knowledge, for the latter, we present the first approximation algorithm that achieves an approximation better than with respect to the makespan.