Average-case approximation ratio of the 2-opt algorithm for the TSP

We show that the 2-opt heuristic for the traveling salesman problem achieves an expected approximation ratio of roughly for instances with n nodes, where the edge weights are drawn uniformly and independently at random.     

On the integrality ratio of the subtour LP for Euclidean TSP

A long standing conjecture says that the integrality ratio of the subtour LP for metric TSP is 4/3$4/3$. A well known family of graphic TSP instances achieves this lower bound asymptotically. For Euclidean TSP the best known lower bound on the integrality ratio was 8/7$8/7$. We improve this value by presenting a family of Euclidean TSP instances for which the integrality ratio of the subtour LP converges to 4/3.     

An improved approximation algorithm for the asymmetric TSP with strengthened triangle inequality

We consider the asymmetric traveling salesperson problem with γ-parameterized triangle inequality for γ[1/2,1). That means, the edge weights fulfill w(u,v)γ(w(u,x)+w(x,v)) for all nodes u,v,x. Chandran and Ram [L.S. Chandran, L.S. Ram, Approximations for ATSP with parametrized triangle inequality, in: Proc. 19th Int. Symp. on Theoret. Aspects of Comput. Sci. (STACS), in: Lecture Notes in Comput. Sci., vol. 2285, Springer, Berlin, 2002, pp. 227–237] gave the first constant factor approximation algorithm with polynomial running time for this problem. They achieve performance ratio γ/(1−γ). We devise an approximation algorithm with performance ratio (1+γ)/(2−γ−γ³), which is better for γ[0.5437,1), that is, for the particularly interesting large values of γ.     

An improved approximation ratio for the minimum latency problem

Given a tour visitingn points in a metric space, thelatency of one of these pointsp is the distance traveled in the tour before reachingp. Theminimum latency problem (MLP) asks for a tour passing throughn given points for which the total latency of then points is minimum; in effect, we are seeking the tour with minimum average arrival time. This problem has been studied in the operations research literature, where it has also been termed the delivery-man problem and the traveling repairman problem. The approximability of the MLP was first considered by Sahni and Gonzalez in 1976; however, unlike the classical traveling salesman problem (TSP), it is not easy to give any constant-factor approximation algorithm for the MLP. Recently, Blum et al. (A. Blum, P. Chalasani, D. Coppersimith, W. Pulleyblank, P. Raghavan, M. Sudan, Proceedings of the 26th ACM Symposium on the Theory of Computing, 1994, pp. 163–171) gave the first such algorithm, obtaining an approximation ratio of 144. In this work, we develop an algorithm which improves this ratio to 21.55; moreover, combining our algorithm with a recent result of Garg (N. Garg, Proceedings of the 37th IEEE Symposium on Foundations of Computer Science, 1996, pp. 302–309) provides an approximation ratio of 10.78. The development of our algorithm involves a number of techniques that seem to be of interest from the perspective of the TSP and its variants more generally. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Supported by NSF contract 9302476-CCR and an NEC research grant.Author supported by an ONR Graduate Fellowship.     

Metric Diophantine approximation over a local field of positive characteristic

The conjectures of Sprind?uk in the metric theory of Diophantine approximation are established over a local field of positive characteristic. In the real case, these were settled by D. Kleinbock and G.A. Margulis using a new technique which involved nondivergence estimates for quasi-polynomial flows on the space of lattices. We extend their technique to the positive characteristic setting.     

Bounding the piercing number

It is shown that for everyk and everyp≥q≥d+1 there is ac=c(k,p,q,d)<∞ such that the following holds. For every familyℋ whose members are unions of at mostk compact convex sets inR ^d in which any set ofp members of the family contains a subset of cardinalityq with a nonempty intersection there is a set of at mostc points inR ^d that intersects each member ofℋ. It is also shown that for everyp≥q≥d+1 there is aC=C(p,q,d)<∞ such that, for every family of compact, convex sets inR ^d so that among andp of them someq have a common hyperplane transversal, there is a set of at mostC hyperplanes that together meet all the members of . This research was supported in part by a United States-Israel BSF Grant and by the Fund for Basic Research administered by the Israel Academy of Sciences.     

Metric results on the approximation of zero by linear combinations of independent and of dependent rationals

We give some “rational analoga” to metric results in the classical theory of the diophantine approximation of zero by linear forms. That is: we study the behaviour of expressions of the form $$\begin{gathered} \lim _{m \to \infty } \frac{1}{{\left| {P_s (m)} \right|}}|\{ (x_1 , \ldots ,x_s ) \in P_s (m): \hfill \\ \parallel a_1 \frac{{x_1 }}{m} + \ldots + a_s \frac{{x_s }}{m}\parallel _m \geqslant \psi (a_1 , \ldots ,a_s ,m) \hfill \\ for all - \frac{m}{2}< a_1 , \ldots ,a_s \leqslant \frac{m}{2}, \hfill \\ with (a_1 , \ldots ,a_s ) \ne (0, \ldots ,0)\} |, \hfill \\ \end{gathered} $$ whereP _s (m) is a certain subset of {1, …,m} ^s , ψ is a certain nonnegative function, and ‖ · ‖ _m means the maximum of 1/m and the distance to the nearest integer. Some of the investigations are also motivated by problems in the theory of uniform distribution and of pseudo-random number generation. The results partly depend on the validity of the generalized Riemann hypothesis.     

Construction heuristics for the asymmetric TSP

Non-Euclidean traveling salesman problem (TSP) construction heuristics, and especially asymmetric TSP construction heuristics, have been neglected in the literature by comparison with the extensive efforts devoted to studying Euclidean TSP construction heuristics. This state of affairs is at odds with the fact that asymmetric models are relevant to a wider range of applications, and indeed are uniformly more general that symmetric models. Moreover, common construction approaches for the Euclidean TSP have been shown to produce poor quality solutions for non-Euclidean instances. Motivation for remedying this gap in the study of construction approaches is increased by the fact that such methods are a great deal faster than other TSP heuristics, which can be important for real time problems requiring continuously updated response. The purpose of this paper is to describe two new construction heuristics for the asymmetric TSP and a third heuristic based on combining the other two. Extensive computational experiments are performed for several different families of TSP instances, disclosing that our combined heuristic clearly outperforms well-known TSP construction methods and proves significantly more robust in obtaining (relatively) high quality solutions over a wide range of problems.     

Bounding Distributions for Stochastic Logic Networks

A stochastic logic network is defined as a connected set of logic and time delay elements. Each of the latter elements has an associated probability distribution describing the nature of that element's delay. When used, for example, in project planning and scheduling, combinations of logic and time delay elements in such networks may represent conditions for the starting of project activities which are themselves represented by time delay elements. It is at present not known how to calculate the probability distributions for the events in such a network. This paper shows how to obtain upper and lower bounds for these probability distributions. The method is not a simulation technique; rather, it is a straightforward computational scheme derived from elementary probability theory. An example is given where the method is applied to a stochastic project scheduling network in which alternative ways exist for carrying out one of the jobs in the network.     

Four-point conditions for the TSP: The complete complexity classification

The combinatorial optimization literature contains a multitude of polynomially solvable special cases of the traveling salesman problem (TSP) which result from imposing certain combinatorial restrictions on the underlying distance matrices. Many of these special cases have the form of so-called four-point conditions: inequalities that involve the distances between four arbitrary cities.In this paper we classify all possible four-point conditions for the TSP with respect to computational complexity, and we determine for each of them whether the resulting special case of the TSP can be solved in polynomial time or whether it remains NP-hard.     

用遗传算法求解分组旅行推销员问题

在遗传算法能够有效解决TSP问题的基础上，根据遗传算法——通过搜索大规模，多样化的种群，在种群间交换个体所携带的遗传信息，保留种群中个体的优越遗传信息——的思想，设计了求解分组TSP问题的遗传算法。算法中染色体表示、评价函数的构造、杂交变异算子的设计经过实例计算的检验被证明较为可靠；算法运算速度快，容易获得有效解。     

Bounding strategies for the hybrid flow shop scheduling problem

In this paper, we investigate new lower and upper bounds for the multiple-center hybrid flow shop scheduling problem. We propose a family of center-based lower bounds as well as a destructive lower bound that is based on the concept of revised energetic reasoning. Also, we describe an optimization-based heuristic that requires iteratively solving a sequence of parallel machine problems with heads and tails. We present the results of extensive computational experiments that provide evidence that the proposed bounding procedures consistently improve the best existing ones.     

A polynomial algorithm with approximation ratio 7/9 for the maximum two peripatetic salesmen problem

Under study is the maximum 2 peripatetic salesmen problem which consists in finding two edge-disjoint Hamiltonian cycles with maximal total weight in a complete undirected graph. We present a cubic time approximation algorithm for this problem with the performance guarantee 7/9 which is the best known estimation by now. We also present a modification of this algorithm for the case when the weights of graph edges are values in a given range [1, q] with the performance guarantee (7q + 3)/(9q + 1) which is also the best known estimation by now and has cubic time complexity too.     

Approximation algorithms for the Euclidean bipartite TSP

We study approximation results for the Euclidean bipartite traveling salesman problem (TSP). We present the first worst-case examples, proving that the approximation guarantees of two known polynomial-time algorithms are tight. Moreover, we propose a new algorithm which displays a superior average case behavior indicated by computational experiments.