Sequential clustering with radius and split criteria

Sequential clustering aims at determining homogeneous and/or well-separated clusters within a given set of entities, one at a time, until no more such clusters can be found. We consider a bi-criterion sequential clustering problem in which the radius of a cluster (or maximum dissimilarity between an entity chosen as center and any other entity of the cluster) is chosen as a homogeneity criterion and the split of a cluster (or minimum dissimilarity between an entity in the cluster and one outside of it) is chosen as a separation criterion. An O(N ³) algorithm is proposed for determining radii and splits of all efficient clusters, which leads to an O(N ⁴) algorithm for bi-criterion sequential clustering with radius and split as criteria. This algorithm is illustrated on the well known Ruspini data set.     

Bounded projectors and duality in the spaces of functions holomorphic in the unit ball

The paper studies the Banach spaces h _∞(φ), h ₀(φ), and h ¹(η) of harmonic functions over the unit ball in R ⁿ . These spaces depend on a weight function φ and a weight measure η. For a given function φ from a sufficiently broad class of functions, we solve the duality problem. that is, we construct measures η such that h ¹(η)* ～ h _∞(φ) and h ₀(φ)* ～ h ¹(η).     

Sufficient conditions for the existence of 0’-limitwise monotonic functions for computable <Emphasis Type="Italic">η</Emphasis>-like linear orders

We find new sufficient conditions for the existence of a 0’-limitwise monotonic function defining the order for a computable η-like linear order L, i.e., of a function G such that L ∑ _q∈? G(q). Namely, we define the notions of left local maximal block and right local maximal block and prove that if the sizes of these blocks in a computable η-like linear order L are bounded then there is a 0’-limitwise monotonic function G with L = ∑ _q∈? G(q).     

Probabilities of high extremes for a Gaussian stationary process in a random environment

Let ξ(t) be a zero-mean stationary Gaussian process with the covariance function r(t) of Pickands type, i.e., r(t) = 1 ? |t| ^α + o(|t| ^α ), t → 0, 0 < α ≤ 2, and η(t), ζ(t) be periodic random processes. The exact asymptotic behavior of the probabilities P(max _t∈[0,T] η(t)ξ(t) > u), P(max _t∈[0,T] (ξ(t) + η(t)) > u) and P(max _t∈[0,T] (η(t)ξ(t) + ζ(t)) > u) is obtained for u → ∞ for any T > 0 and independent ξ(t), η(t), ζ(t).     

A Note on a Queueing Optimization Problem

Van Ackere and Ninios (VN) used discrete-event simulation to determine the optimal strategies for a monopolist who operates a single-server facility and uses advertising to attract customers. Their model was based upon an M/E _r /1/K queue. In this paper, we re-analyze their model using queueing theory and numerical optimization. Our results allow the optimal strategies to be characterized more precisely, and this leads to a reassessment and modification of the conclusions reached by VN.     

Weight assurance region in two-stage additive efficiency decomposition DEA model: an application to school data

In this paper we use the additive efficiency decomposition approach in two-stage data envelopment analysis. Initially, we evaluate the variable returns to scale version and face a structural difficulty of the model. In an extreme case, weights ξ₁ or ξ₂, which represent the relative importance of the performance of the first and second stages, respectively, become zero for a number of decision making units (DMUs). As a result, individual stage efficiencies for these DMUs are undefined. We propose a weight assurance region model to restrict ξ₁ and ξ₂, which ensures that both weights are always positive, and therefore individual stage efficiency is always defined. Furthermore, the proposed model is appropriate for policy making in the presence of a priori information about the relative importance of each stage in the overall process. We employ the new model to evaluate the efficiency of secondary education in 65 countries and construct an overall ‘school efficiency’ index. In the first stage we measure the ‘learning environment efficiency’ and in the second we measure the ‘student’s performance efficiency’.     

Dimension polynomials of intermediate differential fields and the strength of a system of differential equations with group action

Let K be a differential field of zero characteristic with a basic set of derivations Δ = {δ ₁, …, δ _m } and let Θ denote the free commutative semigroup of all elements of the form \( \theta = \delta_1^{{k_1}} \cdots \delta_m^{{k_m}} \) where k _i ∈ ? (1 ≤ i ≤ m). Let the order of such an element be defined as ord \( \theta = \sum\limits_{i = 1}^m {{k_i}} \), and for any r ∈ ?, let Θ(r) = {θ ∈ Θ | ord θ ≤ r}. Let L = K〈η ₁, …, η _s 〉 be a differential field extension of K generated by a finite set η = {η ₁, …, η _s } and let F be an intermediate differential field of the extension L/K. Furthermore, for any r ∈ ?, let \( {L_r} = K\left( {\bigcup\limits_{i = 1}^s {\Theta (r){\eta_i}} } \right) \) and F _r = L _r ∩ F. We prove the existence and describe some properties of a polynomial ? _K,F,η (t) ∈ ?[t] such that ? _K,F,η (r) = trdeg _K F _r for all sufficiently large r ∈ ?. This result implies the existence of a dimension polynomial that describes the strength of a system of differential equations with group action in the sense of A. Einstein. We shall also present a more general result, a theorem on a multivariate dimension polynomial associated with an intermediate differential field F and partitions of the basic set Δ.     

Finding a maximum <Emphasis Type="Italic">k</Emphasis>-club using the <Emphasis Type="Italic">k</Emphasis>-clique formulation and canonical hypercube cuts

Detecting low-diameter clusters is an important graph-based data mining technique used in social network analysis, bioinformatics and text-mining. Low pairwise distances within a cluster can facilitate fast communication or good reachability between vertices in the cluster. Formally, a subset of vertices that induce a subgraph of diameter at most k is called a k-club. For low values of the parameter k, this model offers a graph-theoretic relaxation of the clique model that formalizes the notion of a low-diameter cluster. Using a combination of graph decomposition and model decomposition techniques, we demonstrate how the fundamental optimization problem of finding a maximum size k-club can be solved optimally on large-scale benchmark instances that are available in the public domain. Our approach circumvents the use of complicated formulations of the maximum k-club problem in favor of a simple relaxation based on necessary conditions, combined with canonical hypercube cuts introduced by Balas and Jeroslow.     

Extremes of Gaussian processes with smooth random expectation and smooth random variance

Let ξ(t), t ∈ [0, T],T > 0, be a Gaussian stationary process with expectation 0 and variance 1, and let η(t) and μ(t) be other sufficiently smooth random processes independent of ξ(t). In this paper, we obtain an asymptotic exact result for P(sup _t∈[0,T](η(t)ξ(t) + μ(t)) > u) as u→∞.     

On the solvability of the first nonlocal boundary value problem for an elliptic equation

We consider problems of the existence, uniqueness, and sign-definiteness of the classical solutions of the problem

$(Lu)(x) = f(x)(x \in D),u(x) - \beta (x)u(\sigma x) = \psi (x)(x \in S),$

where L is a linear second-order operator elliptic in the closure of a domain D ? R ⁿ and σ is a single-valued continuous mapping of S ≡ ?D into \(\bar D\).

We show that, under natural assumptions on the smoothness of β, σ, and the coefficients of L, this problem is Fredholm provided that either σ has no attractors on S or σ generates an attractor Θ on S and the spectral radius of the operator A defined on η(x) ∈ C(Θ) by the formula (Aη)(x) = |β(x)|η(σx) is less than unity.We obtain semieffective (in terms of a test function) conditions for the unique solvability of the problem.     

Miyamoto involutions in axial algebras of Jordan type half

Nonassociative commutative algebras A, generated by idempotents e whose adjoint operators ad _e : A → A, given by x ? xe, are diagonalizable and have few eigenvalues, are of recent interest. When certain fusion (multiplication) rules between the associated eigenspaces are imposed, the structure of these algebras remains rich yet rather rigid. For example, vertex operator algebras give rise to such algebras. The connection between the Monster algebra and Monster group extends to many axial algebras which then have interesting groups of automorphisms.Axial algebras of Jordan type η are commutative algebras generated by idempotents whose adjoint operators have a minimal polynomial dividing (x-1)x(x-η), where η ? {0, 1} is fixed, with well-defined and restrictive fusion rules. The case of η ≠1/2 was thoroughly analyzed by Hall, Rehren and Shpectorov in a recent paper, in which axial algebras were introduced. Here we focus on the case where η = 1/2, which is less understood and is of a different nature.     

On the random max-closure for heavy-tailed random variables

In this paper, we study the random max-closure property for not necessarily identically distributed real-valued random variables X ₁ ,X ₂ , . . . , which states that, given distributions \( {F}_{X_1} \) , \( {F}_{X_2} \) , . . . from some class of heavy-tailed distributions, the distribution of the random maximum X( _η) := max{0,X ₁ , . . . , X _η } or random maximum S _(η) := max{0, S ₁ , . . . , S _η } belongs to the same class of heavy-tailed distributions. Here, S _n = X ₁ + · · · + X _n , n ≥ 1, and η is a counting random variable, independent of {X ₁ ,X ₂ , . . . }. We provide the conditions for the random max-closure property in the case of classes Open image in new window and Open image in new window .     

Periods and nonvanishing of central <Emphasis Type="Italic">L</Emphasis>-values for GL(2<Emphasis Type="Italic">n</Emphasis>)

Let π be a cuspidal automorphic representation of PGL(2n) over a number field F, and η the quadratic idèle class character attached to a quadratic extension E/F. Guo and Jacquet conjectured a relation between the nonvanishing of L(1/2, π)L(1/2, π ? η) for π of symplectic type and the nonvanishing of certain GL(n,E) periods. When n = 1, this specializes to a well-known result of Waldspurger. We prove this conjecture, and related global results, under some local hypotheses using a simple relative trace formula.We then apply these global results to obtain local results on distinguished supercuspidal representations, which partially establish a conjecture of Prasad and Takloo-Bighash.     

Guided construction search metaheuristics for the capacitated p-median problem with single source constraint

In the capacitated p-median problem with single source constraint, also known as the capacitated clustering problem, a given set of n weighted points is to be partitioned into p clusters such that the total weight of the points in each cluster does not exceed a given cluster capacity. The objective is to find a set of p centres that minimizes the total scatter of points allocated to these clusters. In this paper, a (λ, μ)-interchange neighbourhood based on the concept of λ-interchange of points restricted to μ-adjacent clusters is proposed. Structural properties of centres are identified and exploited to derive special data structures for their efficient evaluations. Different search and selection strategies including the variable neighbourhood search descent with respect to μ-nearest points are investigated. The most efficient strategies are then embedded in a guided construction search metaheuristic framework based either on a periodic local search procedure or a greedy random adaptive search procedure to solve the problem. Computational experience is reported on a standard set of benchmarks. The computational experience demonstrates the competitive performance of the proposed algorithms when compared to the best-known procedures in the literature in terms of solution quality and computational requirement.     

On <Emphasis Type="Italic">s</Emphasis>-Elementary Super Frame Wavelets and Their Path-Connectedness

A super wavelet of length n is an n-tuple (ψ ₁,ψ ₂,…,ψ _n ) in the product space \(\prod_{j=1}^{n} L^{2}(\mathbb{R})\), such that the coordinated dilates of all its coordinated translates form an orthonormal basis for \(\prod_{j=1}^{n} L^{2} (\mathbb{R})\). This concept is generalized to the so-called super frame wavelets, super tight frame wavelets and super normalized tight frame wavelets (or super Parseval frame wavelets), namely an n-tuple (η ₁,η ₂,…,η _n ) in \(\prod_{j=1}^{n}L^{2} (\mathbb{R})\) such that the coordinated dilates of all its coordinated translates form a frame, a tight frame, or a normalized tight frame for \(\prod_{j=1}^{n} L^{2}(\mathbb{R})\). In this paper, we study the super frame wavelets and the super tight frame wavelets whose Fourier transforms are defined by set theoretical functions (called s-elementary frame wavelets). An m-tuple of sets (E ₁,E ₂,…,E _m ) is said to be τ-disjoint if the E _j ’s are pair-wise disjoint under the 2π-translations. We prove that a τ-disjoint m-tuple (E ₁,E ₂,…,E _m ) of frame sets (i.e., η _j defined by \(\widehat{\eta_{j}}=\frac{1}{\sqrt{2\pi}}\chi_{E_{j}}\) is a frame wavelet for L ²(?) for each j) lead to a super frame wavelet (η ₁,η ₂,…,η _m ) for \(\prod_{j=1}^{m} L^{2} (\mathbb{R})\) where \(\widehat{\eta_{j}}=\frac{1}{\sqrt{2\pi}}\chi_{E_{j}}\). In the case of super tight frame wavelets, we prove that (η ₁,η ₂,…,η _m ), defined by \(\widehat{\eta_{j}}=\frac{1}{\sqrt{2\pi}}\chi_{E_{j}}\), is a super tight frame wavelet for ∏_1≤j≤m L ²(?) with frame bound k ₀ if and only if each η _j is a tight frame wavelet for L ²(?) with frame bound k ₀ and that (E ₁,E ₂,…,E _m ) is τ-disjoint. Denote the set of all τ-disjoint s-elementary super frame wavelets for ∏_1≤j≤m L ²(?) by \(\mathfrak{S}(m)\) and the set of all s-elementary super tight frame wavelets (with the same frame bound k ₀) for ∏_1≤j≤m L ²(?) by \(\mathfrak{S}^{k_{0}}(m)\). We further prove that \(\mathfrak{S}(m)\) and \(\mathfrak{S}^{k_{0}}(m)\) are both path-connected under the ∏_1≤j≤m L ²(?) norm, for any given positive integers m and k ₀.     

A branch-and-cut algorithm for the plant-cycle location problem

The Plant-Cycle Location Problem (PCLP) is defined on a graph G=(I∪J, E), where I is the set of customers and J is the set of plants. Each customer must be served by one plant, and the plant must be opened to serve customers. The number of customers that a plant can serve is limited. There is a cost of opening a plant, and of serving a customer from an open plant. All customers served by a plant are in a cycle containing the plant, and there is a routing cost associated to each edge of the cycle. The PCLP consists in determining which plants to open, the assignment of customers to plants, and the cycles containing each open plant and its customers, minimizing the total cost. It is an NP-hard optimization problem arising in routing and telecommunications. In this article, the PCLP is formulated as an integer linear program, a branch-and-cut algorithm is developed, and computational results on real-world data and randomly generated instances are presented. The proposed approach is able to find optimal solutions of random instances with up to 100 customers and 100 potential plants, and of instances on real-world data with up to 120 customers and 16 potential plants.     

Comparing and Simplifying Distinct-Cluster Phylogenetic Networks

Phylogenetic networks are rooted acyclic directed graphs in which the leaves are identified with members of a set X of species. The cluster of a vertex is the set of leaves that are descendants of the vertex. A network is “distinct-cluster” if distinct vertices have distinct clusters. This paper focuses on the set DC(X) of distinct-cluster networks whose leaves are identified with the members of X. For a fixed X, a metric on DC(X) is defined. There is a “cluster-preserving” simplification process by which vertices or certain arcs may be removed without changing the clusters of any remaining vertices. Many of the resulting networks may be uniquely determined without regard to the order of the simplifying operations.     

A new super-efficiency model in the presence of negative data

This paper proposes a new super-efficiency model when some factors (inputs/outputs) are negative. The proposed model employs the RDM model (Portela et al, 2004) for ranking decision-making units (DMUs). Our model ranks the DMUs and determines the type of efficiency for each DMU, simultaneously     

On needed reals

Given a binary relationR, we call a subsetA of the range ofR R-adequate if for everyx in the domain there is someyεA such that (x, y)εR. Following Blass [4], we call a realη ”needed” forR if in everyR-adequate set we find an element from whichη is Turing computable. We show that every real needed for inclusion on the Lebesgue null sets,Cof(\(\mathcal{N}\)), is hyperarithmetic. Replacing “R-adequate” by “R-adequate with minimal cardinality” we get the related notion of being “weakly needed”. We show that it is consistent that the two notions do not coincide for the reaping relation. (They coincide in many models.) We show that not all hyperarithmetic reals are needed for the reaping relation. This answers some questions asked by Blass at the Oberwolfach conference in December 1999 and in [4].