On the optimality of exact and approximation algorithms for scheduling problems
From MaRDI portal
Recommendations
- On the optimality of approximation schemes for the classical scheduling problem
- Bounding the running time of algorithms for scheduling and packing problems
- Approximation schemes for scheduling on parallel machines
- Bounding the running time of algorithms for scheduling and packing problems
- Algorithms for solving minimax scheduling problem
Cites work
- 3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General
- A simplified NP-complete satisfiability problem
- An EPTAS for scheduling jobs on uniform processors: using an MILP relaxation with a constant number of integral variables
- An improved lower bound for rank four scheduling
- Approximation algorithms for scheduling unrelated parallel machines
- Approximation schemes for scheduling on parallel machines
- Bounding the running time of algorithms for scheduling and packing problems
- Exact and Approximate Algorithms for Scheduling Nonidentical Processors
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1507224 (Why is no real title available?)
- scientific article; zbMATH DE number 6820261 (Why is no real title available?)
- Improved Approximation Schemes for Scheduling Unrelated Parallel Machines
- Lower bounds based on the exponential time hypothesis
- Minimum makespan scheduling with low rank processing times
- On an extension of the Sort \& Search method with application to scheduling theory
- On the computational hardness based on linear fpt-reductions
- On the possibility of faster \textsc{SAT} algorithms
- Parameterized and approximation results for scheduling with a low rank processing time matrix
- Scheduling and fixed-parameter tractability
- There is no EPTAS for two-dimensional knapsack
- Which problems have strongly exponential complexity?
Cited in
(54)- Tighter approximation bounds for LPT scheduling in two special cases
- Optimization of template-driven scheduling mechanisms: Regularity measures and computational techniques
- Special issue: Efficient scheduling algorithms. 6 papers from ESA 2000 and APPROX 2000, both in Saarbrücken, Germany, September 5--8, 2000
- Efficient algorithms for a scheduling problem and its applications to illicit drug market crackdowns
- Optimal randomized scheduling by replacement
- Exact and approximation algorithms for the operational fixed interval scheduling problem
- Extending Graham's result on scheduling to other heuristics
- Exact and heuristic algorithms for the just-in-time scheduling problem in a batch processing system
- An exact algorithm for the bi-objective timing problem
- Exact exponential algorithms for 3-machine flowshop scheduling problems
- Approximation algorithms for the workload partition problem and applications to scheduling with variable processing times
- A probe-based algorithm for piecewise linear optimization in scheduling
- Ten notes on equal-processing-time scheduling: at the frontiers of solvability in polynomial time
- An algebraic geometry algorithm for scheduling in presence of setups and correlated demands
- A greedy algorithm for the solution of the classical NP-hard scheduling problem of minimizing the total delay
- Moderate exponential-time algorithms for scheduling problems
- Scheduling lower bounds via AND subset sum
- Optimal algorithms for scheduling under time-of-use tariffs
- Improved approximation algorithms for the combination problem of parallel machine scheduling and path
- A unified framework for designing EPTAS for load balancing on parallel machines
- On the extension complexity of scheduling polytopes
- A survey of methods for the solution of problems of scheduling theory
- An experimental study of LP-based approximation algorithms for scheduling problems
- scientific article; zbMATH DE number 6378894 (Why is no real title available?)
- scientific article; zbMATH DE number 444983 (Why is no real title available?)
- Reducing the solution space of optimal task scheduling
- Closing the gap for makespan scheduling via sparsification techniques
- Tighter Approximation Bounds for LPT Scheduling in Two Special Cases
- scientific article; zbMATH DE number 3908144 (Why is no real title available?)
- On Approximation Algorithms for Two-Stage Scheduling Problems
- scientific article; zbMATH DE number 850325 (Why is no real title available?)
- The Complexity of Scheduling for p-Norms of Flow and Stretch
- scientific article; zbMATH DE number 7529517 (Why is no real title available?)
- Approximately Supermodular Scheduling Subject to Matroid Constraints
- scientific article; zbMATH DE number 7267489 (Why is no real title available?)
- Time optimal linear schedules for algorithms with uniform dependencies
- On the optimality of approximation schemes for the classical scheduling problem
- An empirical analysis of algorithms for partially Clairvoyant scheduling
- scientific article; zbMATH DE number 6469210 (Why is no real title available?)
- Bounding the running time of algorithms for scheduling and packing problems
- Bounding the running time of algorithms for scheduling and packing problems
- Approximation algorithms for scheduling with reservations
- Complexity of Scheduling Few Types of Jobs on Related and Unrelated Machines
- On the complexity of scheduling problems with a fixed number of parallel identical machines
- On the computational complexity of (maximum) shift class scheduling
- A gap-ETH-tight approximation scheme for Euclidean TSP
- New support size bounds for integer programming, applied to makespan minimization on uniformly related machines
- Complexity of scheduling few types of jobs on related and unrelated machines
- Additive approximation schemes for load balancing problems
- Efficient approximation schemes for scheduling on a stochastic number of machines
- New algorithm for combinatorial n-folds and applications
- Exact algorithms for allocation problems
- Necessary and sufficient conditions of optimality for some classical scheduling problems
- Scheduling and fixed-parameter tractability
This page was built for publication: On the optimality of exact and approximation algorithms for scheduling problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1635503)
