Back to search

Cornell University

Approximation Algorithms Via The Primal-Dual Schema: Applications Of The Simple Dual-Ascent Method To Problems From Logistics

Abstract

dc:description.abstract

The primal-dual schema has been employed to provide approximation algorithms for a large variety of combinatorial optimization problems. This technique relies upon simultaneously constructing a primal integer solution that is feasible for the minimization problem of interest, as well as a dual solution whose objective function value serves as a lower bound. By operating in this framework, the advantages of using an LP-based method are obtained, such as generating an instance-dependent approximation ratio that may greatly improve on the theoretical worst-case, while obviating the need to actually solve an LP. In this thesis, we focus on the application of the simple dual-ascent method, where the feasible dual solution is modified by increasing only a single dual variable at a time, and obtain approximation algorithms for the following problems: capacitated covering problems with lot-sizing applications, the location routing problem with a global limit on locations, and a variant of the generalized assignment problem. For each of these areas, we introduce an exponential number of valid inequalities to strengthen the LP-relaxation, thereby decreasing the integrality gap. As we are only increasing a single dual variable at a time, each of the primal constraints is effectively providing the mechanism by which both the primal and dual solutions can be modified at any given time.

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Carnes, Timothy

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Dc Identifier Bibid
7061541

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
related terms
citation

Carnes, Timothy. Approximation Algorithms Via The Primal-Dual Schema: Applications Of The Simple Dual-Ascent Method To Problems From Logistics. 2010. https://hdl.handle.net/1813/17733