Priority algorithms for makespan minimization in the subset model.
type: Item
instance of: scholarly article
title: Priority algorithms for makespan minimization in the subset model.
zbMATH Open document ID: 1042.68019
DOI: 10.1016/S0020-0190(02)00264-8
author: Oded Regev
published in: Information Processing Letters
publication date: 2003-01-21T00:00:00Z
review text: We continue the recent study of priority algorithms initiated by \textit{Borodin} et al. [Proc. 13th ACM-SIAM Symp. on Discrete Algorithms, 752--761 (2002)]. The definition of a priority algorithm nicely captures the idea of a ``greedy-like'' type algorithm. While priority algorithms are applicable to many optimization problems, in this paper we consider the problem of makespan minimization in scheduling in the subset model. We show that by using a fixed priority algorithm one cannot achieve a considerable improvement over the approximation ratio given by the online greedy algorithm. Namely, we present an \(\Omega(\log m/\log\log m\)) lower bound on the approximation ratio of any fixed priority algorithm where \(m\) is the number of machines.
Mathematics Subject Classification ID: 68M20
Mathematics Subject Classification ID: 68W05
zbMATH DE Number: 1856468
zbMATH Keywords: Approximation algorithms
zbMATH Keywords: Scheduling
MaRDI profile type: Publication
cites work: The Competitiveness of On-Line Assignments
cites work: Q4223058
cites work: Q4829011
cites work: Approximation algorithms for scheduling unrelated parallel machines
cites work: An approximation algorithm for the generalized assignment problem
description: scientific article; zbMATH DE number 1856468