A Greedy On-Line Algorithm for thek-Track Assignment Problem


Faigle, U. and Kern, W. and Nawijn, W.M. (1999) A Greedy On-Line Algorithm for thek-Track Assignment Problem. Journal of Algorithms, 31 (1). pp. 196-210. ISSN 0196-6774

[img] PDF
Restricted to UT campus only
: Request a copy
Abstract:Given a collection [.] ofnjobs that are represented by intervals, we seek a maximal feasible assignment of the jobs tokmachines such that not more thanc(M) intervals overlap pairwise on any machineMand that a job is only assigned to a machine if it fits into one of several prescribed time windows for that machine. We analyze an on-line version of thisNP-complete problem and exhibit an algorithm that achieves at least half of the (theoretical) optimum. In a more detailed analysis, we bound the performance of our algorithm by an additive term that only depends on the time window structure of the machines (but not on the number of jobs). In the case where each machineMhas capacityc(M) = 1, our bound implies that our algorithm loses at mostk − 1 jobs relative to the optimum. We show by an explicit construction that the bound is tight for greedy on-line algorithms.
Item Type:Article
Copyright:© 1999 Elsevier
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/74008
Official URL:http://dx.doi.org/10.1006/jagm.1998.1001
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page

Metis ID: 140560