Bounding the Running Time of Algorithms for Scheduling and Packing Problems

Source abstract

Our goal is to show tight bounds on the running time of algorithms for scheduling and packing problems. To prove lower bounds, we investigate implications of the exponential time hypothesis on such algorithms. For exact algorithms we consider the dependence of the running time on the number $n$ of items (for packing) or jobs (for scheduling). We prove a lower bound of $2^{{\rm o}(n)} \times \|{I}\|^{{{\rm O}(n)}}$, where $\|{I}\|$ denotes the encoding length of the instance, for several of these problems, including SubsetSum, Knapsack, BinPacking, $\langle{P2}\|{C_{\max}}\rangle,\ \text{and}\ \langle{P2}\|{\sum w_j C_j}\rangle$. We also develop an algorithmic framework that is able to solve a large number of scheduling and packing problems in time $2^{{\rm o}(n)} \times \|{I}\|^{{{\rm O}(n)}}$. Finally, we consider approximation schemes. We show that there is no polynomial time approximation scheme for MultipleKnapsack (MKS) and 2d-Knapsack with running time $2^{{\rm o}(1/\epsilon)} \times \|{I}\|^{{{\rm O}(n)}}$ and $n^{{\rm o}(1/\epsilon)} \times \|{I}\|^{{{\rm O}(n)}}$, respectively.