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

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.