Sigma–delta quantization errors and the traveling salesman problem

In transmission, storaging and coding of digital signals we frequently perform A/D conversion using quantization. In this paper we study the maximal and mean square errors as a result of quantization. We focus on the sigma–delta modulation quantization scheme in the finite frame expansion setting. We show that this problem is related to the classical Traveling Salesman Problem (TSP) in the Euclidean space. It is known [Benedetto et al., Sigma–delta () quantization and finite frames, IEEE Trans. Inform. Theory 52, 1990–2005 (2006)] that the error bounds from the sigma–delta scheme depends on the ordering of the frame elements. By examining a priori bounds for the Euclidean TSP we show that error bounds in the sigma–delta scheme is superior to those from the pulse code modulation (PCM) scheme in general. We also give a recursive algorithm for finding an ordering of the frame elements that will lead to good maximal error and mean square error. Supported in part by the National Science Foundation grant DMS-0139261.     

Existence of traveling wave solutions of a high-order nonlinear acoustic wave equation

In this Letter, we present an analytical study of a high-order acoustic wave equation in one dimension, and reformulate a previously given equation in terms of an expansion of the acoustic Mach number. We search for non-trivial traveling wave solutions to this equation, and also discuss the accuracy of acoustic wave equations in terms of the range of Mach numbers for which they are valid.     

Revisiting dynamic programming for precedence-constrained traveling salesman problem and its time-dependent generalization

The precedence constrained traveling salesman problem (TSP-PC), or the sequential ordering problem (SOP), consists of finding an optimal TSP tour that will also satisfy the namesake precedence constraints, typically specified as a partial order or a directed acyclic graph. Its dynamic programming (DP) solution was proposed as early as 1979, however, by late 1990s, it mostly fell out of use in plain TSP-PC. Revisiting this method, we are able to close one of the long-standing TSPLIB SOP problem instances, ry48p.3.sop, and provide improved bounds on its time complexity. Harnessing the “omnivorous” nature of DP, we prove the validity of DP optimality principle for TSP-PC with both (i) abstract cost aggregation function, which may be the arithmetic + operation as in “ordinary” TSP or $\max$ as in Bottleneck TSP, or any other left-associative nondecreasing in the first argument operation and (ii) travel cost functions depending on the set of pending tasks (“sequence dependence”). Using the latter generalization, we close several TD-SOP (time-dependent TSP-PC) instances based on TSPLIB SOP as proposed by Kinable et al., including rbg253a.sop. Through the restricted DP heuristic, which was originally formulated for time-dependent TSP by Malandraki and Dial, we improve the state-of-the-art upper bounds for all yet unsolved TSPLIB-based TD-SOP instances, including those with more than 100 cities. We also improve worst-case complexity estimates for DP in TSP-PC.     

Blow-up solution near the traveling waves for the second-order Camassa–Holm equation

This paper studies the blow-up solution and its blow-up rate near the traveling waves of the second-order Camassa–Holm equation. The sufficient condition for the existence of blow-up solution is obtained by a rather ingenious method. Applying the extended pseudo-conformal transformation, an equivalent proposition of the solution breaking in finite time near the traveling waves is constructed. The relation is established between the blow-up time and rate of the solution and the residual’s.     

Mathematical modeling and numerical simulation of domain wall motion in magnetic nanostrips with crystallographic defects

We investigate field and current driven domain wall propagation in magnetic nanostrips in the framework of the modified Landau–Lifshitz–Gilbert equation including spin-torque effects. We focus our attention on a nonlinear “dry-friction” dissipation model useful for describing the effect of structural defects such as inclusions, impurities or dislocations. The analytical and numerical results herein obtained are compared and their physical implications are discussed.     

On single courier problem

A new set of NP problems defined as Courier Problems that is motivated from the requirements in railway wagon scheduling is proposed. The general version includes many mobile couriers. The simplest version of this will consider a single courier. An algorithm to transform the single courier problem into a traveling salesman problem is presented.     

A new lower bound for the geometric traveling salesman problem in terms of discrepancy

We give a new lower bound for the shortest hamiltonian path through n points of [0,1]^d in terms of the discrepancy of these n points. This improves an earlier result by Steele.     

A note on the relationship between the graphical traveling salesman polyhedron, the Symmetric Traveling Salesman Polytope, and the metric cone

In this short communication, we observe that the Graphical Traveling Salesman Polyhedron is the intersection of the positive orthant with the Minkowski sum of the Symmetric Traveling Salesman Polytope and the polar of the metric cone. This follows almost trivially from known facts. There are nonetheless two reasons why we find this observation worth communicating: It is very surprising; it helps us understand the relationship between these two important families of polyhedra.