Approximation Algorithms in Allocation, Scheduling and Pricing

Abstract

This dissertation examines four optimisation problems. The first chapter examines the optimisation of network usage to prevent traffic congestion and internet data issues. The second chapter describes cyclical production planning for machines, such as those used to process huge volumes of lycra. In the third chapter, tasks that involve several components (such as processing time and memory use) are planned on computers so that no single computer is overloaded. The fourth chapter describes strategies for hiring highly skilled employees and strategies to increase the profit margins of a product. A theoretical lower limit is defined for the complexity of each problem and an algorithm is developed to approach this lower limit.