Lp-Based Approximation Algorithms For Scheduling And Inventory Management Problems

Abstract

There are two fundamental approaches for using linear programming in designing approximation algorithms: LP-rounding and the primal-dual method. In this thesis, we develop LP-based approximation algorithms for several scheduling and inventory management problems, using both LP-rounding and the primal-dual method. In machine scheduling, we consider a general class of single-machine scheduling problem of minimizing the total cost summing over all jobs, and the only requirement on the cost function of each job is that it is non-negative and non-decreasing. Using the primal-dual method, we give a simple algorithm for this problem that is guaranteed to return a solution that costs at most twice the optimal. To obtain this result, we add an exponential number of valid inequalities to strengthen the natural LP-relaxation, then design a primal-dual method that works on this exponential-sized LP. We then show how to modify our algorithm for scheduling problems with machine breakdown. In inventory management, we consider several generalization of the classical Joint Replenishment Problem (JRP): the tree JRP and the cardinality JRP. Using the LP-rounding technique, we give novel algorithms for the tree JRP and cardinality JRP that are guaranteed to generate a solution with cost within a factor of three and five, respectively, of the optimal.