A weighted linear matroid parity algorithm

DOI10.1145/3055399.3055436zbMATH Open1370.05029arXiv1905.13371OpenAlexW2625145881MaRDI QIDQ4977977FDOQ4977977

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)

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.

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

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

zbMATH Keywords

matchingpolynomial-time algorithmPfaffianprimal-dual approachlinear matroid parity

Mathematics Subject Classification ID

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

Cited In (25)

• Title not available (Why is that?)
• Weighted triangle-free 2-matching problem with edge-disjoint forbidden triangles
• Weighted linear matroid parity
• Title not available (Why is that?)
• An algorithm for weighted fractional matroid matching
• A Fast, Simpler Algorithm for the Matroid Parity Problem
• Title not available (Why is that?)
• The linear delta-matroid parity problem
• Matroid matching via mixed skew-symmetric matrices
• A weighted linear matroid parity algorithm
• Algebraic algorithms for linear matroid parity problems
• Weighted triangle-free 2-matching problem with edge-disjoint forbidden triangles
• Boundary classes for graph problems involving non-local properties
• Algorithms for the partial inverse matroid problem in which weights can only be increased
• Computing the Degree of Determinants via Discrete Convex Optimization on Euclidean Buildings
• Pfaffian pairs and parities: counting on linear matroid intersection and parity problems
• A weighted independent even factor algorithm
• 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
• Pfaffian pairs and parities: counting on linear matroid intersection and parity problems
• On matroid parity and matching polytopes
• 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)