Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width

The Multicut problem can be defined as: given a graph G and a collection of pairs of distinct vertices {s_i,t_i} of G, find a minimum set of edges of G whose removal disconnects each s_i from the corresponding t_i. Multicut is known to be NP-hard and Max SNP-hard even when the input graph is restricted to being a tree. The main result of the paper is a polynomial-time approximation scheme (PTAS) for Multicut in unweighted graphs with bounded degree and bounded tree-width. That is, for any ε>0, we present a polynomial-time (1+ε)-approximation algorithm. In the particular case when the input is a bounded-degree tree, we have a linear-time implementation of the algorithm. We also provide some hardness results: we prove that Multicut is still NP-hard for binary trees and that it is Max SNP-hard if we drop any of the three conditions (unweighted, bounded-degree, bounded tree-width). Finally we show that some of these results extend to the vertex version of Multicut and to a directed version of Multicut.     

压缩系数的微粒群优化算法的收敛性分析

该文利用矩阵理论对具有随机数的压缩系数的微粒群优化算法进行了收敛性分析,给出了c=d=1和c=1两种收敛性结果,同时图形化给出了参数选择准则.     

A Hybrid Approach to Scheduling with Earliness and Tardiness Costs

A hybrid technique using constraint programming and linear programming is applied to the problem of scheduling with earliness and tardiness costs. The linear model maintains a set of relaxed optimal start times which are used to guide the constraint programming search heuristic. In addition, the constraint programming problem model employs the strong constraint propagation techniques responsible for many of the advances in constraint programming for scheduling in the past few years. Empirical results validate our approach and show, in particular, that creating and solving a subproblem containing only the activities with direct impact on the cost function and then using this solution in the main search, significantly increases the number of problems that can be solved to optimality while significantly decreasing the search time.     

Stancu-Kantorovich算子在Orlicz空间的逼近阶

研究了Stancu-Kantorovich算子在Orlicz空间的逼近估计     

Optimal volume-corrected laplace-metropolis method

The article provides a refinement for the volume-corrected Laplace-Metropolis estimator of the marginal likelihood of DiCiccioet al. The correction volume of probability α in DiCiccioet al. is fixed and suggested to take the value α=0.05. In this article α is selected based on an asymptotic analysis to minimize the mean square relative error (MSRE). This optimal choice of α is shown to be invariant under linear transformations. The invariance property leads to easy implementation for multivariate problems. An implementation procedure is provided for practical use. A simulation study and a real data example are presented.     

Radiation Transfer in a Binary, Stochastic Medium with Strongly Fluctuating Parameters

The propagation of radiation in a three-dimensional, inhomogeneous, stochastic, scattering medium and in an equivalent homogeneous medium has been investigated by the small-angle iteration method. The statistical structure of the scattering parameters of a three-dimensional medium has been described within the framework of the two-dimensional Poisson process and the binary Markov process. The analytical data obtained point to the fact that the three-dimensional inhomogeneity of a stochastic medium significantly influences the radiation transfer in it.     

正系数多项式倒数逼近的点态和整体估计

利用Ditzian-Totik光滑模对于[0,1]上定义的非角连续函数f(x)，且f(x)≠0，文中证明存在正系数多项式Pn(x)及常数C，使得|f9x)-1/Pn(x)|≤Cωψ^λ（f,n^-1/2(ψ(x) 1/√n)^1-λ)。当λ＝1时，上述结果导出已有的整体估计，而当0≤λ＜1时，得到倒数逼近一个新的点态局部估计。     

Finite-Part Integrals and Modified Splines

We first state a uniform convergence theorem for finite-part integrals which are derivatives of weighted Cauchy principal value integrals. We then give a two-stage process to modify approximating splines and optimal nodal splines in such a way that the conditions of this theorem are satisfied. Consequently, these modified splines can be used in the numerical evaluation of these finite-part integrals.     

原始地应力及力学参数的测定

本文根据孔壁应力解除法获得的量测应变,提出了采用最优化方法直接确定岩体的泊松比和原始地应力。实例表明,这样获得的原始地应力更符合实际——对应最小的量测残差。