Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with oracle model:
TR05-016 | 13th January 2005
Tomas Feder, Daniel Ford

Classification of Bipartite Boolean Constraint Satisfaction through Delta-Matroid Intersection

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 >>>

TR21-141 | 28th September 2021
Alexander Golovnev, Siyao Guo, Spencer Peters, Noah Stephens-Davidowitz

On the (im)possibility of branch-and-bound search-to-decision reductions for approximate optimization

Revisions: 1

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 >>>

ISSN 1433-8092 | Imprint