An algorithm for weighted fractional matroid matching

Details An algorithm for weighted fractional matroid matching An algorithm for weighted fractional matroid matching

2008-06-11

arxiv.org/abs/0806.1818v1

Mathematics

Combinatorics

13 pages

Scientific paper

Let M be a matroid on ground set E. A subset l of E is called a `line' when its rank equals 1 or 2. Given a set L of lines, a `fractional matching' in (M,L) is a nonnegative vector x indexed by the lines in L, that satisfies a system of linear constraints, one for each flat of M. Fractional matchings were introduced by Vande Vate, who showed that the set of fractional matchings is a half-integer relaxation of the matroid matching polytope. It was shown by Chang et al. that a maximum size fractional matching can be found in polynomial time. In this paper we give a polynomial time algorithm to find for any given weights on the lines in L, a maximum weight fractional matching.

Affiliated with

Also associated with

No associations

Rating

An algorithm for weighted fractional matroid matching does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with An algorithm for weighted fractional matroid matching, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An algorithm for weighted fractional matroid matching will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-264846