Matroid Intersection under Restricted Oracles

DOI10.1137/22M152579XzbMATH Open1519.90201arXiv2209.14516MaRDI QIDQ6161263FDOQ6161263

Authors: Kristóf Bérczi, Tamás Király, Yutaro Yamaguchi, Yu Yokoi 

Publication date: 27 June 2023

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: Matroid intersection is one of the most powerful frameworks of matroid theory that generalizes various problems in combinatorial optimization. Edmonds' fundamental theorem provides a min-max characterization for the unweighted setting, while Frank's weight-splitting theorem provides one for the weighted case. Several efficient algorithms were developed for these problems, all relying on the usage of one of the conventional oracles for both matroids. In the present paper, we consider the tractability of the matroid intersection problem under restricted oracles. In particular, we focus on the rank sum, common independence, and maximum rank oracles. We give a strongly polynomial-time algorithm for weighted matroid intersection under the rank sum oracle. In the common independence oracle model, we prove that the unweighted matroid intersection problem is tractable when one of the matroids is a partition matroid, and that even the weighted case is solvable when one of the matroids is an elementary split matroid. Finally, we show that the common independence and maximum rank oracles together are strong enough to realize the steps of our algorithm under the rank sum oracle.

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

Recommendations

• Two algorithms for weighted matroid intersection
• A Fast Approximation for Maximum Weight Matroid Intersection
• Exact and approximation algorithms for weighted matroid intersection
• Exact and approximation algorithms for weighted matroid intersection
• Efficient theoretic and practical algorithms for linear matroid intersection problems

zbMATH Keywords

matroid intersectiontractabilitycommon independence oraclemaximum rank oraclerank sum oracle

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Combinatorial aspects of matroids and geometric lattices (05B35)

Cites Work

• Title not available (Why is that?)
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Title not available (Why is that?)
• Improved Bounds for Matroid Partition and Intersection Algorithms
• Selected papers on probability and statistics
• Title not available (Why is that?)
• Rooted \(k\)-connections in digraphs
• Matroid matching and some applications
• Exact and approximation algorithms for weighted matroid intersection
• Title not available (Why is that?)
• Complexity of Matroid Property Algorithms
• A weighted matroid intersection algorithm
• The dependence graph for bases in matroids
• The computational complexity of matroid properties
• Matroid intersection algorithms
• Matching Theory for Combinatorial Geometries
• Matroid Intersection
• Two algorithms for weighted matroid intersection
• Title not available (Why is that?)
• Algorithmic versus axiomatic definitions of matroids
• AN ALGORITHM FOR FINDING AN OPTIMAL "INDEPENDENT ASSIGNMENT"
• Comments on bases in dependence structures
• Matroids from hypersimplex splits
• Independence and port oracles for matroids, with an application to computational learning theory
• Hypergraph characterization of split matroids

Cited In (1)

• Title not available (Why is that?)

This page was built for publication: Matroid Intersection under Restricted Oracles

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