M.Sc Student | Poria Or |
---|---|

Subject | Approximation Algorithm for the Resource Dependent Assignment Problem |

Department | Department of Industrial Engineering and Management |

Supervisor | Dr. Liron Yedidsion |

Full Thesis text |

Assignment problems deal with the question of how to assign a set of n agents to a set of n tasks such that each task is performed only once and each agent is assigned to a single task so as to minimize a specific predefined objective.

In this research we define and analyze a special kind of assignment problem where the cost of assigning agent j to task i is a function of the amount of resource allocated to this particular task.

The resources are continuous and non-renewable. We assume the resource consumption function to be convex. The amount of resource allocated to each task is a decision variable.

A solution for our assignment problem is defined by the assignment of agents to tasks and by a resource allocation to each agent. The quality of a solution is measured by two criteria. The first criterion is the total assignment cost and the second is the total weighted resource consumption. We address these criteria via four different problem variations. The first is the minimization of a combined cost function of the two criteria; the second is the minimization of the assignment cost under a limitation of total resource consumption; the third is the minimization of the total resource consumption under a limitation of the assignment cost and the fourth problem is to construct the trade-off curve between assignment cost and total resource consumption.

In this research we provide a ρ-approximation algorithm to solve the second problem variation, where a ρ-approximation algorithm is an algorithm that runs in polynomial time and produces a solution with cost within a factor of at most ρ of the optimal solution.

The approximation algorithm is based on the solution method for the first, polynomial, problem variation. In this variation, the solution is a function of the ratio of the weights given to each criterion. Accordingly, we try to find an efficient solution in which the total resource consumption is not greater than but as close as possible to the total resource limitation.

We prove that using this method guarantees that in any case, the total assignment cost would not exceed ρ times the optimal solution. However, ρ itself is a function of one of the problems parameters, k. This parameter defines the resource's efficiency and according to literature is usually confined within 0.5<k<2. For this range our approximation ratio is in fact confined within 1.17<ρ<1.62.