An algorithm for weighted fractional matroid matching
2013
Let M be a matroid on ground set E with rank function r. A subset [email protected]?E is called a line when r(l)@?{1,2}. Given a finite set L of lines in M, a vector [email protected]?R"+^L is called a fractional matching when @?"l"@?"Lx"la(F)"l=Q, a maximum weight fractional matching. A simple reference to the equivalence of separation and optimization does not lead to such an algorithm, since no direct method for polynomial time separation is known for this polytope.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
16
References
15
Citations
NaN
KQI