Expanding Neighborhood GRASP for the Traveling Salesman Problem

In this paper, we present the application of a modified version of the well known Greedy Randomized Adaptive Search Procedure (GRASP) to the TSP. The proposed GRASP algorithm has two phases: In the first phase the algorithm finds an initial solution of the problem and in the second phase a local search procedure is utilized for the improvement of the initial solution. The local search procedure employs two different local search strategies based on 2-opt and 3-opt methods. The algorithm was tested on numerous benchmark problems from TSPLIB. The results were very satisfactory and for the majority of the instances the results were equal to the best known solution. The algorithm is also compared to the algorithms presented and tested in the DIMACS Implementation Challenge that was organized by David Johnson.     

A restricted Lagrangean approach to the traveling salesman problem

We describe an algorithm for the asymmetric traveling salesman problem (TSP) using a new, restricted Lagrangean relaxation based on the assignment problem (AP). The Lagrange multipliers are constrained so as to guarantee the continued optimality of the initial AP solution, thus eliminating the need for repeatedly solving AP in the process of computing multipliers. We give several polynomially bounded procedures for generating valid inequalities and taking them into the Lagrangean function with a positive multiplier without violating the constraints, so as to strengthen the current lower bound. Upper bounds are generated by a fast tour-building heuristic. When the bound-strengthening techniques are exhausted without matching the upper with the lower bound, we branch by using two different rules, according to the situation: the usual subtour breaking disjunction, and a new disjunction based on conditional bounds. We discuss computational experience on 120 randomly generated asymmetric TSP's with up to 325 cities, the maximum time used for any single problem being 82 seconds. This is a considerable improvement upon earlier methods. Though the algorithm discussed here is for the asymmetric TSP, the approach can be adapted to the symmetric TSP by using the 2-matching problem instead of AP.Research supported by the National Science Foundation through grant no. MCS76-12026 A02 and the U.S. Office of Naval Research through contract no. N0014-75-C-0621 NR 047-048.     

Traveling wave solutions of harmonic heat flow

We prove the existence of a traveling wave solution of the equation in an infinitely long cylinder of radius R, which connects two locally stable and axially symmetric steady states at x ₃ = ±∞. Here u is a director field with values in The traveling wave has a singular point on the cylinder axis. Letting R→ ∞ we obtain a traveling wave defined in all space.     

Curved fronts in the Belousov–Zhabotinskii reaction–diffusion systems in R2

In this paper we consider a diffusion system with the Belousov–Zhabotinskii (BZ for short) chemical reaction. Following Brazhnik and Tyson [4] and Pérez-Muñuzuri et al. [45], who predicted V-shaped fronts theoretically and discovered V-shaped fronts by experiments respectively, we give a rigorous mathematical proof of their results. We establish the existence of V-shaped traveling fronts in ${\mathbb{R}}^2$ by constructing a proper supersolution and a subsolution. Furthermore, we establish the stability of the V-shaped front in ${\mathbb{R}}^2$.     

Exact Solitary Wave And Periodic Wave Solutions Of The Kaup-Kuperschmidt Equation

In this paper we investigate the exact traveling wave solutions of the fifth-order Kaup-Kuperschmidt equation. The bifurcation and exact solutions of a general first-order nonlinear equation are investigated firstly. With the help of Maple and by using the bifurcation and exact solutions of two derived subequations, we obtain two families of solitary wave solutions and two families of periodic wave solutions of the KK equation. The relationship of the two subequations and the two known rst integrals are analyzed.     

Qualitative behavior of numerical traveling solutions for reaction–diffusion equations with memory

In this article the qualitative properties of numerical traveling wave solutions for integro- differential equations, which generalize the well known Fisher equation are studied. The integro-differential equation is replaced by an equivalent hyperbolic equation which allows us to characterize the numerical velocity of traveling wave solutions. Numerical results are presented.     

Exponential approximation schemata for some network design problems

We study approximation of some well-known network design problems such as the traveling salesman problem (for both minimization and maximization versions) and the min steiner tree problem by moderately exponential algorithms. The general goal of the issue of moderately exponential approximation is to catch up on polynomial inapproximability by designing superpolynomial algorithms achieving approximation ratios unachievable in polynomial time. Worst-case running times of such algorithms are significantly smaller than those needed for optimal solutions of the problems handled.     

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.     

Accumulation and filtering of nanoparticles in microchannels using electrohydrodynamically induced vortical flows

We present an approach for the accumulation and filtering of nano- and microparticles in microfluidic devices that is based on the generation of electric traveling waves in the radio-frequency range. Upon application of the electric field via a microelectrode array, complex particle trajectories and particle accumulation are observed in well-defined regions in a microchannel. Through the quantitative mapping of the 3-D flow pattern using two-focus fluorescence cross-correlation spectroscopy, two vortices could be identified as one of the sources of the force field that induces the formation of particle clouds. Dielectrophoretic forces that directly act on the particles are the second source of the force field. A thorough 2-D finite element analysis identifies the electric traveling wave mechanism as the cause for the unexpected flow behavior observed. Based on these findings, strategies are discussed, first, for avoiding the vortices to optimize electrohydrodynamic micropumps and, secondly, for utilizing the vortices in the development of microdevices for efficient particle accumulation, separation, and filtering. Such devices may find numerous biomedical applications when highly diluted nano- and microsuspensions have to be processed.