2026-07-18T12:07:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7828 2024-03-06T10:41:21Z ddc:004 open_access

Minimizing Maximum Flow Time on Related Machines via Dynamic Posted Pricing Im, Sungjin Moseley, Benjamin Pruhs, Kirk Stein, Clifford Posted pricing scheme online scheduling related machines maximum flow time competitiveness analysis We consider a setting where selfish agents want to schedule jobs on related machines. The agent submitting a job picks a server that minimizes a linear combination of the server price and the resulting response time for that job on the selected server. The manager's task is to maintain server prices to (approximately) optimize the maximum response time, which is a measure of social good. We show that the existence of a pricing scheme with certain competitiveness is equivalent to the existence of a monotone immediate-dispatch algorithm. Our main result is a monotone immediate-dispatch algorithm that is O(1)-competitive with respect to the maximum response time. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sungjin Im and Benjamin Moseley and Kirk Pruhs and Clifford Stein 2017 Is Part Of LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2017.51 urn:nbn:de:0030-drops-78287 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.51 eng https://creativecommons.org/licenses/by/3.0/legalcode