Coordination Mechanisms for Unrelated Machine Scheduling

Abed, Fidaa

Local TagsRelease HistoryDetailsSummary

Coordination Mechanisms for Unrelated Machine Scheduling

Abed, F. (2011). Coordination Mechanisms for Unrelated Machine Scheduling. Master Thesis, Universität des Saarlandes, Saarbrücken.

Item is Released

show all hide all

Basic

show hide

Item Permalink: https://hdl.handle.net/11858/00-001M-0000-0027-A1A2-B Version Permalink: https://hdl.handle.net/11858/00-001M-0000-0027-A1A3-9

Genre: Thesis

Files

show Files

hide Files

:

Fidaa Abed_Master's Thesis.pdf (Any fulltext), 161KB

File Permalink:
-

Name:
Fidaa Abed_Master's Thesis.pdf

Description:
-

OA-Status:

Visibility:
Restricted (Max Planck Institute for Informatics, MSIN; )

MIME-Type / Checksum:
application/pdf

Technical Metadata:

Copyright Date:
-

Copyright Info:
-

License:
-

Locators

show

Creators

show

hide

Creators:
Abed, Fidaa^{1, 2}, Author
Mehlhorn, Kurt¹, Advisor
Huang, Chien-Chung¹, Referee

Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019
2International Max Planck Research School, MPI for Informatics, Max Planck Society, ou_1116551

Content

show

hide

Free keywords: -

Abstract: We investigate load balancing games in the context of unrelated machines scheduling. In such a game, there are a number of jobs and a number of machines, and each job needs to be scheduled on one machine. A collection of values pij are given, where pij indicates the processing time of job i on machine j. Moreover, each job is controlled by a selfish player who only wants to minimize the completion time of his job while disregarding other players' welfare. The outcome schedule is a Nash equilibrium if no player can unilaterally change his machine and reduce the completion time of his job. It is known that in an equilibrium, the performance of the system can be far from optimal. The degradation of the system performance in Nash equilibrium is defined as the price of anarchy (PoA): the ratio of the cost of the worst Nash equilibrium to the cost of the optimal scheduling. Clever scheduling policies can be designed to reduce PoA. These scheduling policies are called coordination mechanisms. It has been posed as an open question "what is the best possible lower bound when coordination mechanisms use preemption". In this thesis we prove a lower bound of ( logm log logm) for all symmetric preemptive coordination mechanisms. Moreover we study the lower bound for the unusual case when the coordination mechanisms are asymmetric and we get the same bound under the weak assumption that machines have no IDs. On the positive side we prove that the inefficiency-based mechanism can achieve a constant PoA when the maximum inefficiency of the jobs is bounded by a constant.

Details

show

hide

Language(s): eng - English

Dates: Accepted: 2011-10Date issued: 2011

Publication Status: Issued

Pages: -

Publishing info: Saarbrücken : Universität des Saarlandes

Table of Contents: -

Rev. Type: -

Identifiers: BibTex Citekey: Abed2011

Degree: Master

Event

show

Legal Case

show

Project information

show

Source

show