Polynomial time approximation schemes for dense instances of minimum constraint satisfaction

It is known that large fragments of the class of dense Minimum Constraint Satisfaction (MIN‐CSP) problems do not have polynomial time approximation schemes (PTASs) contrary to their Maximum Constraint Satisfaction analogs. In this paper we prove, somewhat surprisingly, that the minimum satisfaction of dense instances of kSAT ‐formulas, and linear equations mod 2, Ek‐LIN2, do have PTASs for any k. The MIN‐Ek‐LIN2 problems are equivalent to the k‐ary versions of the Nearest Codeword problem, the problem which is known to be exceedingly hard to approximate on general instances. The method of solution of the above problems depends on the development of a new density sampling technique for k‐uniform hypergraphs which could be of independent interest. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 23: 73–91, 2003     

A new approximation technique for resource‐allocation problems

We develop a rounding method based on random walks in polytopes, which leads to improved approximation algorithms and integrality gaps for several assignment problems that arise in resource allocation and scheduling. In particular, it generalizes the work of Shmoys and Tardos on the generalized assignment problem to the setting where some jobs can be dropped. New concentration bounds for random bipartite matching are developed as well.     

A randomized method for one‐step extrapolation in reverse time migration

Reverse time migration has drawn great attention in exploration geophysics because it can be used successfully in areas with large structural and velocity complexity. But its computational cost is considerably high. This paper concerns the fast implementation of the optimized separable approximation of the two‐way propagator, which is the most computational expensive step in reverse time migration. On the basis of the low‐rank property of the propagator and the idea of randomized algorithm, a randomized method is introduced for optimized separable approximation‐based one‐step extrapolation. Numerical results of approximating the propagator show that the randomized method is more efficient than the conventional interpolation method. At the same time, numerical experiments of wavefield extrapolation show that the proposed method is much more accurate than the conventional finite‐difference plus pseudo‐spectrum scheme. Copyright © 2014 John Wiley & Sons, Ltd.     

The power of standard information for multivariate approximation in the randomized setting

We study approximating multivariate functions from a reproducing kernel Hilbert space with the error between the function and its approximation measured in a weighted -norm. We consider functions with an arbitrarily large number of variables, , and we focus on the randomized setting with algorithms using standard information consisting of function values at randomly chosen points.

We prove that standard information in the randomized setting is as powerful as linear information in the worst case setting. Linear information means that algorithms may use arbitrary continuous linear functionals, and by the power of information we mean the speed of convergence of the th minimal errors, i.e., of the minimal errors among all algorithms using function evaluations. Previously, it was only known that standard information in the randomized setting is no more powerful than the linear information in the worst case setting.

We also study (strong) tractability of multivariate approximation in the randomized setting. That is, we study when the minimal number of function evaluations needed to reduce the initial error by a factor is polynomial in  (strong tractability), and polynomial in and (tractability). We prove that these notions in the randomized setting for standard information are equivalent to the same notions in the worst case setting for linear information. This result is useful since for a number of important applications only standard information can be used and verifying (strong) tractability for standard information is in general difficult, whereas (strong) tractability in the worst case setting for linear information is known for many spaces and is relatively easy to check.

We illustrate the tractability results for weighted Korobov spaces. In particular, we present necessary and sufficient conditions for strong tractability and tractability. For product weights independent of , we prove that strong tractability is equivalent to tractability.

We stress that all proofs are constructive. That is, we provide randomized algorithms that enjoy the maximal speed of convergence. We also exhibit randomized algorithms which achieve strong tractability and tractability error bounds.

     

轨道逼近时间集的密度

任意给定0pq1,证明了在符号系统中(进而在帐篷映射中)存在Mycielski集C,使得C中任意两个互异的点的轨道按照下密度p,上密度q的"速率"逼近.构造了线段上的连续映射,使其具有一个满Lebesgue测度的Mycielski集S,使得S中任意两个互异的点的轨道按照下密度p,上密度q的"速率"逼近.     

Approximating average parameters of graphs

Inspired by Feige (36th STOC, 2004), we initiate a study of sublinear randomized algorithms for approximating average parameters of a graph. Specifically, we consider the average degree of a graph and the average distance between pairs of vertices in a graph. Since our focus is on sublinear algorithms, these algorithms access the input graph via queries to an adequate oracle. We consider two types of queries. The first type is standard neighborhood queries (i.e., what is the ith neighbor of vertex v?), whereas the second type are queries regarding the quantities that we need to find the average of (i.e., what is the degree of vertex v? and what is the distance between u and v?, respectively). Loosely speaking, our results indicate a difference between the two problems: For approximating the average degree, the standard neighbor queries suffice and in fact are preferable to degree queries. In contrast, for approximating average distances, the standard neighbor queries are of little help whereas distance queries are crucial. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

Low‐rank approximation of tensors via sparse optimization

The goal of this paper is to find a low‐rank approximation for a given nth tensor. Specifically, we give a computable strategy on calculating the rank of a given tensor, based on approximating the solution to an NP‐hard problem. In this paper, we formulate a sparse optimization problem via an l₁‐regularization to find a low‐rank approximation of tensors. To solve this sparse optimization problem, we propose a rescaling algorithm of the proximal alternating minimization and study the theoretical convergence of this algorithm. Furthermore, we discuss the probabilistic consistency of the sparsity result and suggest a way to choose the regularization parameter for practical computation. In the simulation experiments, the performance of our algorithm supports that our method provides an efficient estimate on the number of rank‐one tensor components in a given tensor. Moreover, this algorithm is also applied to surveillance videos for low‐rank approximation.     

A linearized heat‐conducting fluid and its quasi‐static approximation

A linearized flow of a compressible inviscid heat‐conducting fluid is considered and a comparison is made with its coupled/quasi‐static approximation. Copyright © 2005 John Wiley & Sons, Ltd.     

A certain class of weighted statistical convergence and associated Korovkin‐type approximation theorems involving trigonometric functions

The subject of statistical convergence has attracted a remarkably large number of researchers due mainly to the fact that it is more general than the well‐established theory of the ordinary (classical) convergence. In the year 2013, Edely et al 17 introduced and studied the notion of weighted statistical convergence. In our present investigation, we make use of the (presumably new) notion of the deferred weighted statistical convergence to present Korovkin‐type approximation theorems associated with the periodic functions , and defined on a Banach space . In particular, we apply our concept of the deferred weighted statistical convergence with a view to proving a Korovkin‐type approximation theorem for periodic functions and also to demonstrate that our result is a nontrivial extension of several known Korovkin‐type approximation theorems which were given in earlier works. Moreover, we establish another result for the rate of the deferred weighted statistical convergence for the same set of functions. Finally, we consider a number of interesting special cases and illustrative examples in support of our definitions and of the results which are presented in this paper.     

Symmetrical weighted essentially non‐oscillatory‐flux limiter schemes for Hamilton–Jacobi equations

In this paper, we propose a new scheme that combines weighted essentially non‐oscillatory (WENO) procedures together with monotone upwind schemes to approximate the viscosity solution of the Hamilton–Jacobi equations. In one‐dimensional (1D) case, first, we obtain an optimum polynomial on a four‐point stencil. This optimum polynomial is third‐order accurate in regions of smoothness. Next, we modify a second‐order ENO polynomial by choosing an additional point inside the stencil in order to obtain the highest accuracy when combined with the Harten–Osher reconstruction‐evolution method limiter. Finally, the optimum polynomial is considered as a symmetric and convex combination of three polynomials with ideal weights. Following the methodology of the classic WENO procedure, then, we calculate the non‐oscillatory weights with the ideal weights. Numerical experiments in 1D and 2D are performed to compare the capability of the hybrid scheme to WENO schemes. Copyright © 2015 John Wiley & Sons, Ltd.     

The variational approximation for 2‐dimension solitons at cubic‐quintic nonlinearity in quasiperiodic potentials

We apply the variational approximation to study the dynamics of solitary waves of the nonlinear Schrödinger equation with compensative cubic‐quintic nonlinearity for asymmetric 2‐dimension setup. Such an approach allows to study the behavior of the solitons trapped in quasisymmetric potentials without an axial symmetry. Our analytical consideration allows finding the soliton profiles that are stable in a quasisymmetric geometry. We show that small perturbations of such states lead to generation of the oscillatory‐bounded solutions having 2 independent eigenfrequencies relating to the quintic nonlinear parameter. The behavior of solutions with large amplitudes is studied numerically. The resonant case when the frequency of the time variations (time managed) potential is near of the eigenfrequencies is studied too. In a resonant situation, the solitons acquire a weak time decay.     

Blended kernel approximation in the ℋ︁‐matrix techniques

Several types of ??‐matrices were shown to provide a data‐sparse approximation of non‐local (integral) operators in FEM and BEM applications. The general construction is applied to the operators with asymptotically smooth kernel function provided that the Galerkin ansatz space has a hierarchical structure. The new class of ??‐matrices is based on the so‐called blended FE and polynomial approximations of the kernel function and leads to matrix blocks with a tensor‐product of block‐Toeplitz (block‐circulant) and rank‐k matrices. This requires the translation (rotation) invariance of the kernel combined with the corresponding tensor‐product grids. The approach allows for the fast evaluation of volume/boundary integral operators with possibly non‐smooth kernels defined on canonical domains/manifolds in the FEM/BEM applications. (Here and in the following, we call domains canonical if they are obtained by translation or rotation of one of their parts, e.g. parallelepiped, cylinder, sphere, etc.) In particular, we provide the error and complexity analysis for blended expansions to the Helmholtz kernel. Copyright © 2002 John Wiley & Sons, Ltd.     

Renormalization group second‐order approximation for singularly perturbed nonlinear ordinary differential equations

We consider a 2 time scale nonlinear system of ordinary differential equations. The small parameter of the system is the ratio ϵ of the time scales. We search for an approximation involving only the slow time unknowns and valid uniformly for all times at order O(ϵ²). A classical approach to study these problems is Tikhonov's singular perturbation theorem. We develop an approach leading to a higher order approximation using the renormalization group (RG) method. We apply it in 2 steps. In the first step, we show that the RG method allows for approximation of the fast time variables by their RG expansion taken at the slow time unknowns. Next, we study the slow time equations, where the fast time unknowns are replaced by their RG expansion. This allows to rigorously show the second order uniform error estimate. Our result is a higher order extension of Hoppensteadt's work on the Tikhonov singular perturbation theorem for infinite times. The proposed procedure is suitable for problems from applications, and it is computationally less demanding than the classical Vasil'eva‐O'Malley expansion. We apply the developed method to a mathematical model of stem cell dynamics.     

Bounded approximation properties in non‐archimedean Banach spaces

Some non‐archimedean bounded approximation properties are introduced and studied in this paper. As an application, an affirmative answer is given, for non‐spherically complete base fields, to the following problem, posed in 13 , p. 95: Does there exist an absolutely convex edged set B in a non‐archimedean locally convex space such that its closure $\overline{B}Some non‐archimedean bounded approximation properties are introduced and studied in this paper. As an application, an affirmative answer is given, for non‐spherically complete base fields, to the following problem, posed in 13 , p. 95: Does there exist an absolutely convex edged set B in a non‐archimedean locally convex space such that its closure $\overline{B}$ is not edged?     

Anisotropic dilations of shift‐invariant subspaces and approximation properties in

Let A be an expansive linear map in . Approximation properties of shift‐invariant subspaces of when they are dilated by integer powers of A are studied. Shift‐invariant subspaces providing approximation order α or density order α associated to A are characterized. These characterizations impose certain restrictions on the behavior of the spectral function at the origin expressed in terms of the concept of point of approximate continuity. The notions of approximation order and density order associated to an isotropic dilation turn out to coincide with the classical ones introduced by de Boor, DeVore and Ron. This is no longer true when A is anisotropic. In this case the A‐dilated shift‐invariant subspaces approximate the anisotropic Sobolev space associated to A and α. Our main results are also new when S is generated by translates of a single function. The obtained results are illustrated by some examples.     

The approximation properties via the Grothendieck p‐compact sets

A stronger form of compactness, which is due to Grothendieck's criterion of compact sets in Banach spaces, generates an approximation property which is formally weaker than the classical approximation property. In the paper, we investigate this approximation property in a more general setting.     

A domination algorithm for {0,1}‐instances of the travelling salesman problem

We present an approximation algorithm for ‐instances of the travelling salesman problem which performs well with respect to combinatorial dominance. More precisely, we give a polynomial‐time algorithm which has domination ratio . In other words, given a ‐edge‐weighting of the complete graph on vertices, our algorithm outputs a Hamilton cycle of with the following property: the proportion of Hamilton cycles of whose weight is smaller than that of is at most . Our analysis is based on a martingale approach. Previously, the best result in this direction was a polynomial‐time algorithm with domination ratio for arbitrary edge‐weights. We also prove a hardness result showing that, if the Exponential Time Hypothesis holds, there exists a constant such that cannot be replaced by in the result above. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 427–453, 2016     

Higher order numerical approximation for time dependent singularly perturbed differential‐difference convection‐diffusion equations

In this article, we develop a higher order numerical approximation for time dependent singularly perturbed differential‐difference convection‐diffusion equations. A priori bounds on the exact solution and its derivatives, which are useful for the error analysis of the numerical method are given. We approximate the retarded terms of the model problem using Taylor's series expansion and the resulting time‐dependent singularly perturbed problem is discretized by the implicit Euler scheme on uniform mesh in time direction and a special hybrid finite difference scheme on piecewise uniform Shishkin mesh in spatial direction. We first prove that the proposed numerical discretization is uniformly convergent of , where and denote the time step and number of mesh‐intervals in space, respectively. After that we design a Richardson extrapolation scheme to increase the order of convergence in time direction and then the new scheme is proved to be uniformly convergent of . Some numerical tests are performed to illustrate the high‐order accuracy and parameter uniform convergence obtained with the proposed numerical methods.