广义线性多乘积问题的完全多项式时间近似算法

本文针对广义线性多乘积极小化问题,通过一系列的线性规划问题的解提出一种求其全局最优解的完全多项式时间近似算法,并给出该算法的计算复杂性,且数值算例验证该算法是可行的.     

相机位姿估计的加速正交迭代算法

面对需要实时计算的相机位姿估计问题,针对经典的广泛应用的正交迭代算法,提出了一种加速正交迭代算法。其关键思想是将每一次迭代过程规整化,从而提炼出每一次迭代的重复计算,若将此重复计算在迭代开始前提前计算,则可以大幅度的减少迭代过程中的计算量,使得每一次迭代的计算复杂度从O(n)降低为O(1)。因此,可以在更短的时间内迭代更多的次数,从而获得更高的精度。进行了对比实验,结果显示本加速算法计算精度更高,速度更快。并通过实验提出了选择稳健n点透视(RPn P)计算初值,再使用加速正交迭代算法进行迭代运算的方法,在控制点不多的情况下,是一种精度接近最大似然估计,计算速度最快的算法。     

基于背景最佳滤波尺度的红外图像复杂度评价准则

提出一种基于背景最佳滤波尺度的红外图像复杂度评价准则来解决传统方法评价背景效果较差的问题. 同时, 这种方法还可以为红外图像滤波提供最佳高通滤波尺度信息, 从而对红外图像进行性能最佳滤波. 首先, 生成高斯仿真目标并与红外图像进行融合, 获得包含仿真目标及真实红外背景的图像. 然后, 在不同高斯滤波尺度下对图像滤波, 并计算滤波后仿真目标的信噪比. 最后, 取滤波后目标信噪比最大时的滤波尺度作为背景最佳滤波尺度, 使用该尺度可评价红外图像的复杂度. 另外, 本文还使用数学模型推导了红外图像最佳滤波尺度, 得出最佳滤波尺度的数学表达式. 大量实验表明: 1) 本文推导的最佳滤波尺度数学表达式与实验曲线吻合. 2) 这种方法在评价红外图像复杂度方面比传统的基于信息熵的方法效果要好很多. 并且这种方法获取的红外背景复杂度为滤波最佳尺度, 可以直接利用这项指标对图像进行最佳滤波从而更好地检测弱小目标. 3) 仿真目标尺度越大, 最佳滤波尺度也会相应增大. 因此, 在评价图像复杂度时, 应使用相同尺度的仿真目标, 不同图像之间才具备可比性. 同时, 最佳滤波尺度与仿真目标的强度无关. 4) 本文算法使用的滤波器宜用高斯及Butterworth高通滤波器实现. 5) 本文提出的方法不仅可以有效分析红外视频的复杂度, 并且可以通过复杂度的变化分析图像内容的突变.     

On the expressive power of CNF formulas of bounded tree- and clique-width

We study representations of polynomials over a field K from the point of view of their expressive power. Three important examples for the paper are polynomials arising as permanents of bounded tree-width matrices, polynomials given via arithmetic formulas, and families of so called CNF polynomials. The latter arise in a canonical way from families of Boolean formulas in conjunctive normal form. To each such CNF formula there is a canonically attached incidence graph. Of particular interest to us are CNF polynomials arising from formulas with an incidence graph of bounded tree- or clique-width.We show that the class of polynomials arising from families of polynomial size CNF formulas of bounded tree-width is the same as those represented by polynomial size arithmetic formulas, or permanents of bounded tree-width matrices of polynomial size. Then, applying arguments from communication complexity we show that general permanent polynomials cannot be expressed by CNF polynomials of bounded tree-width. We give a similar result in the case where the clique-width of the incidence graph is bounded, but for this we need to rely on the widely believed complexity theoretic assumption #P?FP/poly.     

Thompson＇s Group F and the Linear Group GL∞（Z）

The authors study the finite decomposition complexity of metric spaces of H, equipped with different metrics, where H is a subgroup of the linear group GL_∞(ℤ). It is proved that there is an injective Lipschitz map φ: (F, d _S ) → (H, d), where F is the Thompson’s group, dS the word-metric of F with respect to the finite generating set S and d a metric of H. But it is not a proper map. Meanwhile, it is proved that φ: (F, d _S ) → (H, d ₁) is not a Lipschitz map, where d ₁ is another metric of H.     

Two-machine flow shop scheduling problem with an outsourcing option

We consider a two-machine flow shop problem in which each job is processed through an in-house system or outsourced to a subcontractor. A schedule is established for the in-house jobs, and performance is measured by the makespan. Jobs processed by subcontractors require paying an outsourcing cost. The objective is to minimize the sum of the makespan and total outsourcing costs. We show that the problem is NP-hard in the ordinary sense. We consider a special case in which each job has a processing requirement, and each machine a characteristic value. In this case, the time a job occupies a machine is equal to the job’s processing requirement plus a setup time equal to the characteristic value of that machine. We introduce some optimality conditions and present a polynomial-time algorithm to solve the special case.     

Single courier single restaurant meal delivery (without routing)

We investigate optimization models for meal delivery that do not involve routing. We focus on the simplest case, with a single restaurant and a single courier, and reduce it to the throughput maximization single machine scheduling problem, with release times and bounded slacks. In the meal delivery setting, slacks are small for QoS purposes and we indeed show that the scheduling problem can be solved in polynomial time when slacks are bounded. We discuss extensions to more couriers and restaurants.