Hehui Wu (SFU)
20/09/13 12:00 Talks
Demand matching and correlated independent sets in trees
Speaker:
Hehui Wu (Simon Fraser University, Math.)
Abstract:
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.
Date:
Friday, September 20, 2013
Time:
12:00 pm - 1:00 pm
Location:
TASC1 Building, Room No. 9204, Simon Fraser University, Burnaby
Hehui Wu (Simon Fraser University, Math.)
Abstract:
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.
Date:
Friday, September 20, 2013
Time:
12:00 pm - 1:00 pm
Location:
TASC1 Building, Room No. 9204, Simon Fraser University, Burnaby