A truthful mechanism for interval scheduling

Jugal Garg, Peter McGlaughlin

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Motivated by cloud computing, we study a market-based approach for job scheduling on multiple machines where users have hard deadlines and prefer earlier completion times. In our model, completing a job provides a benefit equal to its present value, i.e., the value discounted to the time when the job finishes. Users submit job requirements to the cloud provider who non-preemptively schedules jobs to maximize the social welfare, i.e., the sum of present values of completed jobs. Using a simple and fast greedy algorithm, we obtain a 1+s/(s-1) approximation to the optimal schedule, where s < 1 is the minimum ratio of a job’s deadline to processing time. Building on our approximation algorithm, we construct a pricing rule to incentivize users to truthfully report all job requirements.

Original languageEnglish (US)
Title of host publicationAlgorithmic Game Theory - 11th International Symposium, SAGT 2018, Proceedings
EditorsXiaotie Deng
PublisherSpringer-Verlag Berlin Heidelberg
Number of pages13
ISBN (Print)9783319996592
StatePublished - Jan 1 2018
Event11th International Symposium on Algorithmic Game Theory, SAGT 2018 - Beijing, China
Duration: Sep 11 2018Sep 13 2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11059 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other11th International Symposium on Algorithmic Game Theory, SAGT 2018

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'A truthful mechanism for interval scheduling'. Together they form a unique fingerprint.

Cite this