Approximating the single source unsplittable min-cost flow problem

In the single source unsplittable min-cost flow problem, commodities must be routed simultaneously from a common source vertex to certain destination vertices in a given graph with edge capacities and costs; the demand of each commodity must be routed along a single path so that the total flow through any edge is at most its capacity. Moreover, the total cost must not exceed a given budget. This problem has been introduced by Kleinberg [7] and generalizes several NP-complete problems from various areas in combinatorial optimization such as packing, partitioning, scheduling, load balancing, and virtual-circuit routing. Kolliopoulos and Stein [9] and Dinitz, Garg, and Goemans [4] developed algorithms improving the first approximation results of Kleinberg for the problem of minimizing the violation of edge capacities and for other variants. However, known techniques do not seem to be capable of providing solutions without also violating the cost constraint. We give the first approximation results with hard cost constraints. Moreover, all our results dominate the best known bicriteria approximations. Finally, we provide results on the hardness of approximation for several variants of the problem. Received: August 23, 2000 / Accepted: April 20, 2001?Published online October 2, 2001     

Error Estimates for Multilevel Approximation Using Polyharmonic Splines

Polyharmonic splines are used to interpolate data in a stationary multilevel iterative refinement scheme. By using such functions the necessary tools are provided to obtain simple pointwise error bounds on the approximation. Linear convergence between levels is shown for regular data on a scaled multiinteger grid, and a multilevel domain decomposition method.     

T-C模型中虚光子过程对光场压缩效应的影响

利用全量子理论,研究非旋波近似下TC模型中受激场的压缩效应.结果表明:非旋波近似下,由于虚光场的影响,Q的演化曲线出现了“小锯齿状”,表现为系统的量子噪声,随着ω和n的增大,量子噪声分别减小和增大,虚光子过程使光场的压缩程度明显加深;研究结果还揭示了原子场耦合系数λ及原子间耦合系数g与光场压缩效应的关系. 关键词： T-C模型 非旋波近似 压缩效应 量子噪声     

Phonon density of states of ann-component alloy

We have generalized the coherent potential approximation (CPA) of Tripathi and Behera to the case of ann-component alloy. It is seen that then-component CPA density of states reproduces the binary, ternary quartenary alloys etc when the appropriate limits are adopted.     

对称正交反对称矩阵反问题解存在的条件

矩阵反问题和矩阵特征值反问题在科学和工程技术中具有广泛的应用,有关它们的研究已取得了许多进展[1,2].[3]和[4]分别研究了反对称矩阵反问题和双反对称矩阵特征值反问题等.本文研究一类更广泛的对称正交反对称矩阵反问题.用Rn×m（Cn×m）表示n×m实（复）矩阵的全体,ASRn×n表示n阶反对称矩阵的全体,ABSRn×n表示n阶双反对称矩阵的全体,ORn×n表示n阶正交矩阵的全体.A+表示矩阵A的Moore-Penrose广义逆.In表示n阶单位矩阵.ei表示n阶单位矩阵的第i列,Sn=[en,en-1,     

Multiscale kernels

This paper reconstructs multivariate functions from scattered data by a new multiscale technique. The reconstruction uses standard methods of interpolation by positive definite reproducing kernels in Hilbert spaces. But it adopts techniques from wavelet theory and shift-invariant spaces to construct a new class of kernels as multiscale superpositions of shifts and scales of a single compactly supported function φ. This means that the advantages of scaled regular grids are used to construct the kernels, while the advantages of unrestricted scattered data interpolation are maintained after the kernels are constructed. Using such a multiscale kernel, the reconstruction method interpolates at given scattered data. No manipulations of the data (e.g., thinning or separation into subsets of certain scales) are needed. Then, the multiscale structure of the kernel allows to represent the interpolant on regular grids on all scales involved, with cheap evaluation due to the compact support of the function φ, and with a recursive evaluation technique if φ is chosen to be refinable. There also is a wavelet-like data reduction effect, if a suitable thresholding strategy is applied to the coefficients of the interpolant when represented over a scaled grid. Various numerical examples are presented, illustrating the multiresolution and data compression effects.     

Discrete approximation of integral operators

A method to approximate the eigenvalues of linear operators depending on an unknown distribution is introduced and applied to weighted sums of squared normally distributed random variables. This area of application includes the approximation of the asymptotic null distribution of certain degenerated U- and V-statistics.

     

Approximation of Matrices and a Family of Gander Methods for Polar Decomposition

Two matrix approximation problems are considered: approximation of a rectangular complex matrix by subunitary matrices with respect to unitarily invariant norms and a minimal rank approximation with respect to the spectral norm. A characterization of a subunitary approximant of a square matrix with respect to the Schatten norms, given by Maher, is extended to the case of rectangular matrices and arbitrary unitarily invariant norms. Iterative methods, based on the family of Gander methods and on Higham’s scaled method for polar decomposition of a matrix, are proposed for computing subunitary and minimal rank approximants. Properties of Gander methods are investigated in details. AMS subject classification (2000) 65F30, 15A18     

Variational extension of the mean spherical approximation to arbitrary dimensions

We generalize a variational principle for the mean spherical approximation for a system of charged hard spheres in 3D to arbitrary dimensions. We first construct a free energy variational trial function from the Debye-Hückel excess charging internal energy at a finite concentration and an entropy obtained at the zero-concentration limit by thermodynamic integration. In three dimensions the minimization of this expression with respect to the screening parameter leads to the mean spherical approximation, usually obtained by solution of the Ornstein-Zernike equation. This procedure, which interpolates naturally between the zero concentration/coupling limit and the high-concentration/ coupling limit, is extended to arbitrary dimensions. We conjecture that this result is also equivalent to the MSA as originally defined, although a technical proof of this point is left for the future. The Onsager limitT ΔS ^MSA /ΔE ^MSA → 0 for infinite concentration/coupling is satisfied for all d ≠ 2, while ford=2 this limit is 1. On leave from Department of Physics, University of Puerto Rico, Mayagüez Campus, Mayagüez, Puerto Rico, 00681.     

总延误问题顺时安排法的性能比

给定一组工件的加工时间与工期，要求确定这些工件在一台机器上的加．工排列，使相应的总延误达到最小，这就是总延误问题．该问题在近年已被证明是NP困难的．由Wilkermn和Irwin（1971），林勋（1983）等所研究的顺时安排法能得到相邻交换意义下的局部解．在本文中，我们进一步证明该算法能得到前移邻域意义下的局部解，并确定了该算法的性能比．