Tighter approximation bounds for LPT scheduling in two special cases

DOI10.1016/J.JDA.2008.11.004zbMath1164.90014OpenAlexW2070440720MaRDI QIDQ1026246

Annamária Kovács

Publication date: 24 June 2009

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2008.11.004

zbMATH Keywords

approximation algorithmsLPTmonotone algorithmsscheduling mechanismsrelated machine scheduling

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Related Items (6)

A survey on makespan minimization in semi-online environments ⋮ New approximation bounds for LPT scheduling ⋮ Worst-case analysis of LPT scheduling on a small number of non-identical processors ⋮ The price of anarchy on uniformly related machines revisited ⋮ On the optimality of list scheduling for online uniform machines scheduling ⋮ A Unified Approach to Truthful Scheduling on Related Machines

Cites Work

• Unnamed Item
• Unnamed Item
• Approximation schemes for scheduling on uniformly related and identical parallel machines
• Scheduling Independent Tasks on Uniform Processors
• A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach
• Tighter Bounds for LPT Scheduling on Uniform Processors
• Bounds for List Schedules on Uniform Processors
• Optimal Auction Design
• Exact and Approximate Algorithms for Scheduling Nonidentical Processors
• Bounds for LPT Schedules on Uniform Processors
• An Application of Bin-Packing to Multiprocessor Scheduling
• A Parametric Worst Case Analysis of the LPT Heuristic for Two Uniform Machines
• An On-Line Algorithm for Some Uniform Processor Scheduling
• STACS 2004
• Algorithms – ESA 2005
• Bounds on Multiprocessing Timing Anomalies

This page was built for publication: Tighter approximation bounds for LPT scheduling in two special cases