Affordable Access

Publisher Website

Exponential approximation schemata for some network design problems

Authors
Journal
Journal of Discrete Algorithms
1570-8667
Publisher
Elsevier
Volume
22
Identifiers
DOI: 10.1016/j.jda.2013.06.011
Keywords
  • Exponential Algorithms
  • Approximation Algorithms
  • Steiner Tree
  • Traveling Salesman Problem
Disciplines
  • Computer Science
  • Design

Abstract

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.

There are no comments yet on this publication. Be the first to share your thoughts.