A tight linear time \(\frac{13}{12}\)-approximation algorithm for the \(P2 || C_{\max}\) problem

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

zbMATH Keywords

approximationmakespanmathematical programmingLPT ruletwo identical parallel machines scheduling

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Deterministic scheduling theory in operations research (90B35) Approximation algorithms (68W25)

Related Items (2)

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

This page was built for publication: A tight linear time \(\frac{13}{12}\)-approximation algorithm for the \(P2 || C_{\max}\) problem