An algorithm for weighted fractional matroid matching

DOI10.1016/J.JCTB.2013.05.004MaRDI QIDQ463292zbMATH OpenOpenAlexFDO

Authors Dion Gijswijt, Gyula Pap

Publication date 16 October 2014

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0806.1818

zbMATH Keywords

algorithmlattice polytopematroid matchingfractional matchingmatroid parity

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: 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.

Recommendations

• Fractional matroid matchings
• Publication:3199198
• Weighted fractional and integral k-matching in hypergraphs
• Approximation algorithms for weighted matching
• Exact and approximation algorithms for weighted matroid intersection
• Exact and approximation algorithms for weighted matroid intersection
• A linear-time approximation algorithm for weighted matchings in graphs
• A weighted linear matroid parity algorithm
• A weighted linear matroid parity algorithm

Cites work

• scientific article; zbMATH DE number 3643026 (Why is no real title available?)
• scientific article; zbMATH DE number 420868 (Why is no real title available?)
• scientific article; zbMATH DE number 4089320 (Why is no real title available?)
• scientific article; zbMATH DE number 3750968 (Why is no real title available?)
• An augmenting path algorithm for linear matroid parity
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Complexity of Matroid Property Algorithms
• Fractional matroid matchings
• Matching 2-lattice polyhedra: Finding a maximum vector
• Matroid matching and some applications
• Solving the linear matroid parity problem as a sequence of matroid intersection problems
• Two-lattice polyhedra: Duality and extreme points

Cited in

(10)

• scientific article; zbMATH DE number 11347 (Why is no real title available?)
• On the diameter of lattice polytopes
• Minimizing submodular functions on diamonds via generalized fractional matroid matchings
• A weighted linear matroid parity algorithm
• scientific article; zbMATH DE number 4174676 (Why is no real title available?)
• On matroid parity and matching polytopes
• Competitive weighted matching in transversal matroids
• Stochastic packing integer programs with few queries
• Algebraic algorithms for fractional linear matroid parity via noncommutative rank
• On the complexity of submodular function minimisation on diamonds

This page was built for publication: An algorithm for weighted fractional matroid matching

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q463292)