| Texto completo | |
| Autor(es): |
Fernandes, Cristina G.
;
Lintzmayer, Carla N.
;
Moura, Phablo F. S.
Número total de Autores: 3
|
| Tipo de documento: | Artigo Científico |
| Fonte: | THEORETICAL COMPUTER SCIENCE; v. 1020, p. 16-pg., 2024-09-10. |
| Resumo | |
The STEINER MULTICYCLE problem consists in, given a complete graph, a weight function on its edges, and a collection of pairwise disjoint non-unitary sets called terminal sets, finding a minimum weight collection of vertex-disjoint cycles in the graph such that, for every terminal set, all of its vertices are in a same cycle of the collection. This problem generalizes the TRAVELING SALESMAN problem and, therefore, is hard to approximate in general. On the practical side, it models a collaborative less-than-truckload problem with pickup and delivery locations. Using an algorithm for the SURVIVABLE NETWORK DESIGN problem and T-joins, we obtain a 3approximation for the metric case, improving on the previous best 4-approximation. Furthermore, 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 to obtain a (7/6)-approximation when every terminal set contains at least four vertices. Finally, we devise an O(lg n )-approximation algorithm for the asymmetric version of the problem. (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 |