New Tools for Peak Memory Scheduling
summary
Shows that a node-sum model (nodes with positive/negative weights) plus a formal dominant schedule notion lets an arbitrary DAG be linearized by replacing isolated subgraphs with their dominant schedules, and proves a dominant schedule always exists (constructively, but not in polynomial time). Proves NP-hardness on starborescence/pumpkin families, reduces series–parallel graphs to caduceus instances solvable by trying D! guesses over high-degree orderings, and notes rematerialization helps but can blow up schedule length (PSPACE‑hard).
AI-written summary · about
chapters (12)
- 0:00Peak memory scheduling intro
- 2:08Problem statement
- 3:32Graph model and memory
- 7:04Pebbling games hardness
- 14:36Node sum dominance
- 18:10Dominance formalization
- 23:45Isolated subgraphs linearization
- 24:49Series parallel graphs
- 26:56Starborescence graphs
- 28:42Caduceus graphs reductions
- 31:09Solving caduceus graphs
- 31:51Q&A
related talks
26mLower Bounds on the Running Time for Scheduling and Packing Problems
40mResilience of 3-Majority Dynamics to Non-Uniform Schedulers
31mNew Unconditional Lower Bounds for Algorithms and Enumeration Problems
29mSubexponential Parameterized Complexity of Completion Problems: Survey of the Upper Bounds
27mOn the Subexponential Time Complexity of the CSP
41mOn counting subgraphs and why counting seeds makes more sense (if one thinks about it clearly)
29mColor Coding-Related Techniques
38mLower Bounds on the Space Complexity of Dynamic Programming