Bounding the Running Time of Algorithms for Scheduling and Packing Problems

DOI10.1007/978-3-642-40104-6_38zbMath1391.68041OpenAlexW103282366MaRDI QIDQ5891115

Kati Land, Felix Land, Klaus Jansen

Publication date: 12 August 2013

Published in: Lecture Notes in Computer Science (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

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (6)

Improved Lower Bounds for Graph Embedding Problems ⋮ On the optimality of exact and approximation algorithms for scheduling problems ⋮ Moderate worst-case complexity bounds for the permutation flowshop scheduling problem using inclusion-exclusion ⋮ Exact exponential algorithms for 3-machine flowshop scheduling problems ⋮ Parallel machine scheduling with minimum number of tardy jobs: approximation and exponential algorithms ⋮ Exponential time algorithms for just-in-time scheduling problems with common due date and symmetric weights

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