Scheduling partially ordered jobs faster than \(2^n\)
From MaRDI portal
Publication:528859
DOI10.1007/s00453-012-9694-7zbMath1360.90124MaRDI QIDQ528859
Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk
Publication date: 17 May 2017
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-012-9694-7
scheduling; dynamic programming; \(2^n\)-barrier; moderately-exponential algorithms; partially ordered jobs
68Q25: Analysis of algorithms and problem complexity
90B35: Deterministic scheduling theory in operations research
90C39: Dynamic programming