Differential approximation results for the Steiner tree problem

作     者：Demange, M Monnot, J Paschos, VT 

作者机构：ESSEC Informat & Decis Syst Dept F-95021 Cergy Pontoise France Univ Paris 09 LAMSADE F-75775 Paris 16 France 

出 版 物：《APPLIED MATHEMATICS LETTERS》 (应用数学快报)

年 卷 期：2003年第16卷第5期

页      面：733-739页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主　　题：algorithmical approximation algorithms complexity 

摘      要：We study the approximability of three versions of the Steiner tree problem. For the first one where the input graph is only supposed connected, we show that it is not approximable within better than \V\N\(-epsilon) for any epsilon is an element of (0, 1), where V and N are the vertex-set of the input graph and the set of terminal vertices, respectively. For the second of the Steiner tree versions considered, the one where the input graph is supposed complete and the edge distances are arbitrary, we prove that it can be differentially approximated within 1/2. For the third one defined on complete graphs with edge distances 1 or 2, we show that it is differentially approximable within 0.82. Also, extending the result of Bern and Plassmann [1], we show that the Steiner tree problem with edge lengths 1 and 2 is MaxSNP-complete even in the case where \V\ less than or equal to r\N\, for any r 0. This allows us to finally show that the Steiner tree problem with edge lengths 1 and 2 cannot by approximated by polynomial time differential approximation schemata. (C) 2003 Elsevier Science Ltd. All rights reserved.