Afficher la notice abrégée

dc.contributor.authorGourvès, Laurent
dc.contributor.authorMonnot, Jérôme
dc.contributor.authorPagourtzis, Aris T.
dc.date.accessioned2017-01-07T16:22:52Z
dc.date.available2017-01-07T16:22:52Z
dc.date.issued2013
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/16136
dc.descriptionin Springer series Lecture Notes in Computer Science, vol. 8070en
dc.language.isoenen
dc.subjectoptimisation combinatoireen
dc.subject.ddc003en
dc.subject.classificationjelC.C4.C44en
dc.titleThe Lazy Bureaucrat Problem with Common Arrivals and Deadlines: Approximation and Mechanism Designen
dc.typeCommunication / Conférence
dc.description.abstractenWe 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.en
dc.identifier.citationpages171-182en
dc.relation.ispartoftitleFundamentals of Computation Theoryen
dc.relation.ispartofeditorGąsieniec, Leszek Antoni
dc.relation.ispartofeditorWolter, Frank
dc.relation.ispartofpublnameSpringeren
dc.relation.ispartofpublcityBerlin Heidelbergen
dc.relation.ispartofdate2013
dc.relation.ispartofpages316en
dc.relation.ispartofurl10.1007/978-3-642-40164-0en
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn978-3-642-40163-3en
dc.relation.conftitle19th International Symposium, FCT 2013en
dc.relation.confdate2013-08
dc.relation.confcityLiverpoolen
dc.relation.confcountryUnited Kingdomen
dc.relation.forthcomingnonen
dc.identifier.doi10.1007/978-3-642-40164-0_18en
dc.description.ssrncandidatenonen
dc.description.halcandidateouien
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewednonen
dc.relation.Isversionofjnlpeerreviewednonen
dc.date.updated2017-01-07T16:10:10Z
hal.person.labIds989
hal.person.labIds989
hal.person.labIds245158
hal.identifierhal-01429311*


Fichiers attachés à cette notice

FichiersTailleFormatConsulter

Il n'y a pas de fichiers associés à cette notice.

Ce document fait partie de la (des) collection(s) suivante(s)

Afficher la notice abrégée