Priority algorithms for makespan minimization in the subset model.

DOI10.1016/S0020-0190(02)00264-8MaRDI QIDQ1853127zbMATH OpenFDO

Authors Oded Regev

Publication date 21 January 2003

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0020-0190(02)00264-8

zbMATH Keywords

Approximation algorithmsScheduling

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Nonnumerical algorithms (68W05)

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.

Recommendations

• scientific article; zbMATH DE number 2119736
• Randomized priority algorithms
• Hierarchies for classes of priority algorithms for job scheduling
• (Incremental) priority algorithms
• Approximation and Online Algorithms

Cites work

• An approximation algorithm for the generalized assignment problem
• Approximation algorithms for scheduling unrelated parallel machines
• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• scientific article; zbMATH DE number 2119736 (Why is no real title available?)
• The Competitiveness of On-Line Assignments

Cited in

(12)

• Priority algorithms for the subset-sum problem
• (Incremental) priority algorithms
• On the Structure of Optimal Greedy Computation (for Job Scheduling)
• Priority Algorithms for the Subset-Sum Problem
• Toward a model for backtracking and dynamic programming
• scientific article; zbMATH DE number 2119736 (Why is no real title available?)
• Limitations of incremental dynamic programming
• A stronger model of dynamic programming algorithms
• Advice complexity of adaptive priority algorithms
• Hierarchies for classes of priority algorithms for job scheduling
• Characterizing sets of jobs that admit optimal greedy-like algorithms
• Randomized priority algorithms

This page was built for publication: Priority algorithms for makespan minimization in the subset model.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1853127)