Title: Approximating the demand matching problem through iterated packing

Speaker: Ojas Parekh, Emory University

Date/Time: Thursday, August 13, 2009, 9:00 am - 10:00 am      

Location: CSRI/90

Brief Abstract: The demand matching problem in graphs is an NP-hard common generalization of the classical knapsack and maximum (weighted) matching problems, which have found numerous applications in diverse areas such as scheduling, resource allocation, graph partitioning, and auction design. The demand matching problem is defined on a (weighted) graph where each vertex v has a capacity b_v, and each edge e has a demand d_e. Selecting an edge uv consumes d_uv units of capacity at both the vertices u and v; we seek the maximum (weight) subset of edges such that the total capacity at each vertex is able to accommodate the selected edges.

We present approximation algorithms for the demand matching problem based on a natural linear programming (LP) relaxation. Our main result is an algorithm which delivers an approximately optimal solution that is guaranteed to select at least 1/3 of the weight of an optimal solution. This result is best possible using the natural LP formulation. A highlight of the algorithm is that it is based on a conceptually simple procedure which constructs a small family of integral solutions by iteratively packing fractional components.

CSRI POC: Mark D. Rintoul, (505) 844-9592