Chennai Mathematical Institute

Seminars




12.00 noon
Primal Dual algorithms for Resource Allocation Problems

Sambuddha Roy
IBM, Delhi.
28-10-10


Abstract

We consider primal dual algorithms for resource allocation problems, that commonly occur in various real-life scenarios. The problem we consider, the {\tt ResAll} problem is a {\em covering} version of the problem commonly known as the {\tt Unsplittable Flow Problem} (UFP) on the line. The UFP problem on the line is a packing problem, and constant factor approximations are known only for certain special cases (for instance, for instances that satisfy the so-called No Bottleneck Assumption [NBA]). It is a popular conjecture that a constant factor approximation exists for the general UFP problem on the line. We show that, for the corresponding {\em covering} versions of the popular UFP problem, there {\em does} exist (polynomial time) constant factor approximations.

The ResAll problem is a generalization of the Minimum Knapsack Problem, and therefore NP-hard; thus we provide polynomial time approximation algorithms for the same. Our techniques are LP based; we exploit the primal dual paradigm for LPs to provide fast combinatorial algorithms for the ResAll problem.

The talk will be at an introductory level, and only basic knowledge of algorithms is required.

This work is joint with Venkat Chakravarthy, Amit Kumar, Gyana Parija, and Yogish Sabharwal.