2-approximation algorithm for a generalization of scheduling on unrelated parallel machines

DOI10.1016/J.IPL.2018.07.005MaRDI QIDQ1799571zbMATH OpenOpenAlexFDO

Authors Yossi Azar, Jaya Prakash Champati, Ben Liang

Publication date 19 October 2018

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2018.07.005

zbMATH Keywords

approximation algorithmsschedulingmakespanunrelated machinesopen cycles

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Approximation algorithms (68W25)

Recommendations

• Approximate algorithms for unrelated machine scheduling to minimize makespan
• Improved approximation schemes for scheduling unrelated parallel machines
• Approximation schemes for scheduling and covering on unrelated machines
• A faster combinatorial approximation algorithm for scheduling unrelated parallel machines
• Automata, Languages and Programming

Cites work

• Algorithm Theory - SWAT 2004
• Algorithms for Scheduling Tasks on Unrelated Processors
• All-norm approximation algorithms
• Analysis of a linear programming heuristic for scheduling unrelated parallel machines
• Approximation algorithms for scheduling unrelated parallel machines
• Exact and Approximate Algorithms for Scheduling Nonidentical Processors
• Network flows. Theory, algorithms, and applications.
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey

Cited in

(2)

• A faster combinatorial approximation algorithm for scheduling unrelated parallel machines
• scientific article; zbMATH DE number 4113979 (Why is no real title available?)

This page was built for publication: 2-approximation algorithm for a generalization of scheduling on unrelated parallel machines

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