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

共 32 条

[1] [Anonymous], 1979, Computers and Intractablity: A Guide to the Theory of NP-Completeness
[2] [Anonymous], 2007, TCS
[3] [Anonymous], 1999, COMPLEXITY APPROXIMA
[4] Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem
Becker, A
Geiger, D
[J]. ARTIFICIAL INTELLIGENCE, 1996, 83 (01) : 167 - 188
[5] Bonnet Edouard, 2013, Parameterized and Exact Computation. 8th International Symposium, IPEC 2013. Revised Selected Papers: LNCS 8246, P54, DOI 10.1007/978-3-319-03898-8_6
[6] Approximation of MAX INDEPENDENT SET, MIN VERTEX COVER and related problems by moderately exponential algorithms
Bourgeois, Nicolas
Escoffier, Bruno
Paschos, Vangelis Th.
[J]. DISCRETE APPLIED MATHEMATICS, 2011, 159 (17) : 1954 - 1970
[7] Approximation of MIN COLORING by moderately exponential algorithms
Bourgeois, Nicolas
Escoffier, Bruno
Paschos, Vangelis Th.
[J]. INFORMATION PROCESSING LETTERS, 2009, 109 (16) : 950 - 954
[8] Brankovic L, 2010, LECT NOTES COMPUT SC, V6506, P390, DOI 10.1007/978-3-642-17517-6_35
[9] Cai LM, 2006, LECT NOTES COMPUT SC, V4169, P96
[10] Chen YJ, 2006, LECT NOTES COMPUT SC, V4169, P109

← 1 2 3 4 →