Paper Info
Title
The optimality of the online greedy algorithm in carpool and chairman assignment problems
Abstract
We study several classes of related scheduling problems including the carpool problem, its generalization to arbitrary inputs and the chairman assignment problem. We derive both lower and upper bounds for online algorithms solving these problems. We show that the greedy algorithm is optimal among online algorithms for the chairman assignment problem and the generalized carpool problem. We also consider geometric versions of these problems and show how the bounds adapt to these cases.
Year
DOI
Venue
2011
10.1145/1978782.1978792
ACM Transactions on Algorithms
Keywords
Field
DocType
online greedy algorithm,online algorithm,geometric version,carpool problem,greedy algorithm,arbitrary input,chairman assignment problem,generalized carpool problem,upper bound,related scheduling problem,scheduling problem,assignment problem
Online algorithm,Mathematical optimization,Combinatorics,Computer science,Scheduling (computing),Carpool,Generalized assignment problem,Greedy algorithm,Assignment problem
Journal
Volume
Issue
ISSN
7
3
1549-6325
Citations 
PageRank 
References 
5
0.64
7
Authors
5
Name
Order
Citations
PageRank
Don Coppersmith14370976.70
Tomasz Nowicki2453.61
Giuseppe Paleologo3501.82
C. P. Tresser4121.99
Chai Wah Wu533067.62