File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Online Makespan Minimization: The Power of Restart

TitleOnline Makespan Minimization: The Power of Restart
Authors
KeywordsOnline Scheduling
Makespan Minimization
Identical Machines
Issue Date2018
PublisherSchloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl Publishing.
Citation
21st International Workshop, APPROX 2018, and 22nd International Workshop, RANDOM 2018, Princeton, USA, 20-22 August 2018. In Blais, E ... et al (eds.), Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018), abstract no. 14:1-19 How to Cite?
AbstractWe consider the online makespan minimization problem on identical machines. Chen and Vestjens (ORL 1997) show that the largest processing time first (LPT) algorithm is 1.5-competitive. For the special case of two machines, Noga and Seiden (TCS 2001) introduce the SLEEPY algorithm that achieves a competitive ratio of (5−5 – √ )/2≈1.382 , matching the lower bound by Chen and Vestjens (ORL 1997). Furthermore, Noga and Seiden note that in many applications one can kill a job and restart it later, and they leave an open problem whether algorithms with restart can obtain better competitive ratios. We resolve this long-standing open problem on the positive end. Our algorithm has a natural rule for killing a processing job: a newly-arrived job replaces the smallest processing job if 1) the new job is larger than other pending jobs, 2) the new job is much larger than the processing one, and 3) the processed portion is small relative to the size of the new job. With appropriate choice of parameters, we show that our algorithm improves the 1.5 competitive ratio for the general case, and the 1.382 competitive ratio for the two-machine case.
DescriptionThe 21st International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX'2018), and the 22nd International Conference on Randomization and Computation (RANDOM'2018)
Persistent Identifierhttp://hdl.handle.net/10722/260347
ISBN
Series/Report no.Leibniz International Proceedings in Informatics (LIPIcs) ; v. 116

 

DC FieldValueLanguage
dc.contributor.authorHuang, Z-
dc.contributor.authorKang, N-
dc.contributor.authorTang, Z-
dc.contributor.authorWu, X-
dc.contributor.authorZhang, Y-
dc.date.accessioned2018-09-14T08:40:11Z-
dc.date.available2018-09-14T08:40:11Z-
dc.date.issued2018-
dc.identifier.citation21st International Workshop, APPROX 2018, and 22nd International Workshop, RANDOM 2018, Princeton, USA, 20-22 August 2018. In Blais, E ... et al (eds.), Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018), abstract no. 14:1-19-
dc.identifier.isbn978-3-95977-085-9-
dc.identifier.urihttp://hdl.handle.net/10722/260347-
dc.descriptionThe 21st International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX'2018), and the 22nd International Conference on Randomization and Computation (RANDOM'2018)-
dc.description.abstractWe consider the online makespan minimization problem on identical machines. Chen and Vestjens (ORL 1997) show that the largest processing time first (LPT) algorithm is 1.5-competitive. For the special case of two machines, Noga and Seiden (TCS 2001) introduce the SLEEPY algorithm that achieves a competitive ratio of (5−5 – √ )/2≈1.382 , matching the lower bound by Chen and Vestjens (ORL 1997). Furthermore, Noga and Seiden note that in many applications one can kill a job and restart it later, and they leave an open problem whether algorithms with restart can obtain better competitive ratios. We resolve this long-standing open problem on the positive end. Our algorithm has a natural rule for killing a processing job: a newly-arrived job replaces the smallest processing job if 1) the new job is larger than other pending jobs, 2) the new job is much larger than the processing one, and 3) the processed portion is small relative to the size of the new job. With appropriate choice of parameters, we show that our algorithm improves the 1.5 competitive ratio for the general case, and the 1.382 competitive ratio for the two-machine case.-
dc.languageeng-
dc.publisherSchloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl Publishing.-
dc.relation.ispartofProceedings of the 21st International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX/RANDOM 2018)-
dc.relation.ispartofseriesLeibniz International Proceedings in Informatics (LIPIcs) ; v. 116-
dc.subjectOnline Scheduling-
dc.subjectMakespan Minimization-
dc.subjectIdentical Machines-
dc.titleOnline Makespan Minimization: The Power of Restart-
dc.typeConference_Paper-
dc.identifier.emailHuang, Z: zhiyi@cs.hku.hk-
dc.identifier.authorityHuang, Z=rp01804-
dc.identifier.doi10.4230/LIPIcs.APPROX-RANDOM.2018.14-
dc.identifier.hkuros290751-
dc.identifier.spage14:1-
dc.identifier.epage14:19-
dc.publisher.placeDagstuhl, Germany-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats