Randomized approximation schemes for minimizing the weighted makespan on identical parallel machines
From MaRDI portal
Publication:6126818
DOI10.1007/s10878-024-01118-wOpenAlexW4393356394MaRDI QIDQ6126818
Publication date: 10 April 2024
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10878-024-01118-w
schedulingapproximation algorithmfully polynomial time approximation schemeefficient polynomial time approximation schemeweighted makespan
Cites Work
- Unnamed Item
- Approximation schemes for scheduling on parallel machines
- Minimizing average completion time in the presence of release dates
- Scheduling problems on two sets of identical machines
- Single machine scheduling with rejection to minimize the weighted makespan
- A unified framework for designing EPTAS for load balancing on parallel machines
- A PTAS for Minimizing the Total Weighted Completion Time on Identical Parallel Machines
- Integer Programming with a Fixed Number of Variables
- Convex quadratic and semidefinite programming relaxations in scheduling
- Closing the Gap for Makespan Scheduling via Sparsification Techniques
- Worst Case Bound of an LRF Schedule for the Mean Weighted Flow-Time Problem
- Algorithms for Scheduling Independent Tasks
- Best-Possible Online Algorithms for Single Machine Scheduling to Minimize the Maximum Weighted Completion Time
- Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines
- Scheduling to Minimize Total Weighted Completion Time via Time-Indexed Linear Programming Relaxations
- Weighted Completion Time Minimization for Unrelated Machines via Iterative Fair Contention Resolution
- Bounds for Certain Multiprocessing Anomalies
- Bounds on Multiprocessing Timing Anomalies
- A PTAS for Scheduling Unrelated Machines of Few Different Types
- An EPTAS for scheduling on unrelated machines of few different types
This page was built for publication: Randomized approximation schemes for minimizing the weighted makespan on identical parallel machines