Approximability of the Minimum Steiner Cycle Problem

Authors

  • Monika Steinová

Keywords:

Approximation, TSP, Steiner tree, terminals, cycle

Abstract

In this paper, we consider variants of a new problem that we call minimum Steiner cycle problem (SCP). The problem is defined as follows. Given is a weighted complete graph and a set of terminal vertices. In the SCP problem, we are looking for a minimum-cost cycle that passes through every terminal exactly once and through every other vertex of the graph at most once. We show that, if P<>NP, there is no approximation algorithm for SCP on directed graphs with an approximation ratio polynomial in the input size. Moreover, this result holds even in the case when the number of terminals is 4. On the contrary, we show that SCP on undirected graphs with constant number of terminals and edge costs satisfying the beta-relaxed triangle inequality is approximable with the ratio beta^2+beta. When the number of terminals k is a part of the input, the problem is obviously a generalization of TSP. For the metric case, we present a 3/2- and a 2/3 log_2 k-approximation algorithm for undirected and directed graphs G=(V,E), respectively. For the case with the beta-relaxed triangle inequality, we present a (beta^2+beta)-approximation algorithm.

Downloads

Download data is not yet available.

Author Biography

Monika Steinová

ETH Zurich
Informationstechnologie und Ausbildung
CAB F 13.1
Universitatsstrasse 6
8092 Zurich, Switzerland

Downloads

Published

2012-01-26

How to Cite

Steinová, M. (2012). Approximability of the Minimum Steiner Cycle Problem. Computing and Informatics, 29(6+), 1349–1357. Retrieved from http://147.213.75.17/ojs/index.php/cai/article/view/148