SUPER-POLYNOMIAL APPROXIMATION BRANCHING ALGORITHMS

被引：2

作者：

Escoffier, Bruno ^{[1
]}

Paschos, Vangelis Th. ^{[2
]}

Tourniaire, Emeric ^{[2
]}

机构：

[1] UPMC Univ Paris 06, Sorbonne Univ, CNRS, UMR 7606,LIP6, 4 Pl Jussieu, F-75005 Paris, France

[2] Univ Paris 09, PSL Res Univ, LAMSADE, CNRS,UMR 7243, Paris, France

来源：

RAIRO-OPERATIONS RESEARCH | 2016年 / 50卷 / 4-5期

关键词：

Branching algorithm; moderately exponential approximation; approximation schema; VERTEX COVER; COMPLEXITY; OPTIMIZATION; SET; CUT;

D O I：

10.1051/ro/2015060

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We give sufficient conditions for deriving moderately exponential and/or parameterized time approximation schemata (i.e., algorithms achieving ratios 1 +/- epsilon, for arbitrarily small epsilon) for broad classes of combinatorial optimization problems via a well-known technique widely used for deriving exact algorithms, namely the branching tree pruning.

引用

页码：979 / 994

页数：16