Hehui Wu (SFU)

Demand matching and correlated independent sets in trees
Hehui Wu (Simon Fraser University, Math.)


We consider the demand matching problem where we are given a simple bipartite graph G = (V, E), a demand d_e and profit p_e for each edge  e in E and capacity b_v for each vertex  v in V. A subset M of edges is called a demand matching if the sum of demands of edges chosen in M incident at v is at most b_v for each vertex v. The goal of the demand matching problem is to select a demand matching M which maximizes the sum of profit of edges in M.

We give nearly tight upper and lower bounds on the integrality gap of a natural linear programming relaxation for the problem. We show that the integrality gap of the linear program is closely related to finding probability distributions over independent sets of a tree that satisfy certain marginal as well as pairwise correlations. We give a nearly tight characterization for such distributions. We use this characterization to bound the integrality gap of the linear programming relaxation for the demand matching problem in the interval [2.6999, 2.7086].

This is a joint work with Mohit Singh from Microsoft Research.


Friday, September 20, 2013


12:00 pm - 1:00 pm

TASC1 Building, Room No. 9204, Simon Fraser University, Burnaby