Long Time Asymptotic Behavior of Solution of Difference Scheme for a Semilinear Parabolic Equation

In this paper we prove that the solution of implicit difference scheme for a semilinear parabolic equation converges to the solution of difference scheme for the corresponding nonlinear stationary problem as $t\rightarrow\infty$. For the discrete solution of nonlinear parabolic problem, we get its long time asymptotic behavior which is similar to that of the continuous solution. For simplicity, we consider one-dimensional problem.     

WDM网络中的排序与波长分配问题的一个多项式时间近似方案

本文考虑基于波分复用技术 (WDM)的光学网络中的排序与波长分配问题 .在波长数目固定的情况下 ,我们证明此问题是NP 困难问题 ,并且给出一个多项式时间近似方案 .若波长数目不固定 ,我们证明此问题不存在多项式时间近似方案     

Advertisement allocation for generalized second-pricing schemes

Recently, there has been a surge of interest in algorithms that allocate advertisement space in an online revenue-competitive manner. Most such algorithms, however, assume a pay-as-you-bid pricing scheme. In this paper, we study the query allocation problem where the ad space is priced using the well-known and widely used generalized second-price (GSP) scheme. We observe that the previous algorithms fail to achieve a bounded competitive ratio under the GSP scheme. On the positive side, we present online constant-competitive algorithms for the problem.     

Analysis of a meshless method for the time fractional diffusion-wave equation

In this paper a numerical technique is proposed for solving the time fractional diffusion-wave equation. We obtain a time discrete scheme based on finite difference formula. Then, we prove that the time discrete scheme is unconditionally stable and convergent using the energy method and the convergence order of the time discrete scheme is \(\mathcal {O}(\tau ^{3-\alpha })\). Firstly, we change the main problem based on Dirichlet boundary condition to a new problem based on Robin boundary condition and then, we consider a semi-discrete scheme with Robin boundary condition and show when \(\beta \rightarrow +\infty \) solution of the main semi-discrete problem with Dirichlet boundary condition is convergent to the solution of the new semi-discrete problem with Robin boundary condition. We consider the new semi-discrete problem with Robin boundary condition and use the meshless Galerkin method to approximate the spatial derivatives. Finally, we obtain an error bound for the new problem. We prove that convergence order of the numerical scheme based on Galekin meshless is \(\mathcal {O}(h)\). In the considered method the appeared integrals are approximated using Gauss Legendre quadrature formula. The main aim of the current paper is to obtain an error estimate for the meshless Galerkin method based on the radial basis functions. Numerical examples confirm the efficiency and accuracy of the proposed scheme.     

Black-Scholes期权定价模型的五点式混合差分方法

研究了欧式看涨期权定价问题的差分方法,将Black-Scholes方程等价代换为标准抛物型偏微分方程,在时间方向上采用前、后差商,空间方向上采用五点差分格式,再引入参数θ建立一个稳定的混合差分格式.根据Von Neumann条件证明了该格式的稳定性及收敛性,并通过数值计算的实际应用,结果表明该算法适用于到期日较长的期权...     

Existence and smoothness of continuous and discrete solutions of a two-dimensional shallow water problem over movable beds

We consider a two-dimensional shallow water system over movable beds. We begin with a continuous system and prove the existence of the solutions, and then we investigate their smoothness. Then, we employ a Galerkin method to obtain a finite-dimensional problem which is solved using a Brouwer fixed point theorem. Therefore, we show that the limits of the resulting solution sequences satisfy the model equations.After solving the continuous problem, we focus on the corresponding discrete problem. We employ a local discontinuous Galerkin scheme for numerical solution of the discrete system and conduct an error analysis of the numerical scheme. We prove that the method is convergent and that the error is bounded according to a specific norm defined herein.     

Tri-directional Scheduling Scheme: Theory and Computation

In this paper we introduce a new scheduling scheme based on so called tri-directional scheduling strategy to solve the well known resource constrained project scheduling problem. In order to demonstrate the effectiveness of tri-directional scheduling scheme, it is incorporated into a priority rule based parallel scheduling scheme. Theoretical and numerical investigations show that the tri-directional scheduling scheme outperforms forward, backward and even bidirectional schemes depending on the problem structure and the priority rule used. Based on empirical evidence, it seems that as the number of activities are increased, the tri-directional scheduling scheme performs better irrespective of the priority rule used. This suggests that tri-directional scheme should also be applied within the category of heuristic methods.     

A second-order difference scheme for a parameterized singular perturbation problem

In this paper we consider a singularly perturbed quasilinear boundary value problem depending on a parameter. The problem is discretized using a hybrid difference scheme on Shishkin-type meshes. We show that the scheme is second-order convergent, in the discrete maximum norm, independent of singular perturbation parameter. Numerical experiments support these theoretical results.     

强向量均衡问题与不动点问题的粘性逼近算法

讨论了强向量均衡问题与非扩张映射不动点问题的公共解.首先,给出了强向量均衡问题的辅助问题,并在适当的条件下,证明了其解的存在性和唯一性结果.然后,利用这些结果,提出了强向量均衡问题与非扩张映射不动点问题公共解的粘性逼近算法,并进一步证明了,在适当的条件下,由该算法产生的迭代序列强收敛于强向量均衡问题和非扩张映射不动点问题的公共解.     

一种无证书的环签名方案和一个基于身份的多重签名方案

在这篇文章里,我们用双线性对构造了一种无证书的环签名方案,并证明它是无条件匿名的,且在随机预言模型中,计算性Diffie-Hellman问题是难解的,我们方案在适应性选择消息攻击下是存在性不可伪造的,它的安全性比在基于身份的公钥密码体制下高.本文首次用多线性形式构造了一个基于身份的广播多重签名方案,它的安全性是基于计算性Diffie-Hellman困难问题.     

Applying a Power Penalty Method to Numerically Pricing American Bond Options

In this paper, we aim to develop a numerical scheme to price American options on a zero-coupon bond based on a power penalty approach. This pricing problem is formulated as a variational inequality problem (VI) or a complementarity problem (CP). We apply a fitted finite volume discretization in space along with an implicit scheme in time, to the variational inequality problem, and obtain a discretized linear complementarity problem (LCP). We then develop a power penalty approach to solve the LCP by solving a system of nonlinear equations. The unique solvability and convergence of the penalized problem are established. Finally, we carry out numerical experiments to examine the convergence of the power penalty method and to testify the efficiency and effectiveness of our numerical scheme.     

Numerical solution of retarded initial value problems: Local and global error and stepsize control

Summary Retarded initial value problems are routinely replaced by an initial value problem of ordinary differential equations along with an appropriate interpolation scheme. Hence one can control the global error of the modified problem but not directly the actual global error of the original problem. In this paper we give an estimate for the actual global error in terms of controllable quantities. Further we show that the notion of local error as inherited from the theory of ordinary differential equations must be generalized for retarded problems. Along with the new definition we are led to developing a reliable basis for a step selection scheme.     

在非均匀网格上解椭圆—双曲型偏微分方程奇异摄动问题

本文考察了椭圆一双曲型偏微分方程奇异摄动问题(1.1),证明了迎风差分格式在一特殊的非均匀网格上是一阶一致收敛的.最后给出了一些数值结果.     

A Multi-Stage Stochastic Integer Programming Approach for Capacity Expansion under Uncertainty

This paper addresses a multi-period investment model for capacity expansion in an uncertain environment. Using a scenario tree approach to model the evolution of uncertain demand and cost parameters, and fixed-charge cost functions to model the economies of scale in expansion costs, we develop a multi-stage stochastic integer programming formulation for the problem. A reformulation of the problem is proposed using variable disaggregation to exploit the lot-sizing substructure of the problem. The reformulation significantly reduces the LP relaxation gap of this large scale integer program. A heuristic scheme is presented to perturb the LP relaxation solutions to produce good quality integer solutions. Finally, we outline a branch and bound algorithm that makes use of the reformulation strategy as a lower bounding scheme, and the heuristic as an upper bounding scheme, to solve the problem to global optimality. Our preliminary computational results indicate that the proposed strategy has significant advantages over straightforward use of commercial solvers.     

Stable numerical differentiation for the second order derivatives

Consider a numerical differential problem, which aims to compute the second order derivative of a function stably from its given noisy data. For this ill-posed problem, we introduce the Lavrent′ev regularization scheme by reformulating this differentiation problem as an integral equation of the first kind. The advantage of this proposed scheme is that we can give the regularizing solution by an explicit integral expression, therefore it is easy to be implemented. The a-priori and a-posterior choice strategies for the regularization parameter are considered, with convergence analysis and error estimate of the regularizing solution for noisy data based on the integral operator decomposition. The validity of the proposed scheme is shown by several numerical examples.     

Parallel decomposition methods for linearly constrained problems subject to simple bound with application to the SVMs training

We consider the convex quadratic linearly constrained problem with bounded variables and with huge and dense Hessian matrix that arises in many applications such as the training problem of bias support vector machines. We propose a decomposition algorithmic scheme suitable to parallel implementations and we prove global convergence under suitable conditions. Focusing on support vector machines training, we outline how these assumptions can be satisfied in practice and we suggest various specific implementations. Extensions of the theoretical results to general linearly constrained problem are provided. We included numerical results on support vector machines with the aim of showing the viability and the effectiveness of the proposed scheme.     

On split common fixed point problems

Based on the convergence theorem recently proved by the second author, we modify the iterative scheme studied by Moudafi for quasi-nonexpansive operators to obtain strong convergence to a solution of the split common fixed point problem. It is noted that Moudafi's original scheme can conclude only weak convergence. As a consequence, we obtain strong convergence theorems for split variational inequality problems for Lipschitz continuous and monotone operators, split common null point problems for maximal monotone operators, and Moudafi's split feasibility problem.     

Numerical analysis of a finite volume scheme for a seawater intrusion model with cross‐diffusion in an unconfined aquifer

We consider a degenerate parabolic system modeling the flow of fresh and saltwater in a porous medium in the context of seawater intrusion. We propose and analyze a finite volume scheme based on two‐point flux approximation with upwind mobilities. The scheme preserves at the discrete level the main features of the continuous problem, namely the nonnegativity of the solutions, the decay of the energy and the control of the entropy and its dissipation. Based on these nonlinear stability results, we show that the scheme converges toward a weak solution to the problem. Numerical results are provided to illustrate the behavior of the model and of the scheme.     

Stability of Rothe difference scheme for the reverse parabolic problem with integral boundary condition

In this paper, we study the approximation of reverse parabolic problem with integral boundary condition. The Rothe difference scheme for an approximate solution of reverse problem is discussed. We establish stability and coercive stability estimates for the solution of the Rothe difference scheme. In sequel, we investigate the first order of accuracy difference scheme for approximation of boundary value problem for multidimensional reverse parabolic equation and obtain stability estimates for its solution. Finally, we give numerical results together with an explanation on the realization in one- and two-dimensional test examples.     

A strongly polynomial FPTAS for the symmetric quadratic knapsack problem

The symmetric quadratic knapsack problem (SQKP), which has several applications in machine scheduling, is NP-hard. An approximation scheme for this problem is known to achieve an approximation ratio of (1 + ?) for any ? > 0. To ensure a polynomial time complexity, this approximation scheme needs an input of a lower bound and an upper bound on the optimal objective value, and requires the ratio of the bounds to be bounded by a polynomial in the size of the problem instance. However, such bounds are not mentioned in any previous literature. In this paper, we present the first such bounds and develop a polynomial time algorithm to compute them. The bounds are applied, so that we have obtained for problem (SQKP) a fully polynomial time approximation scheme (FPTAS) that is also strongly polynomial time, in the sense that the running time is bounded by a polynomial only in the number of integers in the problem instance.