Characterization of best Chebyshev approximations with prescribed norm

In this paper a new characterization of smooth normed linear spaces is discussed using the notion of proximal points of a pair of convex sets. It is proved that a normed linear space is smooth if and only if for each pair of convex sets, points which are mutually nearest to each other from the respective sets are proximal.     

On certain order constrained Chebyshev rational approximations

Some rational approximations which share the properties of Padé and best uniform approximations are considered. The approximations are best in the Chebyshev sense, but the optimization is performed over subsets of the rational functions which have specified derivatives at one end point of the approximation interval. Explicit relationships between the Padé and uniform approximations are developed assuming the function being approximated satisfies easily verified constraints. The results are applied to the exponential function to determine the existence of best uniform A-acceptable approximations.     

On the computational complexity of cut-reduction

Using appropriate notation systems for proofs, cut-reduction can often be rendered feasible on these notations. Explicit bounds can be given. Developing a suitable notation system for Bounded Arithmetic, and applying these bounds, all the known results on definable functions of certain such theories can be reobtained in a uniform way.     

On the sensitivity to rounding errors of Chebyshev series approximations

By analysing the effects of rounding errors from all sources, it is shown that the coefficients of the polynomial interpolating at the points cos jπ/n, (j=0,1,…, n), can be determined by a stable process, and an algorithm is derived which combines efficiency and stability.     

On computing best Chebyshev complex rational approximants

An algorithm for computing best complex ordinary rational functions is presented. The final step of the procedure consists of solving the system of nonlinear equations defined by the local Kolmogorov criterion before checking recently developed sufficient optimality and uniqueness conditions. Various numerical results are reported exhibiting, in particular, nonunique solutions, saddle points and locally best approximants that are not global.     

On the computational complexity of continuous routing

We study the problem of routing and broadcasting messages in a network, in which messages are generated at processors at arbitrary times and each message must reach its destination by a specific deadline. We present distributed and global routing algorithms for some restricted continuous routing problems on arrays of processors. We show that distributed algorithms are unlikely to exist in more general situations by giving an NP-hardness proof for their corresponding feasibility problem; i.e., the problem of determining whether all messages can be routed without violating the constraints of the network. We also present a distributed algorithm for the continuous broadcasting problem.     

On the computational complexity of the Riemann mapping

In this paper we consider the computational complexity of uniformizing a domain with a given computable boundary. We give nontrivial upper and lower bounds in two settings: when the approximation of the boundary is given either as a list of pixels, or by a Turing machine.     

On the computational complexity of piecewise-linear homotopy algorithms

We show that piecewise-linear homotopy algorithms may take a number of steps that grows exponentially with the dimension when solving a system of linear equations whose solution lies close to the starting point. Our examples are based on an example of Murty exhibiting exponential growth for Lemke's algorithm for the linear complementarity problem.This research was supported in part by NSF grant ECS-7921279 and by a Guggenheim Fellowship.     

On the computational complexity of ordered subgraph recognition

Let (G, <) be a finite graph G with a linearly ordered vertex set V. We consider the decision problem (G, <)ORD to have as an instance an (unordered) graph Γ and as a question whether there exists a linear order ≤ on V(Γ) and an order preserving graph isomorphism of (G, <) onto an induced subgraph of Γ. Several familiar classes of graph are characterized as the yes-instances of (G, < )ORD for appropriate choices of (G, <). Here the complexity of (G, <)ORD is investigated. We conjecture that for any 2-connected graph G, G ≠ K_k, (G, <)ORD is NP-complete. This is verified for almost all 2-connected graphs. Several related problems are formulated and discussed. © 1995 John Wiley & Sons, Inc.     

Chebyshev expansions and rational approximations

Let A(z) = A_m(z) + a_mz^mB(z,m) where A_m(z) is a polynomial in z of degree m-1. Suppose A(z) and B(z,m) are approximated by main diagonal Padé approximations of order n and r respectively. Suppose that the number of operations needed to evaluate both sides of the above equations by means of the Padé approximations and polynomial noted are the same. Thus 4n = 3m + 4r. We address ourselves to the question of which procedure is more efficient? That is, which procedure produces the smallest error? A variant of this problem is the situation where A(z) and B(z,m) are approximated by their representations in infinite series of Chebyshev polynomials of the first kind truncated after n and r terms respectively. Here n = m + r.Let F(z) have two different series type representations in overlapping or completely disjoint regions of the complex z-plane. Suppose that for each representation there is a sequence of rational approximations of the same type, say of the Padé class, which converge for |arg z| < π except possibly for some finite set of points. Assume that the number of machine operations required to make evaluations using the noted approximations are the same. Again, we ask which procedure is best? Other variants are studied.General answers to the above questions are not known. Instead, we illustrate the ideas for a number of the rather common special functions.     

ON THE COMPUTATIONAL COMPLEXITY OF THE MAXIMUM TRADE PROBLEM

ＯＮＴＨＥＣＯＭＰＵＴＡＴＩＯＮＡＬＣＯＭＰＬＥＸＩＴＹＯＦＴＨＥＭＡＸＩＭＵＭＴＲＡＤＥＰＲＯＢＬＥＭＺ．－Ｑ．Ｌｕｏ；Ｄ．Ｌ．ＰＡＲＮＡＳ（ＣｏｍｍｕｎｉｃａｔｉｏｎｓＲｅｓｅａｒｃｈＬａｂｏｒａｔｏｃｙＤｅｐａｒｔｍｅｎｔｏｆＥｌｅｃｔｒｉｃａ...