Connections between Primal-Dual and Iterative Rounding for designing approximation algorithms

During the past two decades, the primal-dual scheme has been a major tool for the design of algorithms with very good approximation factors for NP-hard problems. This method is based on the duality theorems of Linear Programming (LP): Strong duality ensures that satisfaction of complementary slackness conditions implies optimality of a (fractional) solution. “Good” relaxation (i.e., relaxation by a small factor) of these conditions can be shown to imply a good integral solution for the original problem formulated as an LP. The primal-dual method is based on the connection between a primal LP and its dual, but in recent years a new method called iterated rounding has been applied to a variety of problems, for which no equally good primal-dual schemes were known. Iterated rounding deals only with the primal LP formulation of the hard (say, minimization) problem, and very carefully rounds up a fractional solution piece-by-piece to an integral one. So, iterated rounding is a combinatorial primal method (like Simplex is a combinatorial method for solving LPs) and the primal-dual scheme involves both the primal and the dual (like similar methods for solving LPs).

The aim of this project will be to explore the possible connections between iterated rounding and primal-dual schemes. We will try to understand their application to network design problems, and through that we will try to understand why each works so well on its own set of problems, and see whether there could be a method of transforming iterated routing algorithms into primal-dual ones and vice-versa. The immediate goal for the research team (supervisor, intern and at least one graduate student) will be to improve the approximation factor of network design problems, but the more ambitious one will be the development of new algorithm design methodologies that will try to encompass both iterated rounding and primal-dual schemes.

Faculty Supervisor:

Dr. George Karakostas

Student:

Yogesh Anbalagan

Partner:

Discipline:

Engineering - computer / electrical

Sector:

Information and communications technologies

University:

McMaster University

Program: