New approximation bounds for LPT scheduling
From MaRDI portal
Publication:2379930
DOI10.1007/S00453-008-9224-9zbMATH Open1191.68868OpenAlexW1978392075MaRDI QIDQ2379930FDOQ2379930
Authors: Annamária Kovács 
Publication date: 23 March 2010
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-008-9224-9
Recommendations
Cites Work
- Title not available (Why is that?)
- A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach
- Bounds for Certain Multiprocessing Anomalies
- Bounds on Multiprocessing Timing Anomalies
- Parametric bounds for LPT scheduling on uniform processors
- Scheduling Independent Tasks on Uniform Processors
- Tighter Bounds for LPT Scheduling on Uniform 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
- Approximation schemes for scheduling on uniformly related and identical parallel machines
- Tighter approximation bounds for LPT scheduling in two special cases
Cited In (22)
- An experimental study of LP-based approximation algorithms for scheduling problems
- Approximate strong equilibria in job scheduling games with two uniformly related machines
- A survey on makespan minimization in semi-online environments
- Tighter approximation bounds for LPT scheduling in two special cases
- A note on LPT scheduling
- Coordination mechanisms with hybrid local policies
- Inefficiency of Nash equilibria with parallel processing policy
- The longest processing time rule for identical parallel machines revisited
- A coordination mechanism for a scheduling game with uniform-batching machines
- Bounds on delay start LPT algorithm for scheduling on two identical machines in the \(l_p\) norm
- Worst-case analysis of LPT scheduling on a small number of non-identical processors
- Scheduling with uncertain processing times in mixed-criticality systems
- The exact LPT-bound for maximizing the minimum completion time
- Related machine scheduling with machine speeds satisfying linear constraints
- Coordination mechanisms for parallel machine scheduling
- A note on the Coffman-Sethi bound for LPT scheduling
- Tighter Approximation Bounds for LPT Scheduling in Two Special Cases
- LP rounding and combinatorial algorithms for minimizing active and busy time
- A note on posterior tight worst-case bounds for longest processing time schedules
- Tighter Bounds for LPT Scheduling on Uniform Processors
- Tight approximation bounds for the LPT rule applied to identical parallel machines with small jobs
- Parallel solutions for preemptive makespan scheduling on two identical machines
This page was built for publication: New approximation bounds for LPT scheduling
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2379930)
