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.     

Modeling of superscalar instruction scheduling and analysis of a heuristic scheduling algorithm

The problem of superscalar instruction scheduling is studied and an analysis of a heuristic scheduling algorithm is presented. First, a superscalar architecture is characterized byk, the number of types of functional units employed,m _i , the number of typei functional units,P _ij , thejth functional unit of typei, andz, the maximal number of delay cycles incurred by the execution of instructions. A program trace to be scheduled is modeled by a directed acyclic graph with delay on precedence relations. These two models reflect most of the flavor of the superscalar instruction scheduling problem. A heuristic scheduling algorithm called the ECG-algorithm is designed by compiling two scheduling guidelines. The performance of the ECG-algorithm is evaluated through worst-case analysis. Lettingw _ECG denote the length of an ECG-schedule andw _opt the length of an optimal schedule, we established the boundwv _ECG /w _opt k+1–2/[max{m _i }(z+1)], which is smaller than other known bounds.     

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 ²).     

On Stable Local Bases for Bivariate Polynomial Spline Spaces

Stable locally supported bases are constructed for the spaces \cal S _d ^r (\triangle) of polynomial splines of degree d≥ 3r+2 and smoothness r defined on triangulations \triangle , as well as for various superspline subspaces. In addition, we show that for r≥ 1 , in general, it is impossible to construct bases which are simultaneously stable and locally linearly independent. February 2, 2000. Date revised: November 27, 2000. Date accepted: March 7, 2001.     

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.     

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 ,

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.     

Uniform Approximation by Entire Functions That Are All Bounded on a Given Set

For two closed sets F and G in the complex plane C, G C , we solve the following problem Under what conditions on F and G can every function f , continuous on F and analytic in its interior, be uniformly approximated by entire functions, each of which is bounded on G ? February 7, 1995. Date revised: October 31, 1995.     

There is No Low Maximal D.C.E. Degree

We show that for any computably enumerable (c.e.) set A and any set L, if L is low and , then there is a c.e. splitting such that . In Particular, if L is low and n‐c.e., then is n‐c.e. and hence there is no low maximal n‐c.e. degree.     

Optimal parallel quicksort on EREW PRAM

In this paper, we present parallel quicksort algorithms running inO((n/p+logp) logn) expected time andO((n/p+logp+log logn) logn) deterministic time respectively, and both withO(n) space by usingp processors on EREW PRAM. Whenp=O(n/logn), the cost is optimal, in terms of the product of time and number of processors. These algorithms can be used to obtain parallel algorithms for constructing balanced binary search trees without using sorting algorithms. One of our quicksort algorithms leads to a parallel quickhull algorithm on EREW PRAM.The work of this author was partially supported by a fellowship from the College of Science, Old Dominion University, Norfolk, VA 23529, USA.     

Average-case results on heapsort

A new algorithm for rearranging a heap is presented and analysed in the average case. The average case upper bound for deleting the maximum element of a random heap is improved, and is shown to be less than [logn]+0.299+M(n) comparisons, *) whereM(n) is between 0 and 1. It is also shown that a heap can be constructed using 1.650n+O(logn) comparisons with this algorithm, the best result for any algorithm which does not use any extra space. The expected time to sortn elements is argued to be less thann logn+0.670n+O(logn), while simulation result points at an average case ofn log n+0.4n which will make it the fastest in-place sorting algorithm. The same technique is used to show that the average number of comparisons when deleting the maximum element of a heap using Williams' algorithm for rearrangement is 2([logn]–1.299+L(n)) whereL(n) also is between 0 and 1, and the average cost for Floyd-Williams Heapsort is at least 2nlogn–3.27n, counting only comparisons. An analysis of the number of interchanges when deleting the maximum element of a random heap, which is the same for both algorithms, is also presented.     

Filtering of Finite-State Time-Nonhomogeneous Markov Processes, a Direct Approach

A filtering equation is derived for P(x _t =x|y _s ,s∈[0,t]) for a continuous-time finite-state two-component time-nonhomogeneous cadlag Markov process z _t =(x _t ,y _t ) . The derivation is based on some new ideas in the filtering theory and does not require any knowledge of stochastic integration. Accepted 10 August 1999. Online publication 13 November 2000.     

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.     

Polynomial Approximation on Convex Subsets of R n

Let K be a closed bounded convex subset of R ⁿ ; then by a result of the first author, which extends a classical theorem of Whitney there is a constant w _m (K) so that for every continuous function f on K there is a polynomial ϕ of degree at most m-1 so that |f(x)-ϕ(x)|≤ w_m(K) sup _{x,x+mh∈ K} |Δ_h^m(f;x)|. The aim of this paper is to study the constant w _m (K) in terms of the dimension n and the geometry of K . For example, we show that w ₂ (K)≤ (1/2) [ log ₂ n]+5/4 and that for suitable K this bound is almost attained. We place special emphasis on the case when K is symmetric and so can be identified as the unit ball of finite-dimensional Banach space; then there are connections between the behavior of w _m (K) and the geometry (particularly the Rademacher type) of the underlying Banach space. It is shown, for example, that if K is an ellipsoid then w ₂ (K) is bounded, independent of dimension, and w ₃ (K)\sim log n . We also give estimates for w ₂ and w ₃ for the unit ball of the spaces l _p ⁿ where 1≤ p≤∈fty. September 24, 1997. Dates revised: January 18, 1999 and June 10, 1999. Date accepted: June 25, 1999.     

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.     

An unfeasible matching problem

LetG be a bipartite graph with natural edge weights, and letW be a function from the set of vertices ofG into natural numbers. AW-matching ofG is a subset of the set of edges ofG such that for each vertexv the total weight of edges in the subset incident tov does not exceedW(v). Letm be a natural number. We show that the problem of deciding whether there is aW-matching inG whose total weight is not less thanm is NP-complete even ifG is bipartite and its edge weights as well as theW(v)-constraints are constantly bounded.     

A generalisation of Brickell's algorithm for fast modular multiplication

Brickell's algorithm findsA ×BmodC forn-bit integersA, B, C, usingO(n) hardware to achieve anO(n) running time. This paper gives a generalisation of his algorithm, and presents a proof, missing from Brickell's paper, that it works, showing the existence of other similar schemes.     

Projective normality of G.I.T. quotient varieties modulo finite groups

We prove that for any finite dimensional representation V of a finite group G of order n the quotient variety G??(V) is projectively normal with respect to descent of 𝒪(1)^?l where l = lcm{1,2,3,4,…,n}. We also prove that for the tautological representation V of the alternating group A_n the projective variety A_n??(V) is projectively normal with respect to the descent of the above line bundle.     

Weighted Polynomial Approximation for Convex External Fields

It is proven that if Q is convex and w(x)= exp(-Q(x)) is the corresponding weight, then every continuous function that vanishes outside the support of the extremal measure associated with w can be uniformly approximated by weighted polynomials of the form w ⁿ P _n . This solves a problem of P. Borwein and E. B. Saff. Actually, a similar result is true locally for any parts of the extremal support where Q is convex. February 10, 1998. Date revised: July 23, 1998. Date accepted: August 17, 1998.     

Approximation and Complexity: Liouvillean-Type Theorems for Linear Differential Equations on an Interval

Let u,v be solutions on an interval I of linear differential equations (LDEs) P=0 , Q=0 , respectively. We obtain a lower bound on the approximation of v by u in terms of bounds on the coefficients of LDE S _i =0 (for several i ), satisfied by the i th derivative of v and by the i th derivative of a basis of the LDE P=0 . One could view this result as a differential analog of the Liouville theorem which states that two different algebraic numbers are well separated if they satisfy algebraic equations with small enough integer coefficients. Unlike the algebraic situation, in the differential setting, in order to bound from below the difference |u-v| , we need to involve not only the coefficients of P,Q themselves, but also those of S _i . September 22, 2000. Final version received: March 11, 2001.