Differential approximation results for the Steiner tree problem

DOI10.1016/S0893-9659(03)00075-2zbMath1046.90096MaRDI QIDQ1431874

Vangelis Th. Paschos, Jérôme Monnot, Marc Demange

Publication date: 11 June 2004

Published in: Applied Mathematics Letters (Search for Journal in Brave)

zbMATH Keywords

AlgorithmsComplexityalgorithmical approximation

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Trees (05C05) Abstract computational complexity for mathematical programming problems (90C60) Approximation algorithms (68W25)

Related Items

Differential approximation of NP-hard problems with equal size feasible solutions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The Steiner problem with edge lengths 1 and 2
• Optimization, approximation, and complexity classes
• On an approximation measure founded on the links between optimization and polynomial approximation theory
• New approximation algorithms for the Steiner tree problems
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• An 11/6-approximation algorithm for the network Steiner problem
• Improved Approximations for the Steiner Tree Problem