File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Non-preemptive min-sum scheduling with resource augmentation

TitleNon-preemptive min-sum scheduling with resource augmentation
Authors
Issue Date2007
Citation
Proceedings - Annual Ieee Symposium On Foundations Of Computer Science, Focs, 2007, p. 614-624 How to Cite?
AbstractWe give the first O(1)-speed O(1)-approximation polynomial-time algorithms for several nonpreemptive minsum scheduling problems where jobs arrive over time and must be processed on one machine. More precisely, we give the first O(1)-speed O(1)-approximations for the non-preemptive scheduling problems 1 | r j | Σ w jF j (weighted flow time), | r j | Σ T j (total tardiness), the broadcast version, of 1 | r j | Σ w jF j, an O(1)-speed, 1-approximation for 1 | r j | ΣŪ j (throughput maximization), and an O(1)-machine, O(1)-speed O(1)-approximation for 1 | r j | Σ w j T j (weighted tardiness). Our main, contribution is an integer programming formulation whose relaxation is sufficiently close to the integer optimum, and which can be transformed to a schedule on a faster machine. © 2007 IEEE.
Persistent Identifierhttp://hdl.handle.net/10722/151917
ISSN
References

 

DC FieldValueLanguage
dc.contributor.authorBansal, Nen_US
dc.contributor.authorChan, HLen_US
dc.contributor.authorKhandekar, Ren_US
dc.contributor.authorPruhs, Ken_US
dc.contributor.authorSchieber, Ben_US
dc.contributor.authorStein, Cen_US
dc.date.accessioned2012-06-26T06:30:47Z-
dc.date.available2012-06-26T06:30:47Z-
dc.date.issued2007en_US
dc.identifier.citationProceedings - Annual Ieee Symposium On Foundations Of Computer Science, Focs, 2007, p. 614-624en_US
dc.identifier.issn0272-5428en_US
dc.identifier.urihttp://hdl.handle.net/10722/151917-
dc.description.abstractWe give the first O(1)-speed O(1)-approximation polynomial-time algorithms for several nonpreemptive minsum scheduling problems where jobs arrive over time and must be processed on one machine. More precisely, we give the first O(1)-speed O(1)-approximations for the non-preemptive scheduling problems 1 | r j | Σ w jF j (weighted flow time), | r j | Σ T j (total tardiness), the broadcast version, of 1 | r j | Σ w jF j, an O(1)-speed, 1-approximation for 1 | r j | ΣŪ j (throughput maximization), and an O(1)-machine, O(1)-speed O(1)-approximation for 1 | r j | Σ w j T j (weighted tardiness). Our main, contribution is an integer programming formulation whose relaxation is sufficiently close to the integer optimum, and which can be transformed to a schedule on a faster machine. © 2007 IEEE.en_US
dc.languageengen_US
dc.relation.ispartofProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCSen_US
dc.titleNon-preemptive min-sum scheduling with resource augmentationen_US
dc.typeConference_Paperen_US
dc.identifier.emailChan, HL:hlchan@cs.hku.hken_US
dc.identifier.authorityChan, HL=rp01310en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.doi10.1109/FOCS.2007.4389530en_US
dc.identifier.scopuseid_2-s2.0-46749116805en_US
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-46749116805&selection=ref&src=s&origin=recordpageen_US
dc.identifier.spage614en_US
dc.identifier.epage624en_US
dc.identifier.scopusauthoridBansal, N=7102714084en_US
dc.identifier.scopusauthoridChan, HL=7403402384en_US
dc.identifier.scopusauthoridKhandekar, R=23034886100en_US
dc.identifier.scopusauthoridPruhs, K=6603866438en_US
dc.identifier.scopusauthoridSchieber, B=35792434800en_US
dc.identifier.scopusauthoridStein, C=7202589565en_US

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats