Moderately exponential approximation for makespan minimization on related machines

DOI10.1016/j.tcs.2013.03.020zbMath1359.90040OpenAlexW1976329942MaRDI QIDQ392019

Pierre-Francois Dutot, Denis Trystram, Marin Bougeret

Publication date: 13 January 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2013.03.020

zbMATH Keywords

schedulingmakespanrelated machinesmoderately exponential approximationoracle guess

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• Approximation algorithms for scheduling unrelated parallel machines
• Grouping techniques for scheduling problems: simpler and faster
• Tighter bound for MULTIFIT scheduling on uniform processors
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Efficient Approximation of Combinatorial Problems by Moderately Exponential Algorithms
• Bounds for Multifit Scheduling on Uniform Processors
• A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach
• Exact and Approximate Algorithms for Scheduling Nonidentical Processors
• Bounds for LPT Schedules on Uniform Processors
• An EPTAS for Scheduling Jobs on Uniform Processors: Using an MILP Relaxation with a Constant Number of Integral Variables

This page was built for publication: Moderately exponential approximation for makespan minimization on related machines