Approximations for the Steiner Multicycle Problem

Autor(es)

Fernandes, Cristina G. ; Lintzmayer, Carla N. ; Moura, Phablo F. S.

• Tipo de documento: Artigo Científico
• Fonte: LATIN 2022: THEORETICAL INFORMATICS; v. 13568, p. 16-pg., 2022-01-01.

Resumo

The Steiner Multicycle problem consists in, given a complete graph G, a weight function w: E(G) -> Q(+), and a partition of V (G) into terminal sets, finding a minimum-weight collection of disjoint cycles in G such that, for every terminal set T, all vertices of T are in a same cycle of the collection. This problem, which is motivated by applications on routing problems with pickup and delivery locations, generalizes the TRAVELING SALESMAN PROBLEM (TSP) and therefore is hard to approximate in general. Using an algorithm for the SURVIVABLE NETWORK DESIGN problem and T-joins, we obtain a 3-approximation for its metric case, improving on the previous best 4-approximation. Furthermore, inspired by a result by Papadimitriou and Yannakakis for the {1, 2}-TSP, we present an (11/9)-approximation for the particular case of the STEINER MULTICYCLE in which each edge weight is 1 or 2. This algorithm can be adapted into a (7/6)-approximation when every terminal set contains at least 4 vertices. (AU)

• Processo FAPESP: 19/13364-7 - Problemas extremais e estruturais em teoria dos grafos
• Beneficiário: Cristina Gomes Fernandes
• Modalidade de apoio: Auxílio à Pesquisa - Regular