Moderately exponential approximation for makespan minimization on related machines

DOI10.1016/J.TCS.2013.03.020MaRDI QIDQ392019zbMATH OpenOpenAlexFDO

Authors Marin Bougeret, Pierre-Francois Dutot, Denis Trystram

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

makespanmoderately exponential approximationoracle guessrelated machinesscheduling

Mathematics Subject Classification ID

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

Recommendations

• An efficient approximation algorithm for minimizing makespan on uniformly related machines.
• scientific article; zbMATH DE number 1187166
• An optimal rounding gives a better approximation for scheduling unrelated machines
• Approximation algorithms for scheduling unrelated parallel machines
• Improved approximation schemes for scheduling unrelated parallel machines

Cites work

• A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach
• An EPTAS for scheduling jobs on uniform processors: using an MILP relaxation with a constant number of integral variables
• Approximation algorithms for scheduling unrelated parallel machines
• Bounds for LPT Schedules on Uniform Processors
• Bounds for Multifit Scheduling on Uniform Processors
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Efficient Approximation of Combinatorial Problems by Moderately Exponential Algorithms
• Exact and Approximate Algorithms for Scheduling Nonidentical Processors
• Grouping techniques for scheduling problems: simpler and faster
• scientific article; zbMATH DE number 1953201 (Why is no real title available?)
• Tighter bound for MULTIFIT scheduling on uniform processors

Cited in

(1)

• An efficient approximation algorithm for minimizing makespan on uniformly related machines.

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q392019)