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'