Explore the vast range of titles available.

This work proposes and analyzes a Smolyak-type sparse grid stochastic collocation method for the approximation of statistical quantities related to the solution of partial differential equations with random coefficients and forcing terms (input data of the model). To compute solution statistics, the sparse grid stochastic collocation method uses approximate solutions, produced here by finite elements, corresponding to a deterministic set of points in the random input space. This naturally requires solving uncoupled deterministic problems as in the Monte Carlo method. If the number of random variables needed to describe the input data is moderately large, full tensor product spaces are computationally expensive to use due to the curse of dimensionality. In this case the sparse grid approach is still expected to be competitive with the classical Monte Carlo method. Therefore, it is of major practical relevance to understand in which situations the sparse grid stochastic collocation method is more efficient than Monte Carlo. This work provides error estimates for the fully discrete solution using L q norms and analyzes the computational efficiency of the proposed method. In particular, it demonstrates algebraic convergence with respect to the total number of collocation points and quantifies the effect of the dimension of the problem (number of input random variables) in the final estimates. The derived estimates are then used to compare the method with Monte Carlo, indicating for which problems the former is more efficient than the latter. Computational evidence complements the present theory and shows the effectiveness of the sparse grid stochastic collocation method compared to full tensor and Monte Carlo approaches.

We give the full solution of the following problem: obtain sharp inequalities between the moduli of smoothness The main tool is the new Hardy–Littlewood–Nikol’skii inequalities. More precisely, we obtained the asymptotic behavior of the quantity We also prove the Ulyanov and Kolyada-type inequalities in the Hardy spaces. Finally, we apply the obtained estimates to derive new embedding theorems for the Lipschitz and Besov spaces.

The aim of this work is to adapt the complex analytic methods originating in modern Oka theory to the study of non-orientable conformal minimal surfaces in All our new tools mentioned above apply to non-orientable minimal surfaces endowed with a fixed choice of a conformal structure. This enables us to obtain significant new applications to the global theory of non-orientable minimal surfaces. In particular, we construct proper non-orientable conformal minimal surfaces in

We study the early work scheduling problem on identical parallel machines in order to maximize the total early work, i.e., the parts of non-preemptive jobs that are executed before a common due date. By preprocessing and constructing an auxiliary instance which has several good properties, for any desired accuracy ε , we propose an efficient polynomial time approximation scheme with running time O f ( 1 / ε n ) , where n is the number of jobs and f ( 1 / ε ) is exponential in 1 / ε , and a fully polynomial time approximation scheme with running time O 1 ε 2 m + 1 + n when the number of machines is fixed.

A convex polynomial is a convex combination of the monomials {1,𝑥,𝑥2,...}. This paper establishes that the convex polynomials on ℝ are dense in 𝐿𝑝(𝜇) and weak* dense in 𝐿∞(𝜇) whenever 𝜇 is a compactly supported regular Borel measure on ℝ and 𝜇([—1,∞)) = 0. It is also shown that the convex polynomials are norm dense in 𝐶(𝐾) precisely when 𝐾⋂[−1,∞) = ⌀, where 𝐾 is a compact subset of the real line. Moreover, the closure of the convex polynomials on [-1,𝑏] is shown to be the functions that have a convex power series representation. A continuous linear operator 𝑇 on a locally convex space 𝑋 is convex-cyclic if there is a vector 𝑥 ∈ 𝑋 such that the convex hull of the orbit of 𝑥 is dense in 𝑋. The previous results are used to characterize which multiplication operators on various real Banach spaces are convex-cyclic. Also, it is shown for certain multiplication operators that every nonempty closed invariant convex set is a closed invariant subspace.

In this paper, we discuss scheduling problems with m identical machines and n jobs where each job has to be assigned to some machine. The objective is to minimize the weighted makespan of jobs, i.e., the maximum weighted completion time of jobs. This scheduling problem is a generalization of minimizing the makespan on parallel machine scheduling problem. We present a ( 2 - 1 m )-approximation algorithm and a randomized efficient polynomial time approximation scheme (EPTAS) for the problem. We also design a randomized fully polynomial time approximation scheme (FPTAS) for the special case when the number of machines is fixed.

We consider the problem of estimating the support size of a discrete distribution whose minimum nonzero mass is at least 1 k . Under the independent sampling model, we show that the sample complexity, that is, the minimal sample size to achieve an additive error of εk with probability at least 0.1 is within universal constant factors of k log k log 2 1 ε , which improves the state-of-the-art result of k ε 2 log k in [In Advances in Neural Information Processing Systems (2013) 2157–2165]. Similar characterization of the minimax risk is also obtained. Our procedure is a linear estimator based on the Chebyshev polynomial and its approximation-theoretic properties, which can be evaluated in O(n+log² k) time and attains the sample complexity within constant factors. The superiority of the proposed estimator in terms of accuracy, computational efficiency and scalability is demonstrated in a variety of synthetic and real datasets.

Stimulated by salient applications arising from power systems, this paper studies a class of non-linear Knapsack problems with non-separable quadratic constrains, formulated in either binary or integer form. These problems resemble the duals of the corresponding variants of 2-weighted Knapsack problem (a.k.a., complex-demand Knapsack problem) which has been studied in the extant literature under the paradigm of smart grids. Nevertheless, the employed techniques resulting in a polynomial-time approximation scheme (PTAS) for the 2-weighted Knapsack problem are not amenable to its minimization version. We instead propose a greedy geometry-based approach that arrives at a quasi PTAS (QPTAS) for the minimization variant with boolean variables. As for the integer formulation, a linear programming-based method is developed that obtains a PTAS. In view of the curse of dimensionality, fast greedy heuristic algorithms are presented, additionally to QPTAS. Their performance is corroborated extensively by empirical simulations under diverse settings and scenarios.

Polynomial approximations constructed using a least-squares approach form a ubiquitous technique in numerical computation. One of the simplest ways to generate data for leastsquares problems is with random sampling of a function. We discuss theory and algorithms for stability of the least-squares problem using random samples. The main lesson from our discussion is that the intuitively straightforward (\"standard\") density for sampling frequently yields suboptimal approximations, whereas sampling from a non-standard density, called the induced distribution, yields near-optimal approximations. We present a recent theory that demonstrates why sampling from the induced distribution is optimal and provide several numerical experiments that support the theory. Software is also provided that reproduces the figures in this paper.

In this paper, we will present a strong (or pathwise) approximation of standard Brownian motion by a class of orthogonal polynomials. The coefficients that are obtained from the expansion of Brownian motion in this polynomial basis are independent Gaussian random variables. Therefore, it is practical (i.e., requires N independent Gaussian coefficients) to generate an approximate sample path of Brownian motion that respects integration of polynomials with degree less than N. Moreover, since these orthogonal polynomials appear naturally as eigenfunctions of the Brownian bridge covariance function, the proposed approximation is optimal in a certain weighted L²(ℙ) sense. In addition, discretizing Brownian paths as piecewise parabolas gives a locally higher order numerical method for stochastic differential equations (SDEs) when compared to the piecewise linear approach. We shall demonstrate these ideas by simulating inhomogeneous geometric Brownian motion (IGBM). This numerical example will also illustrate the deficiencies of the piecewise parabola approximation when compared to a new version of the asymptotically efficient log-ODE (or Castell-Gaines) method.