Lower Bounds on the Running Time for Scheduling and Packing Problems
summary
ETH-based reductions give concrete running-time barriers: a linear reduction from 3-SAT to Subset Sum produces 8m items and rules out 2^{o(n)} algorithms under ETH, and because the numeric encoding is O(m^2) it also rules out 2^{o(sqrt{N})} in the input size. For scheduling and packing: identical-machine scheduling yields lower bounds with the number of machines inside the exponent (exponent grows like roughly sqrt(M) in some formulations), and approximation schemes for multiple knapsack and 2D vector packing admit no (1+ε)-PTAS running in time 2^{o(1/ε)} or 2^{o(sqrt{1/ε})} respectively, with matching or nearly matching DP/ILP upper bounds. Tools are ETH, tight gadget reductions, DP enumerating job subsets, and ILP parameterized bounds.
AI-written summary · about
chapters (15)
- 0:00Introduction
- 1:32Exponential Time Hypothesis
- 1:51Specification
- 2:15Survey
- 3:23Goals
- 4:01Exact Algorithms
- 5:55Example
- 9:23Scheduling
- 10:07Approximation Schemes
- 10:26Multiple Knapsack Problems
- 11:31Restricted Knapsack Problems
- 17:48TwoDimensional Vector Packing
- 18:48Scheduling Problem
- 21:05Summary
- 22:44Question
related talks
34mNew Tools for Peak Memory Scheduling
23mWorst-Case to Expander-Case Reductions
01h 32mInapproximability of Constraint Satisfaction Problems I
01h 01mComplexity and Algorithmic Game Theory I
40mResilience of 3-Majority Dynamics to Non-Uniform Schedulers
28mSettling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams
25mAn Improved Lower Bound for Matroid Intersection Prophet inequalities
18mCharacterizing the Multi-Pass Streaming Complexity for Solving Boolean CSPs Exactly