Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
430867 | Journal of Discrete Algorithms | 2013 | 10 Pages |
Abstract
We study approximation of some well-known network design problems such as the traveling salesman problem (for both minimization and maximization versions) and the min steiner tree problem by moderately exponential algorithms. The general goal of the issue of moderately exponential approximation is to catch up on polynomial inapproximability by designing superpolynomial algorithms achieving approximation ratios unachievable in polynomial time. Worst-case running times of such algorithms are significantly smaller than those needed for optimal solutions of the problems handled.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Nicolas Boria, Nicolas Bourgeois, Bruno Escoffier, Vangelis Th. Paschos,