Description
EGERVÁRY SZEMINÁRIUM
Abstract: Matroid intersection is a well-studied, powerful framework that
generalizes various problems in combinatorial optimization. As written
in many textbooks, it is known that the matroid intersection problem
enjoys several efficient algorithms, celebrated max-min
characterizations, polyhedral descriptions with nice properties, and so
on. However, when such tractable features are discussed, we usually
assume that the information of two matroids in question is obtained
separately, e.g., we can ask for the rank of a subset in each matroid,
or whether a subset is independent or not in each matroid. In this
study, we investigate what happens if only restricted oracles are
available, which answer the sum/minimum/maximum of the ranks of a subset
in two matroids or whether a subset is independent in both matroids or
not.
This is a joint work with Kristóf Bérczi, Tamás Király, and Yu Yokoi,
and also includes and extends an early result of Mihály Bárász. I will
explain technical details skipped in the 12th Japanese-Hungarian
Symposium and a little progress after it.