Task: Given an Independence Oracle and a Basis Super-Set Oracle I want to proove, that they are polynomial equivalent for Matroids.
First I tried to update my knowledge about the topic. Let $(E,\mathcal{F})$ be a Matroid.
The Independence Oracle decides if a given set $F\subset E$ whether $F$ is in $\mathcal{F}$ or not. We learned the Best-In-Greedy-Algorithm:
Given a weight function $c:E\to\mathbb{R}_+$ sort $E=\{e_1,\dots ,e_n\}$ such that $c(e_1)\geq\dots\geq c(e_n)$. Define $F:=\emptyset$. Iterate above (the sorted) $E$ in descending order and add $e_i$ to the set $F$ if $(F\cup\{e_i\})\in\mathcal{F}$.
The Basis Super-Set Oracle decides for a given set $F\subset E$ wether it contains a Basis or not. We learned the Worst-Out-Greedy-algorithm:
Given a weight function $c:E\to\mathbb{R}_+$ sort $E=\{e_1,\dots ,e_n\}$ such that $c(e_1)\leq\dots\leq c(e_n)$. Define $F:=E$. Iterate above (the sorted) $E$ in ascending order and remove $e_i$ from the set $F$ if $(F\setminus\{e_i\})$ still contains a Basis.
The book Combinatorial Optimization - Theory and Algorithms written by Korte & Vygen states:
It is easy to see that the Best-In-Greedy for the Maximization Problem for $(E, \mathcal{F}, c)$ corresponds to the Worst-Out-Greedy for the Minimization Problem for $(E,\mathcal{F}^{*},$ $c)$: adding an element to $F$ in the Best-In-Greedy corresponds to removing an element from $F$ in the Worst-Out-Greedy.
Well for me it is not easy to see. I would appreciate any hints how to proove the task.
To prove, that both Oracles are polynomial equivalent I figured out, that I have to show whether one can be simulated by polynomial-time oracle algorithm using the other. Let $I$ be an instance for the Independence Oracle and $B$ be an instance of the Basis Super-Set Oracle. What I think is, that I have to find a polynomial from $I$ to $B$ and vice versa and to show, that every oracle is able solve the transformed Instance of the other one. Am I on the right path? If yes, what how do I realize a proof like this one?