Super-polynomial approximation branching algorithms
Bruno Escoffier, Vangélis Th. Paschos, Émeric Tourniaire · RAIRO - Operations Research · 2015
We give sufficient conditions for deriving moderately exponential and/or parameterized time approximation schemata (i.e., algorithms achieving ratios 1 ± ϵ, for arbitrarily small ϵ) for broad classes of combinatorial optimization problems via a well-known technique widely used for deriving exact algorithms, namely the branching tree pruning.