The Assignment Problems of Jobs to Machines with Bounded Inter-Machine Costs: NP-hardness, Approximation Algorithms and Their Applications to Networks
| Autor: | 郭建志 |
|---|---|
| Rok vydání: | 2014 |
| Druh dokumentu: | 學位論文 ; thesis |
| Popis: | 103 In this dissertation, we investigate the assignment problem of jobs to machines with bounded inter-machine costs, which aims at minimizing the maximum cost among not only all pairs of a job and its assigned machine but also all pairs of the selected machines. The problem can be applied to the traffic-aware data-locality-aware virtual machine (VM) placement where we consider the hop count between the mountable device and its assigned VM as well as the hop count between any two assigned VMs to reduce the latency of data transmission and shorten the job completion time. In the literature, it has been proved that the proposed assignment problem does not admit any approximation algorithm within a factor of two, whereas no approximation algorithms have been proposed so far. Hence, we initially propose a 3-approximation algorithm, and then propose a 2-approximation algorithm, i.e., an optimal approximation algorithm, with a higher time complexity for the proposed assignment problem. In addition, we generalize the one-to-one assignment problem to a many-to-many assignment problem and propose the approximation algorithms for the many-to-many assignment problem. Finally, we conduct the simulations to evaluate the performance of the proposed algorithms. |
| Databáze: | Networked Digital Library of Theses & Dissertations |
| Externí odkaz: |
|