Thresholds and optimal binary comparison search trees

We present an O(n⁴)-time algorithm for the following problem: Given a set of items with known access frequencies, find the optimal binary search tree under the realistic assumption that each comparison can only result in a two-way decision: either an equality comparison or a less-than comparisons. This improves the best known result of O(n⁵) time, which is based on split tree algorithms. Our algorithm relies on establishing thresholds on the frequency of an item that can occur as an equality comparison at the root of an optimal tree.     

A quantile-based approach to system selection

We propose a quantile-based ranking and selection (R&S) procedure for comparing a finite set of stochastic systems via simulation. Our R&S procedure uses a quantile set of the simulated probability distribution of a performance characteristic of interest that best represents the most appropriate selection criterion as the basis for comparison. Since this quantile set may represent either the downside risk, upside risk, or central tendency of the performance characteristic, the proposed approach is more flexible than the traditional mean-based approach to R&S. We first present a procedure that selects the best system from among K systems, and then we modified that procedure for the case where K − 1 systems are compared against a standard system. We present a set of experiments to highlight the flexibility of the proposed procedures.     

Estimation of a parameter of Morgenstern type bivariate exponential distribution by ranked set sampling

Ranked set sampling is applicable whenever ranking of a set of sampling units can be done easily by a judgement method or based on the measurement of an auxiliary variable on the units selected. In this work, we consider ranked set sampling, in which ranking of units are done based on measurements made on an easily and exactly measurable auxiliary variable X which is correlated with the study variable Y. We then estimate the mean of the study variate Y by the BLUE based on the measurements made on the units of the ranked set sampling regarding the study variable Y, when (X ,Y) follows a Morgenstern type bivariate exponential distribution. We then consider unbalanced multistage ranked set sampling and estimate the mean of the study variate Y by the BLUE based on the observations made on the units of multistage ranked set sample regarding the study variable Y. Efficiency comparison is also made on all estimators considered in this work.     

Crowding with nearest neighbors replacement for multiple species niching and building blocks preservation in binary multimodal functions optimization

This paper introduces a novel niching scheme called the q-nearest neighbors replacement (q-NNR) method in the framework of the steady-state GAs (SSGAs) for solving binary multimodal optimization problems. A detailed comparison of the main niching approaches are presented first. The niching paradigm and difference of the selection-recombination genetic algorithms (GAs) and the recombination-replacement SSGAs are discussed. Then the q-NNR is developed by adopting special replacement policies based on the SSGAs; a Boltzmann scheme for dynamically sizing the nearest neighbors set is designed to achieve a speed-up and control the proportion of individuals adapted to different niches. Finally, experiments are carried out on a set of test functions characterized by deception, epistasis, symmetry and multimodality. The results are satisfactory and illustrate the effectivity and efficiency of the proposed niching method.     

A LEVEL SET APPROACH TO SEMICONTINUOUS VISCOSITY SOLUTIONS FOR CAUCHY PROBLEMS

A level set formulation is presented to characterize a maximal solution of the Cauchy problem for the Hamilton-Jacobi equation with semicontinuous initial data in an explicit way. No convexity assumptions on Hamiltonians are imposed. The solution proposed in the present paper is interpreted as the level set of an auxiliary problem and called an L-solution. It turns out that our L-solution is consistent with a classical discontinuous viscosity solution and a bitateral viscosity solution. Moreover, our L-solution is unique and enjoy the comparison principle. The condition that initial data is really attained is also discussed.     

Inferring consensus weights from pairwise comparison matrices without suitable properties

Pairwise comparison is a popular method for establishing the relative importance of n objects. Its main purpose is to get a set of weights (priority vector) associated with the objects. When the information gathered from the decision maker does not verify some rational properties, it is not easy to search the priority vector. Goal programming is a flexible tool for addressing this type of problem. In this paper, we focus on a group decision-making scenario. Thus, we analyze different methodologies for getting a collective priority vector. The first method is to aggregate general pairwise comparison matrices (i.e., matrices without suitable properties) and then get the priority vector from the consensus matrix. The second method proposes to get the collective priority vector by formulating an optimization problem without determining the consensus pairwise comparison matrix beforehand.     

Determination of conductors from Galois module structure

Let E denote an unramified extension of , and set for an odd prime p and . We determine the conductors of the Kummer extensions of F by those elements such that is Galois. This follows from a comparison of the Galois module structure of with the unit filtration of F. Received: 28 August 2000; in final form: 11 October 2001 / Published online: 4 April 2002     

Comparison semigroups and algebras of transformations

We characterize algebras of transformations on a set under the operations of composition and the pointwise switching function defined as follows: (f,g)[h,k](x)=h(x) if f(x)=g(x), and k(x) otherwise. The resulting algebras are both semigroups and comparison algebras in the sense of Kennison. The same characterization holds for partial transformations under composition and a suitable generalisation of the quaternary operation in which agreement of f,g includes cases where neither is defined. When a zero element is added (modelling the empty function), the resulting signature is rich enough to encompass many operations on semigroups of partial transformations previously considered, including set difference and intersection, restrictive product, and a functional analog of union. When an identity element is also added (modelling the identity function), further domain-related operations can be captured.     

On cycle—Complete graph ramsey numbers

A new upper bound is given for the cycle-complete graph Ramsey number r(C_m, K_n), the smallest order for a graph which forces it to contain either a cycle of order m or a set of n independent vertices. Then, another cycle-complete graph Ramsey number is studied, namely r(?C_m, K_n) the smallest order for a graph which forces it to contain either a cycle of order / for some / satisfying 3?/?m or a set of n independent vertices. We obtain the exact value of r(?C_m K_n) for all m > n and an upper bound which applies when m is large in comparison with log n.     

Sorting in one round

Given an ordered set ofn elements whose order is not known to us, it is shown that by making slightly more thancn ^3/2 simultaneous comparison almost all comparisons can be deduced by direct implications. It is also shown that this result is essentially best possible, and that ifn is large, almost any choice ofcn ^3/2 comparisons will yield almost all comparisons by direct implications.     

Crew Assignment via Constraint Programming: Integrating Column Generation and Heuristic Tree Search

The Airline Crew Assignment Problem (ACA) consists of assigning lines of work to a set of crew members such that a set of activities is partitioned and the costs for that assignment are minimized. Especially for European airline companies, complex constraints defining the feasibility of a line of work have to be respected. We developed two different algorithms to tackle the large scale optimization problem of Airline Crew Assignment. The first is an application of the Constraint Programming (CP) based Column Generation Framework. The second approach performs a CP based heuristic tree search. We present how both algorithms can be coupled to overcome their inherent weaknesses by integrating methods from Constraint Programming and Operations Research. Numerical results show the superiority of the hybrid algorithm in comparison to CP based tree search and column generation alone.     

A density approach to Hamilton-Jacobi equations with t-measurable Hamiltonians

In 1985 H. Ishii [Is85] proposed a generalization of the notion of (continuous) viscosity solution for an Hamilton-Jacobi equation with a t-measurable Hamiltonian—that is, a Hamiltonian which is measurable in time and continuous in the other variables. This notion turned out to agree with natural applications, like Control and Differential Games Theory. Since then, several improvements have been achieved for the standard situation when the Hamiltonian is continuous. It is someway an accepted general idea that parallel improvements are likely for t-measurable Hamiltonians as well, though such a job might appear a bit tedious because of the necessarily involved technicalities.In this paper we show that Ishii’s definition of viscosity solution coincides with the one which would arise by extending by density the standard definition. Namely, we regard a t-measurable Hamiltonian H as an element of the closure (for suitable topologies) of a class of continuous Hamiltonians. On the other hand, we show that the set of Ishii’s (sub-, super-) solutions for H is nothing but the limit set of the (sub-, super-) solutions corresponding to continuous Hamiltonians approaching H. This put us in the condition of establishing comparison, existence, and regularity results by deriving them from the analogous results for the case of continuous Hamiltonians.     

Comparison of isotropic and anisotropic subgrid scale models in Large Eddy Simulations of a backward-facing step and square duct flow

The present paper employs the anisotropic explicit algebraic subgrid-stress model (EASM), proposed by Marstorp et al. J. Fluid. Mech. 639, 403 - 432 (2009), developed in the spirit of an earlier explicit algebraic RANS-model for statistical closures. The EASM in its elementary, computationally efficient non-dynamic version is used for Large Eddy Simulation of three-dimensional flows over a backward-facing step at a bulk Reynolds number of 4805 and a square duct at 2205. Its performance is assessed by comparison with experimental data and an own Direct Numerical Simulation. Furthermore, a set of eddy-viscosity models, including the recent σ-model, is employed for comparison. Various statistical quantities are evaluated to assess the respective performance of the different models showing, that the anisotropic EASM compares favorably to the other models. (© 2016 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Projective spread sets

In this paper the notion of a spread set for at-spread ofPG(2t+1,q) is generalised and it is shown that certaint-spreads ofPG(n, q) correspond to these generalised spread sets. Then a projective spread set is defined and it is shown that anyt-spread ofPG(n, q) corresponds to a projective spread set. Connections between the spread set and the projective spread set of at-spread are discussed, in particular in the case of at-spread ofPG(2t + 1,q) the spread set and the projective spread set are equivalent, giving a new and straightforward construction of a spread set. The methods developed are used to show, with the aid of a computer, that the 1-packing ofPG(7,2) constructed by Baker is regulus-free.Dedicated to Professor Giuseppe Tallini on the occasion of his 60th birthday     

Minimal Overrings of an Integrally Closed Domain

Abstract

The main purpose of this paper is to characterize minimal overrings of an integrally closed domain R. We show that there exists a strong relationship between minimal overrings and the notion of ideal transforms. In particular, we prove that if T(M) = S(M) for each maximal ideal M, then there is a bijective correspondence between the set of invertible maximal ideals of R and the set of minimal overrings of R. This study enables us to produce several interesting applications concerning semi-local, Dedekind, Prüferian and Krull domains. Moreover, we investigate the spectrum of a minimal overring in comparison with the spectrum of R, and we determine whether the polynomial ring R[X ₁, X ₂,…, X _n ] has a minimal overring.     

Comparison theorems for the third order trinomial differential equations with delay argument

In this paper we study asymptotic properties of the third order trinomial delay differential equation (*) y‴(t) − p(t)y′(t) + g(t)y(τ(t)) = 0 by transforming this equation to the binomial canonical equation. The results obtained essentially improve known results in the literature. On the other hand, the set of comparison principles obtained permits to extend immediately asymptotic criteria from ordinary to delay equations. Research was supported by S.G.A. No.1/003/09.     

On mean curvature flow with forcing

Abstract

This paper investigates geometric properties and well-posedness of a mean curvature flow with volume-dependent forcing. With the class of forcing which bounds the volume of the evolving set away from zero and infinity, we show that a strong version of star-shapedness is preserved over time. More precisely, it is shown that the flow preserves the ρ-reflection property, which corresponds to a quantitative Lipschitz property of the set with respect to the nearest ball. Based on this property we show that the problem is well-posed and its solutions starting with ρ-reflection property become instantly smooth. Lastly, for a model problem, we will discuss the flow’s exponential convergence to the unique equilibrium in Hausdorff topology. For the analysis, we adopt the approach developed by Feldman-Kim to combine viscosity solutions approach and variational method. The main challenge lies in the lack of comparison principle, which accompanies forcing terms that penalize small volume.     

Gaussian Complex Zeros on the Hole Event: The Emergence of a Forbidden Region

Consider the Gaussian entire function where {ξ_k} is a sequence of independent standard complex Gaussians. This random Taylor series is distinguished by the invariance of its zero set with respect to the isometries of the plane ℂ. It has been of considerable interest to study the statistical properties of the zero set, particularly in comparison to other planar point processes. We show that the law of the zero set, conditioned on the function F_ℂ having no zeros in a disk of radius r and normalized appropriately, converges to an explicit limiting Radon measure on ℂ as r → ∞. A remarkable feature of this limiting measure is the existence of a large “forbidden region” between a singular part supported on the boundary of the (scaled) hole and the equilibrium measure far from the hole. In particular, this answers a question posed by Nazarov and Sodin, and is in stark contrast to the corresponding result of Jancovici, Lebowitz, and Manificat in the random matrix setting: there is no such forbidden region for the Ginibre ensemble. © 2018 Wiley Periodicals, Inc.     

Test-Based Variable Selection via Cross-Validation

Abstract

Test-based variable selection algorithms in regression often are based on sequential comparison of test statistics to cutoff values. A predetermined a level typically is used to determine the cutoffs based on an assumed probability distribution for the test statistic. For example, backward elimination or forward stepwise involve comparisons of test statistics to prespecified t or F cutoffs in Gaussian linear regression, while a likelihood ratio. Wald, or score statistic, is typically used with standard normal or chi square cutoffs in nonlinear settings. Although such algorithms enjoy widespread use, their statistical properties are not well understood, either theoretically or empirically. Two inherent problems with these methods are that (1) as in classical hypothesis testing, the value of α is arbitrary, while (2) unlike hypothesis testing, there is no simple analog of type I error rate corresponding to application of the entire algorithm to a data set. In this article we propose a new method, backward elimination via cross-validation (BECV), for test-based variable selection in regression. It is implemented by first finding the empirical p value α*, which minimizes a cross-validation estimate of squared prediction error, then selecting the model by running backward elimination on the entire data set using α* as the nominal p value for each test. We present results of an extensive computer simulation to evaluate BECV and compare its performance to standard backward elimination and forward stepwise selection.     

Optimum parameters for the generalized ADI method

Summary. In the context of the generalized ADI method, we are concerned with the problem of finding in the set of rational functions r with numerator degree m and denominator degree n an element that minimizes where E,F are disjoint real intervals. By extending a recent analysis by Levin and Saff, we present an explicit formula for choosing the pair (m,n) for given m +n. Furthermore, we provide a characterization of and a Remes type algorithm for its determination. Extensive numerical computations furnish some comparison of with asymptotically optimal solutions based on Fejér-Walsh and Leja-Bagby points. Received September 6, 1996 / revised version received June 30, 1997