Matroid Intersection under Restricted Oracles
From MaRDI portal
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.
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
Cites work
- A weighted matroid intersection algorithm
- Algorithmic versus axiomatic definitions of matroids
- AN ALGORITHM FOR FINDING AN OPTIMAL "INDEPENDENT ASSIGNMENT"
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Comments on bases in dependence structures
- Complexity of Matroid Property Algorithms
- Exact and approximation algorithms for weighted matroid intersection
- scientific article; zbMATH DE number 3643026 (Why is no real title available?)
- scientific article; zbMATH DE number 3750968 (Why is no real title available?)
- scientific article; zbMATH DE number 5873618 (Why is no real title available?)
- scientific article; zbMATH DE number 3404256 (Why is no real title available?)
- scientific article; zbMATH DE number 3422402 (Why is no real title available?)
- Hypergraph characterization of split matroids
- Improved Bounds for Matroid Partition and Intersection Algorithms
- Independence and port oracles for matroids, with an application to computational learning theory
- Matching Theory for Combinatorial Geometries
- Matroid Intersection
- Matroid intersection algorithms
- Matroid matching and some applications
- Matroids from hypersimplex splits
- Rooted \(k\)-connections in digraphs
- Selected papers on probability and statistics
- The computational complexity of matroid properties
- The dependence graph for bases in matroids
- Two algorithms for weighted matroid intersection
Cited in
(6)- scientific article; zbMATH DE number 5888307 (Why is no real title available?)
- Supermodular extension of Vizing's edge-coloring theorem
- Polynomial algorithms to minimize 2/3-submodular functions
- Weakly polynomial-time algorithms to minimize 2/3-submodular functions
- Deterministic (2/3-)-approximation of matroid intersection using nearly-linear independence-oracle queries
- Optimization of the directed spanning trees using the weighted matroid intersection algorithm
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)
