An Algorithm for the Polyhedral Cycle Cover Problem with Constraints on the Number and Length of Cycles

Аннотация

A cycle cover of a graph is a spanning subgraph whose connected components are simple cycles. Given a complete weighted directed graph, consider the intractable problem of finding a maximum-weight cycle cover which satisfies an upper bound on the number of cycles and a lower bound on the number of edges in each cycle. We suggest a polynomial-time algorithm for solving this problem in the geometric case where the vertices of the graph are points in a multidimensional real space and the distances between them are induced by a positively homogeneous function whose unit ball is an arbitrary convex polytope with a fixed number of facets. The obtained result extends the ideas underlying the well-known algorithm for the polyhedral Max TSP.