Please use this identifier to cite or link to this item:
Title: A unified approach to truthful scheduling on related machines
Authors: Epstein, Leah
Levin, Asaf
Van Stee, Rob
First Published: 22-Dec-2015
Publisher: INFORMS (Institute for Operations Research and Management Sciences)
Citation: Mathematics of Operations Research 2016 41:1, 332-351
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: Copyright © 2015, INFORMS (Institute for Operations Research and Management Sciences). Deposited with reference to the publisher’s archiving policy available on the SHERPA/RoMEO website.
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.