An Improved Randomized Truthful Mechanism for Scheduling Unrelated Machines

Details An Improved Randomized Truthful Mechanism for Scheduling Unrelated Machines An Improved Randomized Truthful Mechanism for Scheduling Unrelated Machines

2008-02-20

arxiv.org/abs/0802.2851v1

Dans Proceedings of the 25th Annual Symposium on the Theoretical Aspects of Computer Science - STACS 2008, Bordeaux : France (

Computer Science

Data Structures and Algorithms

Scientific paper

We study the scheduling problem on unrelated machines in the mechanism design setting. This problem was proposed and studied in the seminal paper (Nisan and Ronen 1999), where they gave a 1.75-approximation randomized truthful mechanism for the case of two machines. We improve this result by a 1.6737-approximation randomized truthful mechanism. We also generalize our result to a $0.8368m$-approximation mechanism for task scheduling with $m$ machines, which improve the previous best upper bound of $0.875m(Mu'alem and Schapira 2007).

Affiliated with

Also associated with

No associations

Rating

An Improved Randomized Truthful Mechanism for Scheduling Unrelated Machines does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with An Improved Randomized Truthful Mechanism for Scheduling Unrelated Machines, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An Improved Randomized Truthful Mechanism for Scheduling Unrelated Machines will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-647827