We consider some generalizations of the Asymmetric Traveling Salesman Path problem. Suppose we have an asymmetric metric G = (V,A) with two distinguished nodes s,t. We are also given a positive integer k. The goal is to find k paths of minimum total cost from s to t whose union spans all nodes. We call this the k-Person Asymmetric Traveling Salesmen Path problem (k-ATSPP). Our main result for k-ATSPP is a bicriteria approximation that, for some parameter b >= 1 we may choose, finds between k and k + k b paths of total length O(b log |V|) times the optimum value of an LP relaxation based on the Held-Karp relaxation for the Traveling Salesman problem. On one extreme this is an O(log |V|)-approximation that uses up to 2k paths and on the other it is an O(k log |V|)-approximation that uses exactly k paths. Next, we consider the case where we have k pairs of nodes (s_1,t_1), ..., (s_k,t_k). The goal is to find an s_i-t_i path for every pair such that each node of G lies on at least one of these paths. Simple approximation algorithms are presented for the special cases where the metric is symmetric or where s_i = t_i for each i. We also show that the problem can be approximated within a factor O(log n) when k=2. On the other hand, we demonstrate that the general problem cannot be approximated within any bounded ratio unless P = NP.
There is a linear programming (LP) relaxation for each of these problems based on the Held-Karp relaxation for TSP @cite_7 . For TSP, this relaxation is: [ ] Many of the approximation algorithms mentioned above also bound the integrality gap of the respective Held-Karp LP relaxation. For TSP, Wolsey @cite_0 proved the solutions found by Christofides' algorithm @cite_23 are within 3 2 of the optimal solution to the above LP relaxation. For ATSP, Williamson @cite_6 proved that the algorithm of Frieze @cite_8 bounds the integrality gap of its respective LP by @math . The improved @math -approximation for ATSP in @cite_15 improved the bound on gap to the same ratio. For TSP paths, An, Kleinberg and Shmoys @cite_14 first showed that Hoogeveen's algorithm bounds the integrality gap of a Held-Karp type relaxation for TSP paths by @math in cases where both endpoints are fixed. In the same paper they argue that their @math -approximation for this case also bounds the integrality gap by the same factor.
@cite_14 @cite_7 @cite_8 @cite_6 @cite_0 @cite_23 @cite_15
2295080441 2035610952 1877952604 1714357736 2117226423 1480355964
Electrophotographic recording material composed of a layer of selenium, selenium alloys, or selenium compounds, with arsenic as a additive, disposed on a conductive carrier is given improved properties by forming the layer to have a total arsenic content of 1 to 20 , by weight, and a concentration gradient such that the arsenic concentration decreases from the exposed surface of the layer in the direction toward the carrier and has a concentration of at least 13 at the exposed surface of the layer. We consider the asymmetric traveling salesman problem for which the triangular inequality is satisfied. For various heuristics we construct examples to show that the worst-case ratio of length of tour found to minimum length tour is (n) for n city problems. We also provide a new O([log2n]) heuristic. The Held-Karp heuristic for the Traveling Salesman Problem (TSP) has in practice provided near-optimal lower bounds on the cost of solutions to the TSP. We analyze the structure of Held-Karp solutions in order to shed light on their quality. In the symmetric case with triangle inequality, we show that a class of instances has planar solutions. We also show that Held-Karp solutions have a certain monotonicity property. This leads to an alternate proof of a result of Wolsey, which shows that the value of Held-Karp heuristic is always at least 2 3 OPT, where OPT is the cost of the optimum TSP tour. Additionally, we show that the value of the Held-Karp heuristic is equal to that of the linear relaxation of the biconnected-graph problem when edge costs are non-negative. In the asymmetric case with triangle inequality, we show that there are many equivalent definitions of the Held-Karp heuristic, which include finding optimally weighted 1-arborescences, 1-antiarborescences, asymmetric 1-trees, and assignment problems. We prove that monotonicity holds in the asymmetric case as well. These theorems imply that the value of the Held-Karp heuristic is no less than OPT and no less than the value of the Balas-Christofides heuristic for the asymmetric TSP. For the 1,2-TSP, we show that the Held-Karp heuristic cannot do any better than 9 10 OPT, even as the number of nodes tends to infinity. Portions of this thesis are joint work with David Shmoys. We consider two questions arising in the analysis of heuristic algorithms. (i) Is there a general procedure involved when analysing a particular problem heuristic? (ii) How can heuristic procedures be incorporated into optimising algorithms such as branch and bound? Abstract : An O(n sup 3) heuristic algorithm is described for solving n-city travelling salesman problems (TSP) whose cost matrix satisfies the triangularity condition. The algorithm involves as substeps the computation of a shortest spanning tree of the graph G defining the TSP, and the finding of a minimum cost perfect matching of a certain induced subgraph of G. A worst-case analysis of this heuristic shows that the ratio of the answer obtained to the optimum TSP solution is strictly less than 3 2. This represents a 50 reduction over the value 2 which was the previously best known such ratio for the performance of other polynomial-growth algorithms for the TSP.