File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1109/FOCS.2007.4389530
- Scopus: eid_2-s2.0-46749116805
- Find via
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
Conference Paper: Non-preemptive min-sum scheduling with resource augmentation
Title | Non-preemptive min-sum scheduling with resource augmentation |
---|---|
Authors | |
Issue Date | 2007 |
Citation | Proceedings - Annual Ieee Symposium On Foundations Of Computer Science, Focs, 2007, p. 614-624 How to Cite? |
Abstract | We 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 Identifier | http://hdl.handle.net/10722/151917 |
ISSN | 2020 SCImago Journal Rankings: 2.949 |
References |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Bansal, N | en_US |
dc.contributor.author | Chan, HL | en_US |
dc.contributor.author | Khandekar, R | en_US |
dc.contributor.author | Pruhs, K | en_US |
dc.contributor.author | Schieber, B | en_US |
dc.contributor.author | Stein, C | en_US |
dc.date.accessioned | 2012-06-26T06:30:47Z | - |
dc.date.available | 2012-06-26T06:30:47Z | - |
dc.date.issued | 2007 | en_US |
dc.identifier.citation | Proceedings - Annual Ieee Symposium On Foundations Of Computer Science, Focs, 2007, p. 614-624 | en_US |
dc.identifier.issn | 0272-5428 | en_US |
dc.identifier.uri | http://hdl.handle.net/10722/151917 | - |
dc.description.abstract | We 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.language | eng | en_US |
dc.relation.ispartof | Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS | en_US |
dc.title | Non-preemptive min-sum scheduling with resource augmentation | en_US |
dc.type | Conference_Paper | en_US |
dc.identifier.email | Chan, HL:hlchan@cs.hku.hk | en_US |
dc.identifier.authority | Chan, HL=rp01310 | en_US |
dc.description.nature | link_to_subscribed_fulltext | en_US |
dc.identifier.doi | 10.1109/FOCS.2007.4389530 | en_US |
dc.identifier.scopus | eid_2-s2.0-46749116805 | en_US |
dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-46749116805&selection=ref&src=s&origin=recordpage | en_US |
dc.identifier.spage | 614 | en_US |
dc.identifier.epage | 624 | en_US |
dc.identifier.scopusauthorid | Bansal, N=7102714084 | en_US |
dc.identifier.scopusauthorid | Chan, HL=7403402384 | en_US |
dc.identifier.scopusauthorid | Khandekar, R=23034886100 | en_US |
dc.identifier.scopusauthorid | Pruhs, K=6603866438 | en_US |
dc.identifier.scopusauthorid | Schieber, B=35792434800 | en_US |
dc.identifier.scopusauthorid | Stein, C=7202589565 | en_US |
dc.identifier.issnl | 0272-5428 | - |