Maximum weight bounded fractional matching

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?

Remarks

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 . Jüttner 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 .