On the uniqueness of an element of the best L 1-approximation for functions with values in a banach space

We study the problem of uniqueness of an element of the best L ₁-approximation for continuous functions with values in a Banach space. We prove two theorems that characterize the uniqueness subspaces in terms of certain sets of test functions.     

Problem of uniqueness of an element of the best nonsymmetric <Emphasis Type="Italic">L</Emphasis><Subscript>1</Subscript>-approximation of continuous functions with values in <Emphasis Type="Italic">KB</Emphasis>-spaces

We consider the problem of characterization of subspaces of uniqueness of an element of the best nonsymmetric L ₁-approximation of functions that are continuous on a metric compact set of functions with values in a KB-space. We find classes of test functions that characterize the uniqueness of an element of the best nonsymmetric approximation. Translated from Ukrains'kyi Matematychnyi Zhurnal, Vol. 60, No. 7, pp. 867–878, July, 2008.     

Constrained Lp-Approximation by Generalized n-Convex Functions Induced by ECT-Systems

The problem of finding a best L_p-approximation (1 ≤ p < ∞) to a function in L_p from a special subcone of generalized n-convex functions induced by an ECT-system is considered. Tchebycheff splines with a countably infinite number of knots are introduced and best approximations are characterized in terms of local best approximations by these splines. Various properties of best approximations and their uniqueness in L₁ are investigated. Some special results for generalized monotone and convex cases are obtained.     

Best mean approximation by splines satisfying generalized convexity constraints

A characterization of the best L₁-approximation to a continuous function by classes of fixed-knot polynomial splines which satisfy generalized convexity constraints is presented and uniqueness is shown. Included is the possibility of specifying the positivity, monotonicity, or convexity of the class. The proof of uniqueness uses recently developed results for Hermite-Birkhoff interpolation by splines.     

Generalized Gaussian quadrature formulas

Existence and uniqueness of canonical points for best L₁-approximation from an Extended Tchebycheff (ET) system, by Hermite interpolating “polynomials” with free nodes of preassigned multiplicities, are proved. The canonical points are shown to coincide with the nodes of a “generalized Gaussian quadrature formula” of the form (*) which is exact for the ET-system. In (*), ∑_{j = 0}^{v_i − 2} ≡ 0 if v_i = 1, the v_i (> 0), I = 1,…, n, are the multiplicities of the free nodes and v₀0, v_{n + 1} 0 of the boundary points in the L₁-approximation problem, ∑_{i = 0}^{n + 1} v_i is the dimension of the ET-system, and σ is the weight in the L₁-norm.The results generalize results on multiple node Gaussian quadrature formulas (v₁,…, v_n all even in (*)) and their relation to best one-sided L₁-approximation. They also generalize results on the orthogonal signature of a Tchebycheff system (v₀ = v_{n + 1} = 0, v_i = 1, I = 1,…, n, in (*)), and its role in best L₁-approximation. Recent works of the authors were the first to treat Gaussian quadrature formulas and orthogonal signatures in a unified way.     

On the uniqueness of elements of the best approximation and the best one-sided approximation in the spaceL 1

The problem of the uniqueness of elements of the best approximations in the spaceL ₁ [a, b] is studied. We consider the problem of the best approximation and the best (, )-approximation of continuous functions and the problem of the best one-sided approximation of continuously differentiable functions.Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 46, No. 5, pp. 475–483, May, 1994.     

Best φ-approximation by n-convex functions

A n-convex function defined on a bounded open interval J ₀ n ≥2 is the (n?l)-st indefinite integral of a nondecreasing function. This fact and the simple structure of the latter enable to obtain concrete results about a n-convex best φ approximation g to a function f ? L _φ on J ₀, where φ: [0, ∞) → [0, ∞) is a convex function that generaJizes the p^th -power functions, 1 ≤ p < ∞. It is shown that g may also be a best generalized spline φ approximation to the restriction of f on the maximal subintervals of J₀ where g is a generalized spline. This is the situation in some cases, among which the L_p -approximation is includedp ≥ 1. For n = 2 it is proven that g is a polynomial of best φ-approximation to f ? L _φ on any maximal interval where g is a polynomial. If f is in addition continuous, then this fact implies the uniqueness of g Under the same assumption, it is shown that the best 3-convex L ₁-approximation is also unique whenever its derivative is bounded.     

Property A in an Infinite-Dimensional Space. I

   Abstract. We prove that an infinite-dimensional space of piecewise polynomial functions of degree at most n-1 with infinitely many simple knots, n ≥ 2 , satisfies Property A. Apart from its independent interest, this result allows us to solve an open classical problem (n ≥ 3 ) in theory of best approximation: the uniqueness of best L ₁ -approximation by n -convex functions to an integrable, continuous function defined on a bounded interval. In this first part of the paper we prove the case n=2 and give key results in order to complete the general proof in the second part.     

Approximation in the mean by convex functions

We give elementary proofs for the existence and uniqueness of the best L₁-approximation to a continuous function from the class of convex functions on a closed interval, and describe thebest approximation in terms of certain piecewise linear functions.     

Best one-sided L 1-approximation by harmonic functions

Let , where B is the open unit ball in (), and let denote the collection of functions h in which are harmonic on B and satisfy on . A function h ^* in is called a best harmonic one-sided L ¹-approximant to f if for all h in . This paper characterizes such approximants and discusses questions of existence and uniqueness. Corresponding results for approximation on the cylinder are also established, but the proofs in this case are more difficult and rely on recent work concerning tangential harmonic approximation. The characterizations are quite different in nature from those recently obtained for harmonic L ¹-approximation without a one-sidedness condition. Received: 25 September 1997     

The Gibbs phenomenon for bestL 1-trigonometric polynomial approximation

The classical Gibbs phenomenon for the Fourier sections (bestL ₂-trigonometric polynomial approximants) of a jump function asserts that, near the jump, these sections overshoot the function by an asymptotically constant factorg (theL ₂-Gibbs constant). In this paper we show that, for a class of one-jump discontinuous functions, a similar phenomenon holds for the trigonometric polynomials of bestL ₁-approximation. We determine theL ₁-Gibbs constant , which is substantially smaller thang. Furthermore, we prove that uniform convergence of bestL ₁-approximants takes place on intervals that avoid the jump. In the analysis we obtain some strong uniqueness theorems for bestL ₁-approximants.Communicated by Vladimir N. Temlyakov.     

On a Minimum Linear Classification Problem

We study the following linear classification problem in signal processing: Given a set B of n black point and a set W of m white points in the plane (m=O(n)), compute a minimum number of lines L such that in the arrangement of L each face contain points with the same color (i.e., either all black points or all white points). We call this the Minimum Linear Classification (MLC) problem. We prove that MLC is NP-complete by a reduction from the Minimum Line Fitting (MLF) problem; moreover, a C-approximation to Minimum Linear Classification implies a C-approximation to the Minimum Line Fitting problem. Nevertheless, we obtain an O(log _n )-factor algorithm for MLC and we also obtain an O(log _Z)-factor algorithm for MLC where Z is the minimum number of disjoint axis-parallel black/white rectangles covering B and W.     

An L2 finite element approximation for the incompressible Navier–Stokes equations

This paper utilizes the Picard method and Newton's method to linearize the stationary incompressible Navier–Stokes equations and then uses an LL* approach, which is a least-squares finite element method applied to the dual problem of the corresponding linear system. The LL* approach provides an L²-approximation to a given problem, which is not typically available with conventional finite element methods for nonlinear second-order partial differential equations. We first show that the proposed combination of linearization scheme and LL* approach provides an L²-approximation to the stationary incompressible Navier–Stokes equations. The validity of L²-approximation is proven through the analysis of the weak problem corresponding to the linearized Navier–Stokes equations. Then, the convergence is analyzed, and numerical results are presented.     

Average CaseL∞-Approximation in the Presence of Gaussian Noise

We consider the average caseL_∞-approximation of functions fromC^r([0, 1]) with respect to ther-fold Wiener measure. An approximation is based onnfunction evaluations in the presence of Gaussian noise with varianceσ²>0. We show that the n th minimal average error is of ordern^{−(2r+1)/(4r+4)} ln^1/2 n, and that it can be attained either by the piecewise polynomial approximation using repetitive observations, or by the smoothing spline approximation using non-repetitive observations. This completes the already known results forL_q-approximation withq<∞ andσ0, and forL_∞-approximation withσ=0.     

Nonstationary problem of free convection with radiative heat transfer

Nonstationary problem of free convection of viscous incompressible fluid in a three-dimensional domain with allowance for radiative heat transfer is studied in the framework of the diffusion P₁-approximation of the equation of radiative transfer. The solvability of the problem is proven, and sufficient conditions for the uniqueness are presented.     

Property A in an Infinite-Dimensional Space. I

Abstract. We prove that an infinite-dimensional space of piecewise polynomial functions of degree at most n-1 with infinitely many simple knots, n ≥ 2 , satisfies Property A. Apart from its independent interest, this result allows us to solve an open classical problem (n ≥ 3 ) in theory of best approximation: the uniqueness of best L ₁ -approximation by n -convex functions to an integrable, continuous function defined on a bounded interval. In this first part of the paper we prove the case n=2 and give key results in order to complete the general proof in the second part.     

An Improved Bound on the One-Sided Minimum Crossing Number in Two-Layered Drawings

Given a bipartite graph G = (V,W,E), a two-layered drawing consists of placing nodes in the first node set V on a straight line L₁ and placing nodes in the second node set W on a parallel line L₂. The one-sided crossing minimization problem asks one to find an ordering of nodes in V to be placed on L₁ so that the number of arc crossings is minimized. In this paper we use a 1.4664-approximation algorithm for this problem. This improves the previously best bound 3 due to P. Eades and N. C. Wormald [Edge crossing in drawing bipartite graphs, Algorithmica 11 (1994), 379-403].     

SimultaneousL 1 approximation of a compact set of real-valued functions

Summary In this paper the uniqueness results found in simultaneous Chebychev approximation are extended to simultaneousL ₁ approximation. In particular a sufficient condition to guarantee uniqueness of a best approximate to aL ₁ compact set is given.This paper is taken in part from a thesis to be submitted by M. P. Carroll in partial fulfillment of the requirements for the Ph. D. degree in the Department of Mathematics at Rensselaer Polytechnic Institute.     

Le n-ondes de lax pour le probleme mixte (the n-waves of lax for initial-boundary value problem)

We Confirm two conjectures of Lax about Glimm's weak solutions for initial boundary value problem whose data have compact support; asmptotic decay as t^-1/2 of the total variation in the genuinely nonlinear case and L¹ -approximation by N-waves or travelling-waves in general case; it is boundary's version of Liu's results [Li2].     

All-norm approximation algorithms

A major drawback in optimization problems and in particular in scheduling problems is that for every measure there may be a different optimal solution. In many cases the various measures are different ℓ_p norms. We address this problem by introducing the concept of an all-norm ρ-approximation algorithm, which supplies one solution that guarantees ρ-approximation to all ℓ_p norms simultaneously. Specifically, we consider the problem of scheduling in the restricted assignment model, where there are m machines and n jobs, each job is associated with a subset of the machines and should be assigned to one of them. Previous work considered approximation algorithms for each norm separately. Lenstra et al. [Math. Program. 46 (1990) 259–271] showed a 2-approximation algorithm for the problem with respect to the ℓ_∞ norm. For any fixed ℓ_p norm the previously known approximation algorithm has a performance of θ(p). We provide an all-norm 2-approximation polynomial algorithm for the restricted assignment problem. On the other hand, we show that for any given ℓ_p norm (p>1) there is no PTAS unless P=NP by showing an APX-hardness result. We also show for any given ℓ_p norm a FPTAS for any fixed number of machines.