Optimization finds its way in many aspects of modern society, for example, in the planning of transport, scheduling of tasks, or allocation of resources. For some of these problems, efficient algorithms are known, whereas other problems are notoriously hard and evidence suggests that no efficient algorithms are possible. For a third group there are algorithms known that are in-between efficient and inefficient. The goal of this project is to study the optimality of these in-between algorithms by either improving them or showing that they cannot be improved.