The Vehicle Routing Problem with Demand Range

We propose and formulate the vehicle routing problem with demand range (VRPDR), a new variation on the traditional vehicle routing problem. In the VRPDR, the delivery quantity for each customer i is allowed to vary from its original size d _i by an amount α d _i where 0 ≤ α < 1. In adding this limited flexibility to the problem, there is potential to generate significant savings in the total distance traveled. We address issues such as bounding the impact of a given α on total distance and provide empirical results to illustrate “typical” behavior.     

Duality for optimization and best approximation over finite intersections

Recently Deutsch, Li and Swetits [2] have studied, in Hilbert space, a dual problem (Q_m ) to the primal problem (P) of minimization of a special class of convex functions f over the intersection of m closed convex sets, where m is finite. In the first part of this paper we obtain, in a locally convex space, some results on problem (Q_m ) and on its relations with the usual Lagrangian dual problem (Q) to (P) (studied in [9]), in the case when (P) has a solution. In the second part we give some applications to duality for the distance to the intersection of m closed convex sets in a normed linear space, in the case when a nearest point exists. Most of our results seem to be new even in the particular cases studied in [9] (the case m = 1), [l] (duality formulas for the distance to the intersection of m closed half-spaces in a normed linear space) and [2].     

Skew codes of prescribed distance or rank

In this paper we generalize the notion of cyclic code and construct codes as ideals in finite quotients of non-commutative polynomial rings, so called skew polynomial rings of automorphism type. We propose a method to construct block codes of prescribed rank and a method to construct block codes of prescribed distance. Since there is no unique factorization in skew polynomial rings, there are much more ideals and therefore much more codes than in the commutative case. In particular we obtain a [40, 23, 10]₄ code by imposing a distance and a [42,14,21]₈ code by imposing a rank, which both improve by one the minimum distance of the previously best known linear codes of equal length and dimension over those fields. There is a strong connection with linear difference operators and with linearized polynomials (or q-polynomials) reviewed in the first section.      

The Guessing Secrets problem: a probabilistic approach

We introduce a probabilistic variant of the Guessing Secrets problem proposed by Chung et al. in [Electron. J. Combin. 8 (2001) R13]. In our variation, a player tries to discover the identity of a set S of n unknown secrets drawn by a second player, from a space Ω of N secrets. The first player tries to learn as much as possible about the elements of S by asking binary questions. For each question asked, the second player randomly chooses one of the n secrets of S that he uses in supplying the answer, which in any case must be truthful. We define a simple probabilistic guessing algorithm that allows us to guess all secrets of S with probability one. We show that the expected number of questions needed to guess all secrets is 2n²log₂N and the expected time complexity of the algorithm is . We also propose a generalization of this probabilistic guessing secrets problem, and provide some similar results for this generalization.     

Multiple pickup and delivery traveling salesman problem with last-in-first-out loading and distance constraints

We extend the traveling salesman problem with pickup and delivery and LIFO loading (TSPPDL) by considering two additional factors, namely the use of multiple vehicles and a limitation on the total distance that a vehicle can travel; both of these factors occur commonly in practice. We call the resultant problem the multiple pickup and delivery traveling salesman problem with LIFO loading and distance constraints (MTSPPD-LD). This paper presents a thorough preliminary investigation of the MTSPPD-LD. We propose six new neighborhood operators for the problem that can be used in search heuristics or meta-heuristics. We also devise a two-stage approach for solving the problem, where the first stage focuses on minimizing the number of vehicles required and the second stage minimizes the total travel distance. We consider two possible approaches for the first stage (simulated annealing and ejection pool) and two for the second stage (variable neighborhood search and probabilistic tabu search). Our computational results serve as benchmarks for future researchers on the problem.     

A differential game with two pursuers and one evader

This paper is concerned with a coplanar pursuit-evasion problem in which a faster evaderE with constant speedw>1 must pass between two pursuersP ₁,P ₂ having unit speed, the payoff being the distance of closest approach to either one of the pursuers. The control variables are the directions of the velocities ofP ₁,P ₂, andE. The path equations are integrated, and a closed-form solution is obtained in terms of elliptic functions of the first and second kind. A closed-loop solution is given graphically in several diagrams, for different values ofw.     

Minimum disparity estimation for continuous models: Efficiency,distributions and robustness

A general class of minimum distance estimators for continuous models called minimum disparity estimators are introduced. The conventional technique is to minimize a distance between a kernel density estimator and the model density. A new approach is introduced here in which the model and the data are smoothed with the same kernel. This makes the methods consistent and asymptotically normal independently of the value of the smoothing parameter; convergence properties of the kernel density estimate are no longer necessary. All the minimum distance estimators considered are shown to be first order efficient provided the kernel is chosen appropriately. Different minimum disparity estimators are compared based on their characterizing residual adjustment function (RAF); this function shows that the robustness features of the estimators can be explained by the shrinkage of certain residuals towards zero. The value of the second derivative of theRAF at zero,A ₂, provides the trade-off between efficiency and robustness. The above properties are demonstrated both by theorems and by simulations.     

Study of generalized eigenfunctions of a perturbed isotropic elastic half‐space

We consider the self‐adjoint operator governing the propagation of elastic waves in a perturbed isotropic half‐space (perturbation with compact support of a homogeneous isotropic half‐space) with a free boundary condition. We propose a method to obtain, numerical values included, a complete set of generalized eigenfunctions that diagonalize this operator. The first step gives an explicit representation of these functions using a perturbative method. The unbounded boundary is a new difficulty compared with the method used by Wilcox [25], who set the problem in the complement of bounded open set. The second step is based on a boundary integral equations method which allows us to compute these functions. For this, we need to determine explicitly the Green's function of (A₀ – ω²), where A₀ is the self‐adjoint operator describing elastic waves in a homogeneous isotropic half‐space. Copyright © 2000 John Wiley & Sons, Ltd.     

A second order accuracy for a full discretized time-dependent Navier–Stokes equations by a two-grid scheme

We study a second-order two-grid scheme fully discrete in time and space for solving the Navier–Stokes equations. The two-grid strategy consists in discretizing, in the first step, the fully non-linear problem, in space on a coarse grid with mesh-size H and time step Δt and, in the second step, in discretizing the linearized problem around the velocity u _H computed in the first step, in space on a fine grid with mesh-size h and the same time step. The two-grid method has been applied for an analysis of a first order fully-discrete in time and space algorithm and we extend the method to the second order algorithm. This strategy is motivated by the fact that under suitable assumptions, the contribution of u _H to the error in the non-linear term, is measured in the L ² norm in space and time, and thus has a higher-order than if it were measured in the H ¹ norm in space. We present the following results: if h ² = H ³ = (Δt)², then the global error of the two-grid algorithm is of the order of h ², the same as would have been obtained if the non-linear problem had been solved directly on the fine grid.     

New formulations of the multiple sequence alignment problem

A well known formulation of the multiple sequence alignment (MSA) problem is the maximum weight trace (MWT), a 0–1 linear programming problem. In this paper, we propose a new integer quadratic programming formulation of the MSA. The number of constraints and variables in the problem are only of the order of kL ², where, k is the number of sequences and L is the total length of the sequences, that is, L = ?_i=1^kl_i{L= \sum_{i=1}^{k}l_{i}} , where l _i is the length of sequence i. Based on this formulation we introduce an equivalent linear constrained 0–1 quadratic programming problem. We also propose a 0–1 linear programming formulation of the MWT problem, with polynomially many constraints. Our formulation provides the first direct compact formulation that ensures that the critical circuit inequalities (which are exponentially many) are all met.     

Streaming Algorithms for Line Simplification

We study the following variant of the well-known line-simplification problem: we are getting a (possibly infinite) sequence of points p ₀,p ₁,p ₂,… in the plane defining a polygonal path, and as we receive the points, we wish to maintain a simplification of the path seen so far. We study this problem in a streaming setting, where we only have a limited amount of storage, so that we cannot store all the points. We analyze the competitive ratio of our algorithms, allowing resource augmentation: we let our algorithm maintain a simplification with 2k (internal) points and compare the error of our simplification to the error of the optimal simplification with k points. We obtain the algorithms with O(1) competitive ratio for three cases: convex paths, where the error is measured using the Hausdorff distance (or Fréchet distance), xy-monotone paths, where the error is measured using the Hausdorff distance (or Fréchet distance), and general paths, where the error is measured using the Fréchet distance. In the first case the algorithm needs O(k) additional storage, and in the latter two cases the algorithm needs O(k ²) additional storage.     

A Parameter Selection Method for Wavelet Shrinkage Denoising

Thresholding estimators in an orthonormal wavelet basis are well established tools for Gaussian noise removal. However, the universal threshold choice, suggested by Donoho and Johnstone, sometimes leads to over-smoothed approximations.For the denoising problem this paper uses the deterministic approach proposed by Chambolle et al., which handles it as a variational problem, whose solution can be formulated in terms of wavelet shrinkage. This allows us to use wavelet shrinkage successfully for more general denoising problems and to propose a new criterion for the choice of the shrinkage parameter, which we call H-curve criterion. It is based on the plot, for different parameter values, of the B ₁ ¹(L ₁)-norm of the computed solution versus the L ₂-norm of the residual, considered in logarithmic scale. Extensive numerical experimentation shows that this new choice of shrinkage parameter yields good results both for Gaussian and other kinds of noise.     

Survey propagation: An algorithm for satisfiability

We study the satisfiability of randomly generated formulas formed by M clauses of exactly K literals over N Boolean variables. For a given value of N the problem is known to be most difficult when α = M/N is close to the experimental threshold α_c separating the region where almost all formulas are SAT from the region where all formulas are UNSAT. Recent results from a statistical physics analysis suggest that the difficulty is related to the existence of a clustering phenomenon of the solutions when α is close to (but smaller than) α_c. We introduce a new type of message passing algorithm which allows to find efficiently a satisfying assignment of the variables in this difficult region. This algorithm is iterative and composed of two main parts. The first is a message‐passing procedure which generalizes the usual methods like Sum‐Product or Belief Propagation: It passes messages that may be thought of as surveys over clusters of the ordinary messages. The second part uses the detailed probabilistic information obtained from the surveys in order to fix variables and simplify the problem. Eventually, the simplified problem that remains is solved by a conventional heuristic. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005     

General models in min-max planar location: Checking optimality conditions

This paper studies the problem of deciding whether the present iteration point of some algorithm applied to a planar singlefacility min-max location problem, with distances measured by either anl _p -norm or a polyhedral gauge, is optimal or not. It turns out that this problem is equivalent to the decision problem of whether 0 belongs to the convex hull of either a finite number of points in the plane or a finite number of differentl _q -circles . Although both membership problems are theoretically solvable in polynomial time, the last problem is more difficult to solve in practice than the first one. Moreover, the second problem is solvable only in the weak sense, i.e., up to a predetermined accuracy. Unfortunately, these polynomial-time algorithms are not practical. Although this is a negative result, it is possible to construct an efficient and extremely simple linear-time algorithm to solve the first problem. Moreover, this paper describes an implementable procedure to reduce the second decision problem to the first with any desired precision. Finally, in the last section, some computational results for these algorithms are reported.The work of the second author was supported by JNICT (Portugal), under Contract BD/631/90-RM, during his stay at Erasmus University in Rotterdam.The authors would like to express their acknowledgments to Jan Brinkhuis for his suggestions and support and to Joe Mitchell for suggesting the simplifications leading to Algorithm 3.1. Also, the anonymous referees are acknowledged for their careful reading of the paper and their useful comments.     

Estimation of a Normal Covariance Matrix with Incomplete Data under Stein′s Loss

Suppose that we have (n − a) independent observations from N_p(0, Σ) and that, in addition, we have a independent observations available on the last (p − c) coordinates. Assuming that both observations are independent, we consider the problem of estimating Σ under the Stein′s loss function, and show that some estimators invariant under the permutation of the last (p − c) coordinates as well as under those of the first c coordinates are better than the minimax estimators of Eaten. The estimators considered outperform the maximum likelihood estimator (MLE) under the Stein′s loss function as well. The method involved here is computation of an unbiased estimate of the risk of an invariant estimator considered in this article. In addition we discuss its application to the problem of estimating a covariance matrix in a GMANOVA model since the estimation problem of the covariance matrix with extra data can be regarded as its canonical form.     

A remark on the rate of convergence for a mixed finite element method for second order problems

A mixed finite element method for second order elliptic problems is considered, where the solution u of the problem and grad u are approximated separately.

It is known that with respect to the L ₂-norm the approximation of grad u converges with the same rate as the approximation of u does if the solution is sufficiently smooth. The aim of this note is to show that except a logarithmic term the same holds true with respect to the L _∞-norm.     

Stable numerical differentiation for the second order derivatives

Consider a numerical differential problem, which aims to compute the second order derivative of a function stably from its given noisy data. For this ill-posed problem, we introduce the Lavrent′ev regularization scheme by reformulating this differentiation problem as an integral equation of the first kind. The advantage of this proposed scheme is that we can give the regularizing solution by an explicit integral expression, therefore it is easy to be implemented. The a-priori and a-posterior choice strategies for the regularization parameter are considered, with convergence analysis and error estimate of the regularizing solution for noisy data based on the integral operator decomposition. The validity of the proposed scheme is shown by several numerical examples.     

Distance matrices for points on a line,on a circle,and at the vertices of ann-dimensional cube

Forn pointsA _i ,i=1, 2, ...,n, in Euclidean space ℝ ^m , the distance matrix is defined as a matrix of the form D=(D _i ,j) _i ,j=1,...,n, where theD _i ,j are the distances between the pointsA _i andA _j . Two configurations of pointsA _i ,i=1, 2,...,n, are considered. These are the configurations of points all lying on a circle or on a line and of points at the vertices of anm-dimensional cube. In the first case, the inverse matrix is obtained in explicit form. In the second case, it is shown that the complete set of eigenvectors is composed of the columns of the Hadamard matrix of appropriate order. Using the fact that distance matrices in Euclidean space are nondegenerate, several inequalities are derived for solving the system of linear equations whose matrix is a given distance matrix. Translated fromMatematicheskie Zametki, Vol. 58, No. 1, pp. 127–138, July, 1995.     

On the Blow-up of the Solutions of a Quasilinear Wave Equation With a Semilinear Source Term

In this paper, following the ideas of Lax, we prove a blow-up result for a class of solutions of the equation ϕ_tt−ϕ_xx−ϕ²_xϕ_xx−ϕ³ = 0, corresponding, in certain cases, to the development of a singularity in the second derivatives of ϕ. These solutions solve locally (in time) the Cauchy problem for smooth initial data belonging to the uniformly local Sobolev spaces considered by Kato and by Majda.     

Finding independent sets in a graph using continuous multivariable polynomial formulations

Two continuous formulations of the maximum independent set problem on a graph G=(V,E) are considered. Both cases involve the maximization of an n-variable polynomial over the n-dimensional hypercube, where n is the number of nodes in G. Two (polynomial) objective functions F(x) and H(x) are considered. Given any solution to x ₀ in the hypercube, we propose two polynomial-time algorithms based on these formulations, for finding maximal independent sets with cardinality greater than or equal to F(x₀) and H(x₀), respectively. A relation between the two approaches is studied and a more general statement for dominating sets is proved. Results of preliminary computational experiments for some of the DIMACS clique benchmark graphs are presented.