Paper Info
Title
The lazy bureaucrat problem with common arrivals and deadlines: approximation and mechanism design
Abstract
We study the Lazy Bureaucrat scheduling problem (Arkin, Bender, Mitchell and Skiena [1]) in the case of common arrivals and deadlines. In this case the goal is to select a subset of given jobs in such a way that the total processing time is minimized and no other job can fit into the schedule. Our contribution comprises a linear time 4/3-approximation algorithm and an FPTAS, which respectively improve on a linear time 2-approximation algorithm and a PTAS given for the more general case of common deadlines [2,3]. We then consider a selfish perspective, in which jobs are submitted by players who may falsely report larger processing times, and show a tight upper bound of 2 on the approximation ratio of strategyproof mechanisms, even randomized ones. We conclude by introducing a maximization version of the problem and a dedicated greedy algorithm.
Year
DOI
Venue
2013
10.1007/978-3-642-40164-0_18
FCT
Keywords
Field
DocType
lazy bureaucrat scheduling problem,mechanism design,3-approximation algorithm,2-approximation algorithm,lazy bureaucrat problem,dedicated greedy algorithm,linear time,larger processing time,common deadline,total processing time,general case,common arrival
Discrete mathematics,Mathematical optimization,Strategyproof,Job shop scheduling,Upper and lower bounds,Computer science,Greedy algorithm,Mechanism design,Time complexity,Maximization,Distributed computing
Conference
Citations 
PageRank 
References 
2
0.38
8
Authors
3
Name
Order
Citations
PageRank
Laurent Gourvès124130.97
Jérôme Monnot251255.74
Aris T. Pagourtzis3385.55