On the enumerative nature of Gomory’s dual cutting plane method

For 30 years after their invention half a century ago, cutting planes for integer programs have been an object of theoretical investigations that had no apparent practical use. When they finally proved their practical usefulness in the late eighties, that happened in the framework of branch and bound procedures, as an auxiliary tool meant to reduce the number of enumerated nodes. To this day, pure cutting plane methods alone have poor convergence properties and are typically not used in practice. Our reason for studying them is our belief that these negative properties can be understood and thus remedied only based on a thorough investigation of such procedures in their pure form. In this paper, the second in a sequence, we address some important issues arising when designing a computationally sound pure cutting plane method. We analyze the dual cutting plane procedure proposed by Gomory in 1958, which is the first (and most famous) convergent cutting plane method for integer linear programming. We focus on the enumerative nature of this method as evidenced by the relative computational success of its lexicographic version (as documented in our previous paper on the subject), and we propose new versions of Gomory’s cutting plane procedure with an improved performance. In particular, the new versions are based on enumerative schemes that treat the objective function implicitly, and redefine the lexicographic order on the fly to mimic a sound branching strategy. Preliminary computational results are reported.     

On the negativity of higher order derivatives of Dirichlet’s energy in plateau’s problem

We calculate higher order derivatives of Dirichlet’s Energy at a branched minimal surface in the direction of Forced Jacobi Fields discovered by the author and R. Böhme. We show that, under certain conditions these derivatives can be made negative, while all lower order derivatives vanish. This is the first time that derivatives of order greater than three have been calculated.     

On the finite element approximation for maxwell’s problem in polynomial domains of the plane

The time-harmonic Maxwell boundary value problem in polygonal domains of R² is considered. The behaviour of the solution in the neighbourhood of nonregular boundary points is given and asymptotic error estimates in L₂- and in curl-div-norm for a finite element approximation of the solution are derived     

On Ulm’s method using divided differences of order one

We provide new sufficient convergence conditions for the semilocal convergence of Ulm’s method (Tzv Akad Nauk Est SSR 16:403–411, 1967) in order to approximate a locally unique solution of an equation in a Banach space setting. We show that in some cases, our hypotheses hold true but the corresponding ones in Burmeister (Z Angew Math Mech 52:101–110, 1972), Kornstaedt (Aequ Math 13:21–45, 1975), Moser (1973), and Potra and Pták (Cas Pest Mat 108:333–341, 1983) do not. We also show that under the same hypotheses and computational cost, finer error bounds can be obtained. Some error bounds are also shown to be sharp. Numerical examples are also provided further validating the results.     

On the degree of iterates of automorphisms¶of the affine plane

For a polynomial automorphism f of ?² _ℂ, we set τ = deg f ²)/(deg f). We prove that τ≤ 1 if and only if f is triangularizable. In this situation, we show (by using a deep result from number theory known as the theorem of Skolem–Mahler–Lech) that the sequence (deg f ⁿ ) _{n ∈ℕ} is periodic for large n. In the opposite case, we prove that τ is an integer (τ≥ 2) and that the sequence (deg f ⁿ ) _{n ∈ℕ} is a geometric progression of ratio τ. In particular, if f is any automorphism, we obtain the rationality of the formal series . Received: 1 December 1997     

On an Analog of the Plan’s Formula

In this paper we obtain an analog of the Plan’s formula, which plays an essential role in obtaining a functional relation for classical Riemann zeta-function.We provide examples of rational functions that satisfy a certain symmetry condition and admit a Maclaurin series expansion with coefficients equal to zero or one.     

On the Behaviour of the spectral characteristic of Feigenbaum’s map

Let T _g : [?1, 1] ?? [?1, 1] be the Feigenbaum map. It is well known that T _g has a Cantor-type attractor F and a unique invariant measure ??₀ supported on F. The corresponding unitary operator (U _g ??)(x) = ??(g(x)) has pure point spectrum consisting of eigenvalues ?? _n,r , n ?? 1, 0 ?? r ?? 2 ^n?1 ? 1 with eigenfunctions e _r ⁽ⁿ⁾ (x). Suppose that f ?? C ¹([?1, 1]), f?? is absolutely continuous on [?1, 1] and f?? ?? L ^p ([?1, 1], d??₀), p > 1. Consider the sum of the amplitudes of the spectral measure of f: $$ Sn(f): = \sum\limits_{r = 0}^{2^n - 1} {|\rho _r^{(n)} |^2 ,\rho _r^{(n)} = \int\limits_{ - 1}^1 {f(x)\overline {e_r^{(n)} (x)} d\mu _o } } (x). $$ Using the thermodynamic formalism for T _g we prove that S _n (f) ?? 2^?n q ⁿ , as n ?? ??, where the constant q ?? (0, 1) does not depend on f.     

On improving the accuracy of Horner’s and Goertzel’s algorithms

It is known that Goertzels algorithm is much less numerically accurate than the Fast Fourier Transform (FFT) (cf. [2]). In order to improve accuracy we propose modifications of both Goertzels and Horners algorithms based on the divide-and-conquer techniques. The proof of the numerical stability of these two modified algorithms is given. The numerical tests in Matlab demonstrate the computational advantages of the proposed modifications. The appendix contains the proof of numerical stability of Goertzels algorithm of polynomial evaluation. AMS subject classification 65F35, 65G50     

On the Sharpness of Mockenhaupt’s Restriction Theorem

We prove that the range of exponents in Mockenhaupt’s restriction theorem for Salem sets (Geom Funct Anal 10:1579–1587, 2000), with the endpoint estimate due to Bak and Seeger (Math Res Lett 18:767–781, 2011), is optimal.     

On the proof of Erdős’ inequality

Using undergraduate calculus, we give a direct elementary proof of a sharp Markov-type inequality \({\left\| {p'} \right\|_{\left[ { - 1,1} \right]}} \leqslant \frac{1}{2}{\left\| p \right\|_{\left[ { - 1,1} \right]}}\) for a constrained polynomial p of degree at most n, initially claimed by P. Erd?s, which is different from the one in the paper of T.Erdélyi (2015). Whereafter, we give the situations on which the equality holds. On the basis of this inequality, we study the monotone polynomial which has only real zeros all but one outside of the interval (?1, 1) and establish a new asymptotically sharp inequality.     

On the Moments of the Absorption Time of Kingman’s Coalescent

Simple integral representations are derived for the moments of the absorption time of Kingman’s coalescent Kingman (J Appl Probab 19:27-43, (1982a)). Their computational efficiency versus known representations is established.     

On Σ-rigid presentations of the real order

For arbitrary tuples of real parameters \(\bar p\) , we prove the existence and effective infiniteness of the class of the linear orders on ? of type 〈?,<〉 which are Σ-definable over \(\mathbb{H}\mathbb{F}(\mathbb{R})\) with parameters \(\bar p\) and have no nontrivial Σ-definable self-embeddings with parameters \(\bar p\) .     

On the order of growth of generalized eigenfunctions of the Sturm-Liouville operator. The Shnol’ theorem

For the generalized eigenfunctions corresponding to a Sturm-Liouville operator on a semiaxis, growth estimates are obtained. In the paper, in contrast to the known Shnol’ theorem, the dependence of the growth order on the behavior at infinity of the potential is studied. Translated fromMatematicheskie Zametki, Vol. 67, No. 1, pp. 46–51, January, 2000.     

On the equivalence of Lagrange’s axiom to the Lotschnittaxiom

We prove that, in Hilbert’s plane absolute geometry, an axiom used by Lagrange in a proof of the Euclidean parallel postulate in a paper read on 3 February 1806 at the Institut de France, which states that “If a and b are two parallels from P to g, then the reflection of a in b is parallel to g as well”, is equivalent to F. Bachmann’s Lotschnittaxiom, which states that “The perpendiculars on the sides a right angle always intersect.”