# A Survey on Approximation in Parameterized Complexity: Hardness and Algorithms
## 4 Algorithms
### Packing Problems
#### 4.1.4 Scheduling  
Yet another packing problem on graphs, which, however, has applications in scheduling and bandwidth allocation, is the Unsplittable Flow on a Path problem. Here a path with edge capacities is given together with a set of tasks, each of which specifies a start and an end vertex on the path and a demand value. The goal is to find the largest number of tasks such that for each edge on the path the total demand of selected tasks for which the edge lies between its start and end vertex, does not exceed the capacity of the edge. This problem admits a QPTAS [121], but it remains a challenging open question whether a PTAS exists. When parameterizing by the solution size, Unsplittable Flow on a Path is W[1]-hard [122]. However a PAS exists [122] for this parameter.  
**Theorem 17** ([122]).: _For the Unsplittable Flow on a Path problem a \((1+\varepsilon)\)-approximation can be computed in \(2^{O(k\log k)}n^{g(\varepsilon)}\) time for some computable function \(g\) and any \(\varepsilon>0\), where \(k\) is the solution size._  
Another scheduling problem is Flow Time Scheduling, for which a set of jobs is given, each of which is specified by a processing time, a release date, and a weight. The jobs need to be scheduled on a given number of machines, such that no job is processed before its release date and a job only runs on one machine at a time. Given a schedule, the flow time of a job is the weighted difference between its completion time and release date, and the task for the Flow Time Scheduling problem is to minimize the sum of all flow times. Two types of schedules are distinguished: in a preemptive schedule a job may be interrupted on one machine and then resumed on another, while in a non-preemptive schedule every job runs on one machine until its completion once it was started. If pre-emptive schedules are allowed, Flow Time Scheduling has no polynomial time \(O(\log^{1-\varepsilon}p)\)-approximation algorithm [123], unless P = NP, where \(p\) is the maximum processing time. For the more restrictive non-preemtive setting, no \(O(n^{1/2-\varepsilon})\)-approximation can be computed in polynomial time [124], unless P = NP, where \(n\) is the number of jobs. The latter lower bound is in fact even valid for only one machine, and thus parameterizing Flow Time Scheduling by the number of machines will not yield any better approximation ratio in this setting. A natural parameter for Flow Time Scheduling is the maximum over all processing times and weights of the given jobs. It is not known whether the problem is FPT or W[1]-hard for this parameter. However, when combining this parameter with the number of machines, a PAS can be obtained [125] despite the strong polynomial time approximation lower bounds.  
**Theorem 18** ([125]): _For the Flow Time Scheduling problem a \((1+\varepsilon)\)-approximation can be computed in \((mk)^{O(mk^{3}/\varepsilon)}n^{O(1)}\) time in the preentive setting, and in \((mk/\varepsilon)^{O(mk^{3})}n^{O(1)}\) time in the non-preemtive setting, for any \(\varepsilon>0\), where \(m\) is the number of machines and \(k\) is an upper bound on every processing time and weight._