Priority algorithms for makespan minimization in the subset model. (Q1853127): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: The Competitiveness of On-Line Assignments / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4223058 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4829011 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Approximation algorithms for scheduling unrelated parallel machines / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: An approximation algorithm for the generalized assignment problem / rank | |||
Normal rank |
Latest revision as of 11:22, 5 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Priority algorithms for makespan minimization in the subset model. |
scientific article |
Statements
Priority algorithms for makespan minimization in the subset model. (English)
0 references
21 January 2003
0 references
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.
0 references
Approximation algorithms
0 references
Scheduling
0 references