2017/05/29 by Sara Ahmadian, Ahmadian, Sara, Zachary Friggstad +1 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Approximation algorithm #Bounded function #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Data Structures and Algorithms (cs.DS) #Discrete mathematics #FOS: Computer and information sciences #Graph #Line graph #Linear programming #Linear programming relaxation #Matching (statistics) #Mathematical optimization #Mathematics #Matroid #Optimization and Search Problems #Pathwidth #Rounding #Treewidth #Vertex (graph theory) #cs.DS
paper · pdf · doi:10.48550/arxiv.1705.10396
arxiv created 2017/05/29 · openalex publication_date 2017/05/29 · arxiv updated 2017/05/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We pursue a study of the Generalized Demand Matching problem, a common generalization of the b-Matching and Knapsack problems. Here, we are given a graph with vertex capacities, edge profits, and asymmetric demands on the edges. The goal is to find a maximum-profit subset of edges so the demands of chosen edges do not violate vertex capacities. This problem is APX-hard and constant-factor approximations are known. Our results fall into two categories. First, using iterated relaxation and various filtering strategies, we show with an efficient rounding algorithm if an additional matroid structure \mathcal M is given and we further only allow sets F ⊆ E that are independent in \mathcal M, the natural LP relaxation has an integrality gap of at most (25)/(3) ≈ 8.333. This can be improved in various special cases, for example we improve over the 15-approximation for the previously-studied Coupled Placement problem [Korupolu et al. 2014] by giving a 7-approximation. Using similar techniques, we show the problem of computing a minimum-cost base in \mathcal M satisfying vertex capacities admits a (1,3)-bicriteria approximation. This improves over the previous (1,4)-approximation in the special case that \mathcal M is the graphic matroid over the given graph [Fukanaga and Nagamochi, 2009]. Second, we show Demand Matching admits a polynomial-time approximation scheme in graphs that exclude a fixed minor. If all demands are polynomially-bounded integers, this is somewhat easy using dynamic programming in bounded-treewidth graphs. Our main technical contribution is a sparsification lemma allowing us to scale the demands to be used in a more intricate dynamic programming algorithm, followed by randomized rounding to filter our scaled-demand solution to a feasible solution.