M.Sc Thesis


M.Sc StudentYeheskel Ran
SubjectGraph Balancing with Orientation Costs
DepartmentDepartment of Computer Science
Supervisor ASSOCIATE PROF. Roy Schwartz
Full Thesis textFull thesis text - English Version


Abstract

In the well known Generalized Assignment Problem we are given a set of n machines and m jobs that need to be processed on these machines. Additionally, for each pair of job j and machine i we are given the time it takes for machine i to process

job j, and cost of assigning job j to machine i. The goal is to find an assignment of the jobs to the machines that minimizes (1) the total assignment costs and (2) the makespan of the assignment, i.e., the time it takes to process all the jobs by the machines (where

each machine, in parallel with respect to the other machines, processes its assigned job).

Motivated by the classic Generalized Assignment Problem, we consider the Graph Balancing problem in the presence of orientation costs: a special case of Generalized Assignment Problem where every job can be assigned to at most two machines and has an equal processing time on those machines.

Graph Balancing was first introduced by Ebenlendr-Krcál-Sgall [Algorithmica ‘14] and can be formulated as a graph optimization problem: given an undirected multi-graph G = (V,E) equipped with edge weights and orientation costs on the edges, the goal is to find an orientation of the edges that minimizes both the maximum weight of edges oriented toward any vertex (makespan) and total orientation cost.

We present a general framework for minimizing makespan in the presence of costs that allows us to: (1) achieve bicriteria approximations for the Graph Balancing problem that capture known previous results (Shmoys-Tardos [Math. Progrm. ‘93],

Ebenlendr-Krcál-Sgall [Algorithmica ‘14], and Wang-Sitters [Inf. Process. Lett. ‘16]); and (2) achieve bicriteria approximations for extensions of the Graph Balancing problem that admit hyperedges and unrelated weights.

We also present bicriteria lower bounds in the form of integrality gaps that show that a loss in the total orientation cost is required if one aims for an approximation better than 2 in the makespan. Our

framework is based on a remarkably simple rounding of a strengthened linear relaxation.

We believe this framework might be of independent interest to other related scheduling problems.