A PTAS for scheduling unrelated machines of few different types
DOI10.1142/S0129054118410071zbMATH Open1397.90173OpenAlexW2811361556WikidataQ129644887 ScholiaQ129644887MaRDI QIDQ5895057FDOQ5895057
Authors: Jan Clemens Gehrke, Stefan E. J. Kraft, Jakob Schikowski, Klaus Jansen 
Publication date: 24 July 2018
Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1142/s0129054118410071
Recommendations
approximation algorithmPTASpolynomial time approximation schemescheduling on unrelated machinesscheduling on unrelated machines of few different typessingle exponential in approximation ratio
Cites Work
- Title not available (Why is that?)
- An approximation algorithm for the generalized assignment problem
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
- Polynomiality for bin packing with a constant number of item types
- A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach
- Exact and Approximate Algorithms for Scheduling Nonidentical Processors
- Approximation algorithms for scheduling unrelated parallel machines
- Scheduling jobs on identical and uniform processors revisited
- An improved lower bound for rank four scheduling
- Grouping techniques for scheduling problems: simpler and faster
- An optimal rounding gives a better approximation for scheduling unrelated machines
- A faster combinatorial approximation algorithm for scheduling unrelated parallel machines
- Assigning real-time tasks on heterogeneous multiprocessors with two unrelated types of processors
- On \((1,\varepsilon)\)-restricted assignment makespan minimization
- Improved Approximation Schemes for Scheduling Unrelated Parallel Machines
- Scheduling problems on two sets of identical machines
- Minimum makespan scheduling with low rank processing times
- Partitioned EDF scheduling on a few types of unrelated multiprocessors
- Task assignment algorithms for two-type heterogeneous multiprocessors
Cited In (5)
- Improved bi-criteria approximation schemes for load balancing on unrelated machines with cost constraints
- Makespan minimization on unrelated parallel machines with a few bags
- A PTAS for scheduling unrelated machines of few different types
- Bi-Criteria Approximation Algorithms for Load Balancing on Unrelated Machines with Costs
- Randomized approximation schemes for minimizing the weighted makespan on identical parallel machines
This page was built for publication: A PTAS for scheduling unrelated machines of few different types
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5895057)
