Weighted Linear Matroid Parity

Author Satoru Iwata



PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2017.1.pdf
  • Filesize: 364 kB
  • 5 pages

Document Identifiers

Author Details

Satoru Iwata

Cite AsGet BibTex

Satoru Iwata. Weighted Linear Matroid Parity. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 1:1-1:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.ISAAC.2017.1

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, Lovasz (1978) 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. This talk presents a recently developed 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.
Keywords
  • Matroid
  • matching
  • Pfaffian
  • polynomial-time algorithm

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail