Minimum makespan scheduling with low rank processing times

DOI10.1137/1.9781611973105.67MaRDI QIDQ5741775zbMATH OpenOpenAlexFDO

Authors Aditya Bhaskara, Ravishankar Krishnaswamy, Kunal Talwar, Udi Wieder

Publication date 15 May 2019

Published in Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/1.9781611973105.67

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Deterministic scheduling theory in operations research (90B35)

Recommendations

• An improved lower bound for rank four scheduling
• Parameterized and approximation results for scheduling with a low rank processing time matrix
• Approximation algorithms for scheduling unrelated parallel machines
• On the optimality of approximation schemes for the classical scheduling problem
• Improved approximation schemes for scheduling unrelated parallel machines

Cited in

(8)

• On the optimality of exact and approximation algorithms for scheduling problems
• An improved lower bound for rank four scheduling
• Parameterized and approximation results for scheduling with a low rank processing time matrix
• A PTAS for scheduling unrelated machines of few different types
• Complexity of Scheduling Few Types of Jobs on Related and Unrelated Machines
• (In-)approximability results for interval, resource restricted, and low rank scheduling
• Complexity of scheduling few types of jobs on related and unrelated machines
• Scheduling two types of jobs with minimum makespan

This page was built for publication: Minimum makespan scheduling with low rank processing times

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