Please use this identifier to cite or link to this item:
Title: A Unified Approach to Truthful Scheduling on Related Machines
Authors: Van Stee, Rob
Epstein, L.
Levin, A.
First Published: 22-Dec-2015
Publisher: INFORMS (Institute for Operations Research and Management Sciences)
Citation: Mathematics of Operations Research, 2016, 41 (1), pp. 332-351 (20)
Abstract: We present a unified framework for designing deterministic monotone polynomial time approximation schemes (PTASs) for a wide class of scheduling problems on uniformly related machines. This class includes (among others) minimizing the makespan, maximizing the minimum load, and minimizing the p-norm of the machine loads vector. Previously, this kind of result was only known for the makespan objective. Monotone algorithms have the property that an increase in the speed of a machine cannot decrease the amount of work assigned to it. Our results imply the existence of a truthful mechanism that can be implemented in polynomial time, where the social goal is approximated within arbitrary precision.
DOI Link: 10.1287/moor.2015.0730
ISSN: 0364-765X
eISSN: 1526-5471
Version: Post-print
Status: Peer-reviewed
Type: Journal Article
Rights: The file associated with this record is distributed after the end of the embargo period under the Creative Commons “Attribution Non-Commercial No Derivatives” licence, further details of which can be found via the following link:
Description: The file associated with this record is under a 12-month embargo from publication in accordance with the publisher's self-archiving policy. The full text may be available through the publisher links provided above.
Appears in Collections:Published Articles, Dept. of Computer Science

Files in This Item:
File Description SizeFormat 
monotone_PTAS_MOR_revised5-1.pdfPost-review (final submitted)295.98 kBUnknownView/Open

Items in LRA are protected by copyright, with all rights reserved, unless otherwise indicated.