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.
    • Correction
    • Source
    • Cite
    • Save
    • Machine Reading By IdeaReader
    16
    References
    15
    Citations
    NaN
    KQI
    []