Sublinear time approximation schemes for makespan minimization on parallel machines
From MaRDI portal
Cites work
- A (1+epsilon)-approximation for makespan scheduling with precedence constraints using LP hierarchies
- A survey on how the structure of precedence constraints may change the complexity class of scheduling problems
- Algorithms for Scheduling Independent Tasks
- Approximating Average Parameters of Graphs
- Approximating the Minimum Spanning Tree Weight in Sublinear Time
- Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time
- Bounds for Certain Multiprocessing Anomalies
- Bounds on Multiprocessing Timing Anomalies
- Complexity of Scheduling under Precedence Constraints
- Estimating the weight of metric minimum spanning trees in sublinear-time
- Hardness of precedence constrained scheduling on identical machines
- scientific article; zbMATH DE number 1615273 (Why is no real title available?)
- scientific article; zbMATH DE number 819814 (Why is no real title available?)
- NP-complete scheduling problems
- On Sums of Independent Random Variables with Unbounded Variance and Estimating the Average Degree in a Graph
- Optimal Long Code Test with One Free Bit
- Optimal scheduling for two-processor systems
- Property testing and its connection to learning and approximation
- Scheduling
- Scheduling precedence graphs of bounded height
- Sublinear Geometric Algorithms
- Sublinear time width-bounded separators and their application to the protein side-chain packing problem
This page was built for publication: Sublinear time approximation schemes for makespan minimization on parallel machines
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6949793)
