Maximum weight bounded fractional matching

From Egres Open
Jump to: navigation, search

Given a graph G=(V,E), and weight and capacity functions [math]w,u: E \to {\mathbb R_+}[/math] defined on the edge set, is there a combinatorial, strongly polynomial algorithm to find a vector x maximizing wx subject to the constraints [math]x \in P(G)[/math] and [math]x \leq u[/math], where P(G) is the convex hull of the incidence vectors of perfect matchings of G?


Here a combinatorial algorithm informally means that only addition, multiplication by constant, and comparison operations are used on components of u. More precisely, we are interested in an algorithm that is linear in u, as defined in [1]. Jüttner [1] showed that such an algorithm could be used to solve the budgeted maximum matching problem, which is defined as follows. Let G=(V,E) be a graph, [math]c,w: E \to {\mathbb R}_+[/math] be cost and weight functions defined on edges, and [math]\beta \in {\mathbb R}_+[/math] be a budget constraint. Find a nonnegative vector z with [math]cz \leq \beta[/math] which minimizes the weight of the (w-z)-maximal matching. This problem can be solved in strongly polynomial time when G is bipartite [1].


  1. 1.0 1.1 1.2 A. Jüttner, On budgeted optimization problems, SIAM J. Discrete Math. 20 (2006), 880-892. DOI link. Author link.