A tight linear time \(\frac{13}{12}\)-approximation algorithm for the \(P2 || C_{\max}\) problem
From MaRDI portal
Publication:2424829
DOI10.1007/s10878-019-00399-wzbMath1423.90087OpenAlexW2921367668MaRDI QIDQ2424829
Vincent T'kindt, Rosario Scatamacchia, Frederico Della Croce
Publication date: 25 June 2019
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10878-019-00399-w
Numerical mathematical programming methods (65K05) Deterministic scheduling theory in operations research (90B35) Approximation algorithms (68W25)
Related Items
A characterization of optimal multiprocessor schedules and new dominance rules, Tight approximation bounds for the LPT rule applied to identical parallel machines with small jobs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Multiprocessor scheduling: Combining LPT and MULTIFIT
- Approximation schemes for scheduling on parallel machines
- Time bounds for selection
- Approximation results for the incremental knapsack problem
- A note on the Coffman-Sethi bound for LPT scheduling
- A note on minimizing the sum of squares of machine completion times on two identical parallel machines
- An improved delayed-start LPT algorithm for a partition problem on two identical parallel machines
- Algorithms for Scheduling Independent Tasks
- An Application of Bin-Packing to Multiprocessor Scheduling
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
- A Parametric Worst Case Analysis of the LPT Heuristic for Two Uniform Machines
- Beating ratio 0.5 for weighted oblivious matching problems
- An ILP-based Proof System for the Crossing Number Problem
- An EPTAS for Scheduling Jobs on Uniform Processors: Using an MILP Relaxation with a Constant Number of Integral Variables
- Bounds on Multiprocessing Timing Anomalies
- A note on LPT scheduling
