Complexity and inapproximability results for parallel task scheduling and strip packing
From MaRDI portal
Publication:5915576
DOI10.1007/978-3-319-90530-3_15zbMath1434.68187arXiv1705.04587OpenAlexW2613758344WikidataQ128347510 ScholiaQ128347510MaRDI QIDQ5915576
Lars Schmarje, Sören Henning, Klaus Jansen, Malin Rau
Publication date: 28 November 2018
Published in: Theory of Computing Systems, Computer Science – Theory and Applications (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1705.04587
Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Related Items
A tight \((3/2+\varepsilon)\)-approximation for skewed strip packing, Peak demand minimization via sliced strip packing, An improved approximation algorithm for scheduling monotonic moldable tasks, On the complexity of scheduling problems with a fixed number of parallel identical machines, A Tight (3/2+ε) Approximation for Skewed Strip Packing., Improved approximation for two dimensional strip packing with polynomial bounded width, Exact solution techniques for two-dimensional cutting and packing, Closing the Gap for Pseudo-Polynomial Strip Packing
Cites Work
- Unnamed Item
- Unnamed Item
- A \((5/3+\varepsilon)\)-approximation for strip packing
- A note on the Kenyon-Remila strip-packing algorithm
- Rectangle packing with one-dimensional resource augmentation
- A 2.5 times optimal algorithm for packing in two dimensions
- Dynamic scheduling on parallel machines
- Linear-Time approximation schemes for scheduling malleable parallel tasks
- Improved approximation for two dimensional strip packing with polynomial bounded width
- Approximation and online algorithms for multidimensional bin packing: a survey
- A Near-Optimal Solution to a Two-Dimensional Cutting Stock Problem
- APPROXIMATION ALGORITHMS FOR MULTIPLE STRIP PACKING AND SCHEDULING PARALLEL JOBS IN PLATFORMS
- Improved Absolute Approximation Ratios for Two-Dimensional Packing Problems
- Complexity of Scheduling Parallel Task Systems
- Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms
- Orthogonal Packings in Two Dimensions
- Performance Bounds for Orthogonal Oriented Two-Dimensional Packing Algorithms
- A algorithm for two-dimensional packing
- Bounds for Multiprocessor Scheduling with Resource Constraints
- A Strip-Packing Algorithm with Absolute Performance Bound 2
- On approximating strip packing with a better ratio than 3/2
- Improved Pseudo-Polynomial-Time Approximation for Strip Packing
- Hardness of Approximation for Strip Packing
- Bin Packing in Multiple Dimensions: Inapproximability Results and Approximation Schemes
- Approximation Algorithms for Scheduling Parallel Jobs
- Scheduling independent multiprocessor tasks
