# 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 ^{[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]}.

## References

- ↑
^{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.