Document Type
Lecture
Publication Date
9-17-2012
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 = (VE), a demand function d and a pro t function on edges and a capacity function b on vertices. A subset M of edges is called a demand matching if the sum of demands de of edges chosen in M incident at v is at most bv for each vertex v. The goal of the demand matching problem is to select a demand matching M which maximizes the sum of pro t of edges in M. When all demands de = 1, this problem is exactly the b-matching problem. We give nearly tight upper and lower bounds on the integrality gap of a natural linear programming relaxation for the problem. Our rst 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 nonadjacent vertices of a tree by vertex disjoint paths of length at least two. We then present an explicit bound of 2709 on the fractional chromatic number of any tree-net which also results in a 2709-approximation algorithm. To complement this algorithm, we explicitly show a lower bound of 2699 on the integrality gap by constructing tree-net graphs whose fractional chromatic number is at least 2699. This is joint work with Dr. Mohit Singh.
Relational Format
presentation
Recommended Citation
Wu, Hehui, "Nearly Tight Linear Programming Bounds for Demand Matching in Bipartite Graphs" (2012). Combinatorics Seminar. 61.
https://egrove.olemiss.edu/math_combinatorics/61
