research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Article
Entered by:
TitleScheduling to maximize participation
Bibtex cite IDRACTI-RU1-2008-73
Journal Theoretical Computer Science (TCS)
Year published 2008
Volume 402
Number 2-3
Pages 142-155
DOI science?_ob=articleurl&_udi=b6v1g-4sd6spb-4&_user=742574&_rdoc=1&_fmt=&_orig=search&_sort=d&view=c&_acct=c000059659&_version=1&_urlversion=0&_userid=742574&md5=29da4b93bd38eb663699533f108841ba
Keywords Scheduling; Nash equilibria; Approximation and online algorithms; Competitive analysis
We study a problem of scheduling client requests to servers. Each client has a particular latency requirement at each server and may choose either to be assigned to some server in order to get serviced provided that her latency requirement is met, or not to participate in the assignment at all. From a global perspective, in order to optimize the performance of such a system, one would aim to maximize the number of clients that participate in the assignment. However, clients may behave selfishly in the sense that, each of them simply aims to participate in an assignment and get serviced by some server where her latency requirement is met with no regard to overall system performance. We model this selfish behavior as a strategic game, show how to compute pure Nash equilibria efficiently, and assess the impact of selfishness on system performance. We also show that the problem of optimizing performance is computationally hard to solve, even in a coordinated way, and present efficient approximation and online algorithms.
Caragiannis, Ioannis
Kaklamanis, Christos
Kanellopoulos, Panagiotis
Papaioannou, Evi
sched.pdf (main file)
Publication ID534