Definition
Factor-
Approximation Algorithm Let
be a minimisation or maximisation problem, and let . Minimisation
For a minimisation problem,
where
. Maximisation
For a maximisation problem,
where
. An algorithm
is a factor- approximation algorithm for if,
- on each instance
, produces a factor- approximate solution for and - runs in polynomial time in
.
Solution
Definition
Link to originalFactor-
Approximate Solution A feasible solution
to an instance is a factor- approximate solution if it satisfies the approximation bound below.
NP-Hard Optimisation Problem
Definition
Link to original
-Approximable NP-Hard Optimisation Problem An NP-hard optimisation problem
is called -approximable if it admits a factor-delta approximation algorithm