A. Adir, E. Bin, et al.
HLDVT 2003
A directed multigraph is said to be d-regular if the indegree and outdegree of every vertex is exactly d. By Hall's theorem, one can represent such a multigraph as a combination of at most n 2 cycle covers, each taken with an appropriate multiplicity. We prove that if the d-regular multigraph does not contain more than [dβ2] copies of any 2-cycle then we can find a similar decomposition into n 2 pairs of cycle covers where each 2-cycle occurs in at most one component of each pair. Our proof is constructive and gives a polynomial algorithm to find such a decomposition. Since our applications only need one such a pair of cycle covers whose weight is at least the average weight of all pairs, we also give an alternative, simpler algorithm to extract a single such pair. This combinatorial theorem then comes handy in rounding a fractional solution of an LP relaxation of the maximum Traveling Salesman Problem (TSP) problem. The first stage of the rounding procedure obtains two cycle covers that do not share a 2-cycle with weight at least twice the weight of the optimal solution. Then we show how to extract a tour from the 2 cycle covers, whose weight is at least 2/3 of the weight of the longest tour. This improves upon the previous 5/8 approximation with a simpler algorithm. Utilizing a reduction from maximum TSP to the shortest superstring problem, we obtain a 2.5-approximation algorithm for the latter problem, which is again much simpler than the previous one. For minimum asymmetric TSP, the same technique gives two cycle covers, not sharing a 2-cycle, with weight at most twice the weight of the optimum. Assuming triangle inequality, we then show how to obtain from this pair of cycle covers a tour whose weight is at most 0.842 log 2 n larger than optimal. This improves upon a previous approximation algorithm with approximation guarantee of 0.999 log2 n. Other applications of the rounding procedure are approximation algorithms for maximum 3-cycle cover (factor 2/3, previously 3/5) and maximum asymmetric TSP with triangle inequality (factor 10/13, previously 3/4). © 2005 ACM.
A. Adir, E. Bin, et al.
HLDVT 2003
Alain Vaucher, Philippe Schwaller, et al.
AMLD EPFL 2022
Ankit Vishnubhotla, Charlotte Loh, et al.
NeurIPS 2023
Hannaneh Hajishirzi, Julia Hockenmaier, et al.
UAI 2011