descriptionPublicationkeyboard_double_arrow_right Part of book or chapter of book , Article , Preprint 01 Jan 2014Embargo end date: 01 Jan 2013Publisher:Springer International PublishingJournal:Algorithmica, volume 78, pages 492-520 (issn: 0178-4617, eissn: 1432-0541,

Authors: Albers, Susanne; Hellwig, Matthias;

doi: 10.1007/978-3-319-08404-6_2 , 10.1007/s00453-016-0172-5 , 10.48550/arxiv.1304.5625

arXiv: http://arxiv.org/abs/1304.5625

Online Makespan Minimization with Parallel Schedules

- Summary
- Subjects
- Metrics

Abstract

In online makespan minimization a sequence of jobs $��= J_1,..., J_n$ has to be scheduled on $m$ identical parallel machines so as to minimize the maximum completion time of any job. We investigate the problem with an essentially new model of resource augmentation. Here, an online algorithm is allowed to build several schedules in parallel while processing $��$. At the end of the scheduling process the best schedule is selected. This model can be viewed as providing an online algorithm with extra space, which is invested to maintain multiple solutions. The setting is of particular interest in parallel processing environments where each processor can maintain a single or a small set of solutions. We develop a $(4/3+\eps)$-competitive algorithm, for any $0

Related Organizations

Keywords

FOS: Computer and information sciences, Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS)

Impact byBIP!

	citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	26
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Top 10%
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Top 10%
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Top 10%