Cornell University
Lp-Based Approximation Algorithms For Scheduling And Inventory Management Problems
Abstract
dc:description.abstractThere 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.
Degree
thesis:*- Name thesis:degree_name
- Ph. D., Operations Research
- Level thesis:degree_level
- Doctor of Philosophy
- Discipline thesis:degree_discipline
- Operations Research
- Grantor
- Cornell University
- Year dc:date.issued
- 2012
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Cheung, Maurice
- Chair dc:contributor.chair
-
- Shmoys, David B
- Committee members dc:contributor.committeemember
-
- Kleinberg, Robert David
- Lewis, Adrian S.
Subjects
dc:subject × 3Rights
- Language dc:language.iso
- en_US
Identifiers
dc:identifier.*- Dc Identifier Bibid
- 8251360