CIS Seminar - Nearly Tight Linear Programming Bounds for Demand Matching in Bipartite Graphs

CIS Seminar
3:00 PM, Wednesday October 7 2015
235 Weir Hall

Nearly Tight Linear Programming Bounds for Demand Matching in Bipartite Graphs

Abstract: We consider the demand matching problem which is a generalization of the maximum weight bipartite matching problem as well as the b-matching problem. We are given a simple bipartite graph G=(V,E), a demand function d and a profit function $\pi$ on edges and a capacity function b on vertices. A subset M of edges is called a demand matching if the sum of demands d_e 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. When all demands d_e=1, this problem is exactly the b-matching problem.

In this talk we give nearly tight upper and lower bounds on the integrality gap of a natural linear programming relaxation for the problem. Our first result is to show that the integrality gap is bounded from above by the fractional coloring number of a tree-net. A tree-net is a graph obtained by connecting non-adjacent vertices of a tree by vertex disjoint paths of length at least two. We then give an explicit bound of 2.709 on the fractional chromatic number of any tree-net which also results in a $\up$-approximation algorithm.  To complement this algorithm, we explicitly show a lower bound of 2.699 on the integrality gap by constructing tree-net graphs whose fractional chromatic number is at least 2.699.

This is joint work with Mohit Singh in Microsoft Research.

Bio: Dr. Hehui Wu is an Assistant Professor in the Department of Mathematics at University of Mississippi. He received his Ph.D. degree in Mathematics from University of Illinois at Urbana-Champaign. Before he joined University of Mississippi, he worked as a Postdoctoral Fellow in School of Computer Science at Mcgill University in 2011-2013 and as a PIMS Postdoctoral Fellow in the Department of Mathematics at Simon Fraser University in 2013-2014. His research interests lie in combinatorics, including graph theory, combinatorial optimization, and additive combinatorics. With coauthors, he fully settled the long-standing problem Fouquet-Jolivet Conjecture from 1976 and the Ohba's Conjecture from 2002; the latter was listed in "100 unsolved problems in Graph Theory" in 2008.