Tomas Feder, Daniel Ford

Matroid intersection has a known polynomial time algorithm using an

oracle. We generalize this result to delta-matroids that do not have

equality as a restriction, and give a polynomial time algorithm for

delta-matroid intersection on delta-matroids without equality using an

oracle. We note that when equality is present, delta-matroid intersection

more >>>

Alexander Golovnev, Siyao Guo, Spencer Peters, Noah Stephens-Davidowitz

We study a natural and quite general model of branch-and-bound algorithms. In this model, an algorithm attempts to minimize (or maximize) a function $f : D \to \mathbb{R}_{\geq 0}$ by making oracle queries to a heuristic $h_f$ satisfying

\[

\min_{x \in S} f(x) \leq h_f(S) \leq \gamma \cdot ...
more >>>