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'