Embeddings on a boolean cube

In this paper, we characterize a class of graphs which can be embedded on a boolean cube. Some of the graphs in this class are identified with the well known graphs such asmulti-dimensional mesh of trees, tree of meshes, etc. We suggest (i) an embedding of anr-dimensional mesh of trees ofn ^r (r+1)–rn ^r–1 nodes on a boolean cube of (2n) ^r nodes, and (ii) an embedding of a tree of meshes with 2n ² logn+n ² nodes on a boolean cube withn ² exp₂ (log (2 logn+1)]) nodes.     

Finding thek smallest spanning trees

We give improved solutions for the problem of generating thek smallest spanning trees in a graph and in the plane. Our algorithm for general graphs takes timeO(m log(m, n)=k ²); for planar graphs this bound can be improved toO(n+k ²). We also show that thek best spanning trees for a set of points in the plane can be computed in timeO(min(k ² n+n logn,k ²+kn log(n/k))). Thek best orthogonal spanning trees in the plane can be found in timeO(n logn+kn log log(n/k)+k ²).     

Selection on rectangular meshes with multiple broadcasting

One of the fundamental algorithmic problems in computer science involves selecting thekth smallest element in a setS ofn elements. In this paper we present a fast selection algorithm which runs inO(n ^1/8 logn) time on a mesh with multiple broadcasting of sizen ^3/8 ×n ^5/8. Our result shows that, just like semigroup computations, selection can be done much faster on a suitably chosen rectangular mesh than on square meshes. We also show that if every processor can storen ^1/9 items, then our selection algorithm runs inO(n ^1/9 logn) time on a mesh with multiple broadcasting of sizen ^1/3 ×n ^5/9.Work supported by NASA under grant NCC1-99.This author was partly supported by NSF grant CCR-8009996.     

Strong Arens irregularity of Beurling algebras with a locally convex topology

Let G be a locally compact group with a weight function ω. Recently, we have shown that the Banach space L₀^∞ (G,1/ω) can be identified with the strong dual of L¹(G, ω)equipped with some locally convex topologies τ. Here we use this duality to introduce an Arens multiplication on (L¹(G, ω), τ)**, and prove that the topological center of (L¹(G, ω), τ)** is (L¹(G, ω); this enables us to conclude that (L¹(G, ω), τ) is Arens regular if and only if G is discrete. We also give a characterization for Arens regularity of L₀^∞ (G, 1/ω)¹. Received: 8 March 2005     

Tangential Markov Inequalities on Transcendental Curves

   Abstract. We show that on the curves γ:=(x,e ^t(x) ) , x∈ [a,b] , where t(x) is a fixed polynomial, there holds a tangential Markov inequality of exponent four for algebraic polynomials P _N (x,y) of degree at most N in each variable x,y: ||(P _N (x,e ^t(x) ))'|| _[a,b] ≤ CN ⁴ ||P _N || _γ , and the exponent four is sharp. On the other hand, the corresponding tangential Markov factors on curves y=x ^α with irrational α grow exponentially in the degree of the polynomials.     

Shape-Preserving Widths of Weighted Sobolev-Type Classes of Positive, Monotone, and Convex Functions on a Finite Interval

   Abstract. Let I be a finite interval, r∈ N and ρ(t)= dist {t, I} , t∈ I . Denote by Δ ^s ₊ L _q the subset of all functions y∈ L _q such that the s -difference Δ ^s _τ y(t) is nonnegative on I ,

A dynamic programming approach to the complete set partitioning problem

The complete set partitioning (CSP) problem is a special case of the set partitioning problem where the coefficient matrix has 2 ^m –1 columns, each column being a binary representation of a unique integer between 1 and 2 ^m –1,m1. It has wide applications in the area of corporate tax structuring in operations research. In this paper we propose a dynamic programming approach to solve the CSP problem, which has time complexityO(3 ^m ), wheren=2 ^m –1 is the size of the problem space.     

The Two-Parameter Higher-Order Differential Calculus and Curvature on a Quantum Plane

We construct an associative differential algebra on a two-parameter quantum plane associated with a nilpotent endomorphism d in the two cases d ² = 0 and d ³ = 0 (d ² ≠ 0). The correspondent curvature is derived and the related non-commutative gauge field theory is introduced.     

The weighted maximum independent set problem in permutation graphs

In this paper, sequential and parallel algorithms are presented to find a maximum independent set with largest weight in a weighted permutation graph. The sequential algorithm, which is designed based on dynamic programming, runs in timeO(nlogn) and requiresO(n) space. The parallel algorithm runs inO(log² n) time usingO(n ³/logn) processors on the CREW PRAM, orO(logn) time usingO(n ³) processors on the CRCW PRAM.     

Parallel algorithms for permutation graphs

In this paper, parallel algorithms are presented for solving some problems on permutation graphs. The coloring problem is solved inO(log² n) time usingO(n ³/logn) processors on the CREW PRAM, orO(logn) time usingO(n ³) processors on the CRCW PRAM. The weighted clique problem, the weighted independent set problem, the cliques cover problem, and the maximal layers problem are all solved with the same complexities. We can also show that the longest common subsequence problem belongs to the class NC.     

The primitive permutation groups of degree 2 a ·3 b

In this paper, we give a complete classification of all finite simple groups with maximal subgroups of index n, where n = 2^a·3^b for a, b≧ 1. As a consequence, for such n, all primitive permutation groups of degree n are given. The motivation of this work comes also from a study of Cayley graphs of certain valency on a finite simple group. Received: 9 March 2005     

Optimal Control of the Obstacle for an Elliptic Variational Inequality

An optimal control problem for an elliptic obstacle variational inequality is considered. The obstacle is taken to be the control and the solution to the obstacle problem is taken to be the state. The goal is to find the optimal obstacle from H ¹ ₀ (Ω) so that the state is close to the desired profile while the H ¹ (Ω) norm of the obstacle is not too large. Existence, uniqueness, and regularity as well as some characterizations of the optimal pairs are established. Accepted 11 September 1996     

Geometry of Local Adaptive Galerkin Bases

The local adaptive Galerkin bases for large-dimensional dynamical systems, whose long-time behavior is confined to a finite-dimensional manifold, are optimal bases chosen by a local version of a singular decomposition analysis. These bases are picked out by choosing directions of maximum bending of the manifold restricted to a ball of radius ɛ . We show their geometrical meaning by analyzing the eigenvalues of a certain self-adjoint operator. The eigenvalues scale according to the information they carry, the ones that scale as ɛ ² have a common factor that depends only on the dimension of the manifold, the ones that scale as ɛ ⁴ give the different curvatures of the manifold, the ones that scale as ɛ ⁶ give the third invariants, as the torsion for curves, and so on. In this way we obtain a decomposition of phase space into orthogonal spaces E _m , where E _m is spanned by the eigenvectors whose corresponding eigenvalues scale as ɛ ^m . This decomposition is analogous to the Frenet frames for curves. We also discover a practical way to compute the dimension and local structure of the invariant manifold. Accepted 14 October 1998     

A note on optimal multiway split trees

Split trees are suitable data structures for storing records with different access frequencies. Under assumption that the access frequencies are all distinct, Huang has proposed anO(n ⁴ logm) time algorithm to construct an (m+1)-way split tree for a set ofn keys. In this paper, we generalize Huang's algorithm to deal with the case of non-distinct access frequencies. The technique used in the generalized algorithm is a generalization of Hesteret al.'s, where the binary case was considered. The generalized algorithm runs inO(n ⁵ logm) time.     

The Friedrichs Extension of the Aharonov–Bohm Hamiltonian on a Disc

We show that the Aharonov–Bohm Hamiltonian considered on a disc has a four-parameter family of self-adjoint extensions. Among the in- finitely many self-adjoint extensions, we determine to which parameters the Friedrichs extension H^F corresponds and its lowest eigenvalue is found. Moreover, we note that the diamagnetic inequality holds for H^F.     

On the minimality of polygon triangulation

The problem of triangulating a polygon using the minimum number of triangles is treated. We show that the minimum number of triangles required to partition a simplen-gon is equal ton+2w –d – 2, wherew is the number of holes andd is the maximum number of independent degenerate triangles of then-gon. We also propose an algorithm for constructing the minimum triangulation of a simple hole-freen-gon. The algorithm takesO(nlog² n+DK ²) time, whereD is the maximum number of vertices lying on the same line in then-gon andK is the number of minimally degenerate triangles of then-gon.     

On the Degree of Approximation by Manifolds of Finite Pseudo-Dimension

The pseudo-dimension of a real-valued function class is an extension of the VC dimension for set-indicator function classes. A class of finite pseudo-dimension possesses a useful statistical smoothness property. In [10] we introduced a nonlinear approximation width = which measures the worst-case approximation error over all functions by the best manifold of pseudo-dimension n . In this paper we obtain tight upper and lower bounds on ρ _n (W ^r,d _p , L _q ) , both being a constant factor of n ^-r/d , for a Sobolev class W ^r,d _p , . As this is also the estimate of the classical Alexandrov nonlinear n -width, our result proves that approximation of W ^r,d _p by the family of manifolds of pseudo-dimension n is as powerful as approximation by the family of all nonlinear manifolds with continuous selection operators. March 12, 1997. Dates revised: August 26, 1997, October 24, 1997, March 16, 1998, June 15, 1998. Date accepted: June 25, 1998.     

Uniqueness of Markov-Extremal Polynomials on Symmetric Convex Bodies

For a compact set K\subset R ^d with nonempty interior, the Markov constants M _n (K) can be defined as the maximal possible absolute value attained on K by the gradient vector of an n -degree polynomial p with maximum norm 1 on K . It is known that for convex, symmetric bodies M _n (K) = n ² /r(K) , where r(K) is the ``half-width' (i.e., the radius of the maximal inscribed ball) of the body K . We study extremal polynomials of this Markov inequality, and show that they are essentially unique if and only if K has a certain geometric property, called flatness. For example, for the unit ball B ^d (\smallbf 0, 1) we do not have uniqueness, while for the unit cube [-1,1] ^d the extremal polynomials are essentially unique. September 9, 1999. Date revised: September 28, 2000. Date accepted: November 14, 2000.     

Exponential Convergence for a System of Conuclear Space-Valued Diffusions with Mean-Field Interaction

We consider an interacting system of n diffusion processes X ⁿ _j (t): t∈[0,1] , j=1,2,. . ., n , taking values in a conuclear space Φ' . Let ζ ⁿ _t =(1/n)Σ ⁿ _j=1 δ _Xnj(t) be the empirical process. It has been proved that ζ ⁿ , as n→∞ , converges to a deterministic measure-valued process which is the unique solution of a nonlinear differential equation. In this paper we show that, under suitable conditions, ζ ⁿ converges to ζ at an exponential rate. Accepted 20 October 1997     

On Shellsort and the frobenius problem

A boundO(N ^1+1/k ) for the running time of Shellsort, withO(logN) passes, is proved very simply by application of a Frobenius basis withk elements.