1 Introduction
1.1 Formal Problem Statement
1.2 Related Work
1.3 Our Results
2 Preliminaries
3 Inapproximability
3.1 Overview of Proof
3.2 Reduction Overview
3.3 The True Clock & Colour Slots
3.4 Variables
3.5 Duplication of Variables and Constants
3.5.1 3-Duplicators
3.5.2 6-Duplicators
3.6 Clauses
3.7 Sorting Networks
3.7.1 12-Edge Duplicator
3.7.2 OR2 Gadget
3.7.3 AND2 Gadget
3.7.4 Slot Splitting Gadgets
3.7.5 SWAP Gadgets
3.7.6 Sorting Network Schedules
3.8 Tension
3.9 Correctness Proof of Reduction
4 Computational Complexity
5 Unweighted Poly Scheduling & Edge Coloring
6 Approximation Algorithms
6.1 Lower Bounds
6.2 Approximation for Almost Equal Growth Rates
6.3 Layering Algorithm
7 Fractional Poly Scheduling
7.1 Linear Programs for Poly Scheduling
7.2 Poly Density
8 Open Problems & Future Directions
References
