Min–Max vs. Min–Sum Vehicle Routing: A worst-case analysis

The classical objective function of the Vehicle Routing Problem (VRP) is to minimize the total distance traveled by all vehicles (Min–Sum). In several situations, such as disaster relief efforts, computer networks, and workload balance, the minimization of the longest route (Min–Max) is a better objective function. In this paper, we compare the optimal solution of several variants of the Min–Sum and the Min–Max VRP, from the worst-case point of view. Our aim is two-fold. First, we seek to motivate the design of heuristic, metaheuristic, and matheuristic algorithms for the Min–Max VRP, as even the optimal solution of the classical Min–Sum VRP can be very poor if used to solve the Min–Max VRP. Second, we aim to show that the Min–Max approach should be adopted only when it is well-justified, because the corresponding total distance can be very large with respect to the one obtained by optimally solving the classical Min–Sum VRP.     

On the Maximum Number of Cycles in Outerplanar and Series–Parallel Graphs

Let c(n) be the maximum number of cycles in an outerplanar graph with n vertices. We show that lim c(n)^1/n exists and equals β = 1.502837 . . ., where β is a constant related to the recurrence x_n+1 = 1 + x_n²,  x₀=1{x_{n+1} = 1 + x_n^2, , x_0=1}. The same result holds for the larger class of series–parallel graphs.     

A Min–Max Property of Chordal Bipartite Graphs with Applications

We show that if G is a bipartite graph with no induced cycles on exactly 6 vertices, then the minimum number of chain subgraphs of G needed to cover E(G) equals the chromatic number of the complement of the square of line graph of G. Using this, we establish that for a chordal bipartite graph G, the minimum number of chain subgraphs of G needed to cover E(G) equals the size of a largest induced matching in G, and also that a minimum chain subgraph cover can be computed in polynomial time. The problems of computing a minimum chain cover and a largest induced matching are NP-hard for general bipartite graphs. Finally, we show that our results can be used to efficiently compute a minimum chain subgraph cover when the input is an interval bigraph.     

Dynamic Robust Output Min–Max Control for Discrete Uncertain Systems

Min–max control is a robust control, which guarantees stability in the presence of matched uncertainties. The basic min–max control is a static state feedback law. Recently, the applicability conditions of discrete static min–max control through the output have been derived. In this paper, the results for output static min–max control are further extended to a class of output dynamic min–max controllers, and a general parametrization of all such controllers is derived. The dynamic output min–max control is shown to exist in many circumstances under which the output static min–max control does not exist, and usually allows for broader bounds on uncertainties. Another family of robust output min–max controllers, constructed from an asymptotic observer which is insensitive to uncertainties and a state min–max control, is derived. The latter is shown to be a particular case of the dynamic min–max control when the nominal system has no zeros at the origin. In the case where the insensitive observer exists, it is shown that the observer-controller has the same stability properties as those of the full state feedback min–max control.     

On the Classification of Arc-transitive Circulant Digraphs of Order Odd-Prime-Squared

A Cayley graph F = Cay（G, S） of a group G with respect to S is called a circulant digraph of order pk if G is a cyclic group of the same order. Investigated in this paper are the normality conditions for arc-transitive circulant （di）graphs of order p^2 and the classification of all such graphs. It is proved that any connected arc-transitive circulant digraph of order p^2 is, up to a graph isomorphism, either Kp2, G（p^2,r）, or G（p,r）[pK1], where r｜p- 1.     

Cycles,chaos, and noise in predator–prey dynamics

In contrast to the single species models that were extensively studied in the 1970s and 1980s, predator–prey models give rise to long-period oscillations, and even systems with stable equilibria can display oscillatory transients with a regular frequency. Many fluctuating populations appear to be governed by such interactions. However, predator–prey models have been poorly studied with respect to the interaction of nonlinear dynamics, noise, and system identification. I use simulated data from a simple host–parasitoid model to investigate these issues. The addition of even a modest amount of noise to a stable equilibrium produces enough structured variation to allow reasonably accurate parameter estimation. Despite the fact that more-or-less regular cycles are generated by adding noise to any of the classes of deterministic attractor (stable equilibrium, periodic and quasiperiodic orbits, and chaos), the underlying dynamics can usually be distinguished, especially with the aid of the mechanistic model. However, many of the time series can also be fit quite well by a wrong model, and the fitted wrong model usually misidentifies the underlying attractor. Only the chaotic time series convincingly rejected the wrong model in favor of the true one. Thus chaotic population dynamics offer the best chance for successfully identifying underlying regulatory mechanisms and attractors.     

Cycles in Newton´s means

In the dynamical system defined by Newton′s means for n complex variables, n≥2 there are invariant, planar curves with (chaotic) dynamics conjugated to the dynamics of z↦z ⁿ on the unit circle in the complex plane. Oblatum 8-III-2000 & 8-XI-2000?Published online: 5 March 2001     

K-Factors and Hamilton Cycles in Graphs

We discuss k-factors and Hamiltonian Graphs in graph theory. We prove a general version of the conjecture by R. Haggkvist; as a result, we prove two extended versions of two well-known theorems due to O. Ore and B. Jachson, respectively.     

On system reliability in stress–strength setup

In this paper we study stress–strength reliability for a general coherent system. The exact expression as well as bounds and approximations for system reliability are presented. We also illustrate the estimation procedure for exponential stress–strength distributions.     

On Hardy–Rellich type inequalities in RN

In this note we introduce a new class of Hardy–Rellich type inequalities and explicitly obtain their corresponding sharp constants. Our approach suggests definitions of new Sobolev spaces and embedding results.     

On differential–algebraic equations in infinite dimensions

We consider a class of differential–algebraic equations (DAEs) with index zero in an infinite dimensional Hilbert space. We define a space of consistent initial values, which lead to classical continuously differential solutions for the associated DAE. Moreover, we show that for arbitrary initial values we obtain mild solutions for the associated problem. We discuss the asymptotic behaviour of solutions for both problems. In particular, we provide a characterisation for exponential stability and exponential dichotomies in terms of the spectrum of the associated operator pencil.     

On the Adams–Riemann–Roch theorem in positive characteristic

Let p > 0 be a prime number. We give a short proof of the Adams–Riemann–Roch theorem for the p-th Adams operation, when the involved schemes live in characteristic p. We also answer a question of B. Köck.     

On Nonlocal Cahn–Hilliard–Navier–Stokes Systems in Two Dimensions

We consider a diffuse interface model which describes the motion of an incompressible isothermal mixture of two immiscible fluids. This model consists of the Navier–Stokes equations coupled with a convective nonlocal Cahn–Hilliard equation. Several results were already proven by two of the present authors. However, in the two-dimensional case, the uniqueness of weak solutions was still open. Here we establish such a result even in the case of degenerate mobility and singular potential. Moreover, we show the weak–strong uniqueness in the case of viscosity depending on the order parameter, provided that either the mobility is constant and the potential is regular or the mobility is degenerate and the potential is singular. In the case of constant viscosity, on account of the uniqueness results, we can deduce the connectedness of the global attractor whose existence was obtained in a previous paper. The uniqueness technique can be adapted to show the validity of a smoothing property for the difference of two trajectories which is crucial to establish the existence of an exponential attractor. The latter is established even in the case of variable viscosity, constant mobility and regular potential.     

Max–min Bin Packing Algorithm and its application in nano-particles filling

With regard to existing bin packing algorithms, higher packing efficiency often leads to lower packing speed while higher packing speed leads to lower packing efficiency. Packing speed and packing efficiency of existing bin packing algorithms including NFD, NF, FF, FFD, BF and BFD correlates negatively with each other, thus resulting in the failure of existing bin packing algorithms to satisfy the demand of nano-particles filling for both high speed and high efficiency. The paper provides a new bin packing algorithm, Max–min Bin Packing Algorithm (MM), which realizes both high packing speed and high packing efficiency. MM has the same packing speed as NFD (whose packing speed ranks no. 1 among existing bin packing algorithms); in case that the size repetition rate of objects to be packed is over 5, MM can realize almost the same packing efficiency as BFD (whose packing efficiency ranks No. 1 among existing bin packing algorithms), and in case that the size repetition rate of objects to be packed is over 500, MM can achieve exactly the same packing efficiency as BFD. With respect to application of nano-particles filling, the size repetition rate of nano particles to be packed is usually in thousands or ten thousands, far higher than 5 or 500. Consequently, in application of nano-particles filling, the packing efficiency of MM is exactly equal to that of BFD. Thus the irreconcilable conflict between packing speed and packing efficiency is successfully removed by MM, which leads to MM having better packing effect than any existing bin packing algorithm. In practice, there are few cases when the size repetition of objects to be packed is lower than 5. Therefore the MM is not necessarily limited to nano-particles filling, and can also be widely used in other applications besides nano-particles filling. Especially, MM has significant value in application of nano-particles filling such as nano printing and nano tooth filling.