A Subexponential Algorithm for Abstract Optimization Problems
Bernd Gärtner
Institut für Informatik
Freie Universität Berlin
email: gaertner@inf.fu-berlin.de
Report B 93-05
May 93
Get the report here or by anonymous ftp:
Server: fubinf.inf.fu-berlin.de
File: pub/reports/tr-b-93-05.ps.gz
An {\em Abstract Optimization Problem} (AOP) is a triple $(H,<, \Phi)$ where
$H$ is a finite set, $<$ a total order on $2^{H}$ and $\Phi$ an oracle that,
for given $F\subseteq G\subseteq H$, either reports that
$F=\min_{<}\{F'\subseteq G\}$ or
returns a set $F'\subseteq G$ with $F'