Tight bounds for christofides' traveling salesman heuristic

Christofides [1] proposes a heuristic for the traveling salesman problem that runs in polynomial time. He shows that when the graphG = (V, E) is complete and the distance matrix defines a function onV × V that is metric, then the length of the Hamiltonian cycle produced by the heuristic is always smaller than 3/2 times the length of an optimal Hamiltonian cycle. The purpose of this note is to refine Christofides' worst-case analysis by providing a tight bound for everyn 3, wheren is the number of vertices of the graph. We also show that these bounds are still tight when the metric is restricted to rectilinear distances, or to Euclidean distances for alln 6.This work was supported, in part, by NSF Grant ENG 75-00568 to Cornell University. This work was done when the authors were affiliated with the Center for Operations Research and Econometrics, University of Louvain, Belgium.     

Statistical mechanics of a dynamical system based on Conway's game of Life

We study a discrete dynamical system whose evolution is governed by rules similar to those of Conway's game of Life but also include a stochastic element (parametrized by a temperature). Statistical properties that are examined are density as a function of temperature and entropy (suitably defined). A phase transition and a certain thermodynamic constant of the motion are observed.Lady Davis Visiting Scientist at the Technion 1974–75.     

A variable dimension algorithm for the linear complementarity problem

A variable dimension algorithm is presented for the linear complementarity problems – Mz = q; s,z 0; s _i z _i = 0 fori = 1,2, ,n. The algorithm solves a sequence of subproblems of different dimensions, the sequence being possibly nonmonotonic in the dimension of the subproblem solved. Every subproblem is the linear complementarity problem defined by a leading principal minor of the matrixM. Index-theoretic arguments characterize the points at which nonmonotonic behavior occurs.     

Cost operator algorithms for the transportation problem

A primal transportation algorithm is devised via post-optimization on the costs of a modified problem. The procedure involves altering the costs corresponding to the basic cells of the initial (primal feasible) solution so that it is dual feasible as well. The altered costs are then successively restored to their true values with appropriate changes in the optimal solution by the application of cell or area cost operators discussed elsewhere. The cell cost operator algorithm converges to optimum within (2T – 1) steps for primal nondegenerate transportation problems and [(2T + 1) min (m, n)] – 1 steps for primal degenerate transportation problems, whereT is the sum of the (integer) warehouse availabilities (also the sum of the (integer) market requirements) andm andn denote the number of warehouses and markets respectively. For the area cost operator algorithm the corresponding bounds on the number of steps areT and (T + 1) min (m, n) respectively.This report was prepared as part of the activities of the Management Sciences Research Group, Carnegie—Mellon University, under Contract N00014-67-A-0314-0007 NR 047-048 with the U.S. Office of Naval Research.     

Computer-assisted choice of discrete spacers for anionic isotachophoresis separations

In isotachophoresis (ITP), the sample constituents migrate, depending on their concentrations in the loaded sample, either in fully developed zones or in the boundary layers between the zones of constituents of the corresponding effective mobilities. The latter (spike) migration mode is analytically beneficial in selective detections of trace analytes, especially, when appropriately chosen discrete spacers minimize detection interferences due to matrix constituents. To facilitate a search for suitable mixtures of discrete spacers, a two-step calculation procedure was developed in this work. Using a pool of discrete spacers consisting of 42 anionic and zwitterionic constituents, this procedure was shown effective in the anionic ITP separations performed at pH = 6.5-10.0. Besides the predictions of the migration orders, it was helpful in identifying the spacing constituents that could cause resolution problems due to an uncertainty with which pH of the leading electrolyte solution is known. The ionic mobility and pKa data, taken for the spacing constituents from the literature and the ones obtained from the ITP experiments carried out in this work, were used in the calculations performed in a context with the choice of spacers. Although the data obtained from the ITP experiments provided better results, small uncertainties with which they were acquired (attributable to fluctuations in the experimental conditions) set practical limits in the calculation based choice of multi-component mixtures of the spacing constituents.     

The discrete Gaussian chain with 1/r n interactions: Exact results

We show that the discrete Gaussian chain with interactionV(r) = 1/(r ²–1/4) is self-dual. At the dual temperaturek _B T = 1 we calculate the height-height correlation function and find that the system is rough. A duality relation is established for the temperature-dependent correlation function exponent. We also consider interactionsV(r)–1/r ⁿ and show that absence of a phase transition for 2 <n < 3 implies absence of a phase transition for 1 <n < 2. All these results have their counterparts in a linear system of charges interacting through a potential which is asymptotically logarithmic (forn = 2) or power-law-like (forn 2.On leave of absence from Chemistry Laboratory III, Universitetsparken 5, 2100 ©, Copenhagen, Denmark.     

On the symmetric travelling salesman problem I: Inequalities

We investigate several classes of inequalities for the symmetric travelling salesman problem with respect to their facet-defining properties for the associated polytope. A new class of inequalities called comb inequalities is derived and their number shown to grow much faster with the number of cities than the exponentially growing number of subtour-elimination constraints. The dimension of the travelling salesman polytope is calculated and several inequalities are shown to define facets of the polytope. In part II (On the travelling salesman problem II: Lifting theorems and facets) we prove that all subtour-elimination and all comb inequalities define facets of the symmetric travelling salesman polytope.     

Computational complexity of LCPs associated with positive definite symmetric matrices

Murty in a recent paper has shown that the computational effort required to solve a linear complementarity problem (LCP), by either of the two well known complementary pivot methods is not bounded above by a polynomial in the size of the problem. In that paper, by constructing a class of LCPs—one of ordern forn 2—he has shown that to solve the problem of ordern, either of the two methods goes through 2 ⁿ pivot steps before termination.However that paper leaves it as an open question to show whether or not the same property holds if the matrix,M, in the LCP is positive definite and symmetric. The class of LCPs in whichM is positive definite and symmetric is of particular interest because of the special structure of the problems, and also because they appear in many practical applications.In this paper, we study the computational growth of each of the two methods to solve the LCP, (q, M), whenM is positive definite and symmetric and obtain similar results.This research is partially supported by Air Force Office of Scientific Research, Air Force Number AFOSR-78-3646. The United States Government is authorized to reproduce and distribute reprints for governmental purposes notwithstanding any copyright notation thereon.     

Impulsive generalized function synchronization of complex dynamical networks

This Letter investigates generalized function synchronization of continuous and discrete complex networks by impulsive control. By constructing the reasonable corresponding impulsively controlled response networks, some criteria and corollaries are derived for the generalized function synchronization between the impulsively controlled complex networks, continuous and discrete networks are both included. Furthermore, the generalized linear synchronization and nonlinear synchronization are respectively illustrated by several examples. All the numerical simulations demonstrate the correctness of the theoretical results.     

Application of DEM modified with enlarged particle model to simulation of bead motion in a bead mill

We applied the discrete element method （DEM） of simulation modified by an enlarged particle model to simulate bead motion in a large bead mill. The stainless-steel bead mill has inner diameter of 102 mm and mill length of 198 mm. The bead diameter and filling ratio were fixed respectively at 0.5 mm and 85%. The agitator rotational speed was changed from 1863 to 3261 rpm. The bead motion was monitored experimentally using a high-speed video camera through a transparent mill body. For the simulation, enlarged particle sizes were set as 3-6 mm in diameter. With the DEM modified by the enlarged particle model, the motion of enlarged particles in a mill was simulated.The velocity data of the simulated enlarged particles were compared with those obtained in the experiment. The simulated velocity of the enlarged particles depends on the virtual frictional coefficient in the DEM model. The optimized value of the virtual frictional coefficient can be determined by considering the accumulated mean value. Results show that the velocity of the enlarged particles simulated increases with an increase in the optimum virtual frictional coefficient, but the simulated velocity agrees well with that determined experimentally by optimizing the virtual frictional coefficient in the simulation. The computing time in the simulation decreases with increased particle size.