A weighted linear matroid parity algorithm

DOI10.1145/3055399.3055436MaRDI QIDQ4977977zbMATH OpenOpenAlexFDO

Authors Satoru Iwata, Yusuke Kobayashi

Publication date 17 August 2017

Published in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

matchingpolynomial-time algorithmPfaffianprimal-dual approachlinear matroid parity

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Combinatorial aspects of matroids and geometric lattices (05B35)

Abstract: The matroid parity (or matroid matching) problem, introduced as a common generalization of matching and matroid intersection problems, is so general that it requires an exponential number of oracle calls. Nevertheless, Lov'asz (1980) showed that this problem admits a min-max formula and a polynomial algorithm for linearly represented matroids. Since then efficient algorithms have been developed for the linear matroid parity problem. In this paper, we present a combinatorial, deterministic, polynomial-time algorithm for the weighted linear matroid parity problem. The algorithm builds on a polynomial matrix formulation using Pfaffian and adopts a primal-dual approach based on the augmenting path algorithm of Gabow and Stallmann (1986) for the unweighted problem.

Recommendations

• A weighted linear matroid parity algorithm
• Weighted linear matroid parity
• Solving the linear matroid parity problem as a sequence of matroid intersection problems
• Shortest disjoint \(S\)-paths via weighted linear matroid parity
• Algebraic algorithms for linear matroid parity problems

Cited in

(25)

• scientific article; zbMATH DE number 11347 (Why is no real title available?)
• Weighted triangle-free 2-matching problem with edge-disjoint forbidden triangles
• Weighted linear matroid parity
• An algorithm for weighted fractional matroid matching
• scientific article; zbMATH DE number 3902670 (Why is no real title available?)
• A Fast, Simpler Algorithm for the Matroid Parity Problem
• scientific article; zbMATH DE number 2086910 (Why is no real title available?)
• The linear delta-matroid parity problem
• Matroid matching via mixed skew-symmetric matrices
• A weighted linear matroid parity algorithm
• Algorithms for the partial inverse matroid problem in which weights can only be increased
• Boundary classes for graph problems involving non-local properties
• Algebraic algorithms for linear matroid parity problems
• Weighted triangle-free 2-matching problem with edge-disjoint forbidden triangles
• Computing the Degree of Determinants via Discrete Convex Optimization on Euclidean Buildings
• A weighted independent even factor algorithm
• Pfaffian pairs and parities: counting on linear matroid intersection and parity problems
• Shortest disjoint \(S\)-paths via weighted linear matroid parity
• On a weighted linear matroid intersection algorithm by deg-det computation
• Weighted matching with pair restrictions
• An augmenting path algorithm for linear matroid parity
• On matroid parity and matching polytopes
• Pfaffian pairs and parities: counting on linear matroid intersection and parity problems
• Random pseudo-polynomial algorithms for exact matroid problems
• Algorithm for constraint partial inverse matroid problem with weight increase forbidden

This page was built for publication: A weighted linear matroid parity algorithm

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