Graham's Schedules and the Number Partition Problem

Simple item page
dc.creatorReddi, Seenu S.
dc.date2008-08-07
dc.date.accessioned2026-07-07T09:55:37Z
dc.date.available2026-07-07T09:55:37Z
dc.descriptionWe show the equivalence of the Number Partition Problem and the two processor scheduling problem. We establish a priori bounds on the completion times for the scheduling problem which are tighter than Graham's but almost on par with a posteriori bounds of Coffman and Sethi. We conclude the paper with a characterization of the asymptotic behavior of the scheduling problem which relates to the spread of the processing times and the number of jobs.
dc.description6 pages, 1 table
dc.identifierhttps://arxiv.org/abs/0808.1119
dc.identifierhttp://arxiv.org/abs/0808.1119
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/166693
dc.subjectComputational Complexity
dc.subjectDiscrete Mathematics
dc.titleGraham's Schedules and the Number Partition Problem
dc.typetext

Files

Collections

arXiv