Back to search

Cornell University

Lp-Based Approximation Algorithms For Scheduling And Inventory Management Problems

Abstract

dc:description.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.

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 × 3

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Dc Identifier Bibid
8251360

Chain of custody

source
Harvested from
Cornell University
Base URL
ecommons.cornell.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Cheung, Maurice. Lp-Based Approximation Algorithms For Scheduling And Inventory Management Problems. Doctor of Philosophy thesis, Cornell University, 2012. https://hdl.handle.net/1813/31470