# A greedy on-line algorithm for the k-track assignment problem

Faigle, U.
and
Kern, W.
and
Nawijn, W.M.
(1999)
*A greedy on-line algorithm for the k-track assignment problem.*
Journal of algorithms, 31
(1).
pp. 196-210.
ISSN 0196-6774

PDF
Restricted to UT campus only : Request a copy 95kB |

Abstract: | Given a collection [.] of n jobs that are represented by intervals, we seek a maximal feasible assignment of the jobs to k machines such that not more than c(M) intervals overlap pairwise on any machine M and 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 this NP-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 machine M has capacity c(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 |

Faculty: | 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 EndNote HTML Citation Reference Manager |

Repository Staff Only: item control page

Metis ID: 140560