Bounding the Running Time of Algorithms for Scheduling and Packing Problems

DOI10.1137/140952636zbMath1336.68100OpenAlexW2280590529MaRDI QIDQ5890508

Kati Land, Felix Land, Klaus Jansen

Publication date: 4 March 2016

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://macau.uni-kiel.de/receive/macau_mods_00001780

zbMATH Keywords

schedulingpackinglower boundsexact algorithmsexponential time hypothesis

Mathematics Subject Classification ID

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 (6)

On the fine-grained parameterized complexity of partial scheduling to minimize the makespan ⋮ On the complexity of scheduling problems with a fixed number of parallel identical machines ⋮ Non-preemptive scheduling in a smart grid model and its implications on machine minimization ⋮ Unnamed Item ⋮ Four decades of research on the open-shop scheduling problem to minimize the makespan ⋮ Complexity of Grundy coloring and its variants

Uses Software

• Knapsack

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Exact exponential algorithms.
• There is no EPTAS for two-dimensional knapsack
• A simplified NP-complete satisfiability problem
• Complexity theory. Limits of the efficiency of algorithms
• Computing optimal preemptive schedules for parallel tasks: linear programming approaches
• Approximation algorithms for knapsack problems with cardinality constraints
• Which problems have strongly exponential complexity?
• On the complexity of multiprocessor task scheduling
• Bin packing with fixed number of bins revisited
• Parametrized complexity theory.
• On the computational hardness based on linear fpt-reductions
• Optimal two- and three-stage production schedules with setup times included
• Non-Approximability Results for Scheduling Problems with Minsum Criteria
• A Fast Approximation Scheme for the Multiple Knapsack Problem
• A Dynamic Programming Approach to Sequencing Problems
• Scheduling Multiprocessor Tasks to Minimize Schedule Length
• Complexity of Scheduling Parallel Task Systems
• Minimizing Mean Flow Time in Two-Machine Open Shops and Flow Shops
• Computing Partitions with Applications to the Knapsack Problem
• Open Shop Scheduling to Minimize Finish Time
• Complexity of Scheduling under Precedence Constraints
• Flowshop and Jobshop Schedules: Complexity and Approximation
• The Complexity of Flowshop and Jobshop Scheduling
• Short Shop Schedules
• On the optimality of approximation schemes for the classical scheduling problem
• Approximation Algorithms for Scheduling Parallel Jobs
• On the complexity of \(k\)-SAT

This page was built for publication: Bounding the Running Time of Algorithms for Scheduling and Packing Problems