带机器准备时间的两台同型机复合半在线排序问题

本文研究了预知两种信息,带机器准备时间的两台同型平行机复合半在线排序问题,即已知所有工件加工时间总和和工件按加工时间非增顺序到达,目标为极小化最大机器完工时间的半在线排序模型.我们分析了它的下界,并给出了竞争比为7/6的最优算法.     

带机器准备时间的m台平行机在线和半在线排序

本文研究了目标为极大化机器最早完工时间的带机器准备时间的m台平行机在线和半在线排序问题.对于在线排序问题,本文证明了LS算法的竞争比为m.对于已知所有工件加工时间总和(sum)和最大工件加工时间(max)的两个半在线模型,本文分析了它们的下界,并给出了竞争比均为m-1的最优算法.     

平行机在线排序综述

平行机排序是一类重要的组合优化问题,列表在线排序是在线问题研究形成和发展的重要推手,也是成果最为丰富的在线问题之一.本文回顾以最大完工时间为目标的在线和半在线排序问题的最新进展,总结工件可拒绝、机器可增加及目标为机器负载的Lp范数等3类复杂目标在线排序问题的主要结果,介绍竞争比近似方案、带建议的在线算法和多样化算法性能指标等3个在线排序新课题.     

带复合信息的三台平行机半在线排序问题

本文讨论在已知加工工件总长度(sum)以及机器带一个缓冲区(buffer)两个复合信息下的同型平行机半在线排序问题． Dosa和He研究了当机器数m=2时的情形,设计出竞争比为5／4的最优半在线算法．本文将其情况推广到三台机器,给出竞争比为4／3的半在线算法,并得到一个11／9的问题下界．     

带两个服务等级的三台机最优在线算法

研究了带服务等级约束的三台平行机在线排序问题.每台机器和每个工件的服务等级为1或者2,工件只能在等级不高于它的机器上加工,即等级为1的工件只能在等级为1的机器上加工,等级为2的工件可在所有机器上加工.每个工件的加工时间为一个单位,目标是极小化所有工件的总完工时间.考虑两种情形:当一台机器等级为1,两台机器等级为2时,给出了竞争比为17/14的最优在线算法;当两台机器等级为1,一台机器等级为2时,给出了竞争比为43/36的最优在线算法.     

带机器准备时间的机器覆盖问题的在线、半在线算法

研究以极大化最小机器负载为目标的机器带准备时间的同型机排序问题.证明了LS算法是求解该问题的最好的在线算法,它的最坏情况界为1/m.同时给出了求解两台机的预先知道工件最大加工时间,预先知道工件集的总加工时间以及预先知道工件从大到小到达这三种情形下最好的半在线算法,这三个算法的最坏情况界分别为2/3,2/3以及3/4.     

具有特殊工件的平行机在线排序问题

本文研究一类具有特殊工件的平行机在线排序问题,目标是最小化最大完工时间.此模型有两种工件:正常工件和特殊工件.正常工件能够在m台平行机的任何一台机器上加工,而特殊工件仅能够在它唯一被指定的机器上加工.文中所有特殊工件的指定机器为M1.我们提供了竞争比为(2m2-2m 1)/(m2-m 1)的在线近似算法.当m=2时,算法是最好可能的.当m=3时,算法的竞争比为13/7≈1.857,并且提供了竞争比的下界(1 (平方根33))14≈1.686.     

带机器准备时间的平行机在线与半在线排序

本文研究带机器准备时间的m台平行机系统在线和半在线排序问题.对在线排序问题,我们证明了LS算法的最坏情况界为2-1/m.对已知工件加工时间递减,已知总加工时间和已知工件最大加工时间三个半在线模型,我们分析了它们的下界和所给算法的最坏情况界.对其中两台机情形均得到了最好近似算怯。     

平行机半在线排序问题研究(Ⅰ)

对半在线平行机排序问题的研究进展作了详细综述和进一步探讨。文章给出半在线排序问题的背景、定义、分类和求解。介绍它们定义和在不同机器环境和目标函数下半在线排序问题分类，以及第一类半在线模型的近似算法的设计及其竞争比分析。     

加工时间可控和简单线性增长的平行机排序

本文研究加工时间可控并随开工时间简单线性增长的平行机排序问题.证明了该问题为NP-难问题,该问题存在满足以下性质的最优排序:每个工件的加工时间要么完全压缩,要么完全不压缩;每台机器的工件排序由一个工件参数和控制变量的函数的递增序给出.通过将问题等价转换为0-1非线性整数规划问题,给出了平行机排序问题的贪婪算法.     

不含三角形图的$A_\alpha$-谱半径的界

设$G$是简单无向图. 对于实数$\alpha \in [0,1]$, Nikiforov于2017年定义图的$A_\alpha$-矩阵为$A_\alpha(G)=\alpha D(G)+(1-\alpha)A(G)$, 其中$A(G)$和$D(G)$分别为图$G$的邻接矩阵和度对角矩阵. 图的$A_\alpha$-矩阵可以看着是图的邻接矩阵和无符号拉普拉斯矩阵的共同推广, 其最大特征值称为图的$A_\alpha$- 谱半径. 对于$\alpha\in[0,1)$, 本文确定了不含三角形图的$A_\alpha$-谱半径的一个下界;对于$\alpha \in[1/2, 1)$, 本文确定了不含三角形$k$圈图的$A_\alpha$-谱半径的一个上界.     

High-Dimensional Shape Fitting in Linear Time

Let $P$ be a set of $n$ points in $\Re^d$. The {\em radius} of a $k$-dimensional flat ${\cal F}$ with respect to $P$, which we denote by ${\cal RD}({\cal F},P)$, is defined to be $\max_{p \in P} \mathop{\rm dist}({\cal F},p)$, where $\mathop{\rm dist}({\cal F},p)$ denotes the Euclidean distance between $p$ and its projection onto ${\cal F}$. The $k$-flat radius of $P$, which we denote by ${R^{\rm opt}_k}(P)$, is the minimum, over all $k$-dimensional flats ${\cal F}$, of ${\cal RD}({\cal F},P)$. We consider the problem of computing ${R^{\rm opt}_k}(P)$ for a given set of points $P$. We are interested in the high-dimensional case where $d$ is a part of the input and not a constant. This problem is NP-hard even for $k = 1$. We present an algorithm that, given $P$ and a parameter $0 < \eps \leq 1$, returns a $k$-flat ${\cal F}$ such that ${\cal RD}({\cal F},P) \leq (1 + \eps) {R^{\rm opt}_k}(P)$. The algorithm runs in $O(nd C_{\eps,k})$ time, where $C_{\eps,k}$ is a constant that depends only on $\eps$ and $k$. Thus the algorithm runs in time linear in the size of the point set and is a substantial improvement over previous known algorithms, whose running time is of the order of $d n^{O(k/\eps^c)}$, where $c$ is an appropriate constant.     

加权Banach空间中随机函数列 { tλn (ω) } 的完备性与闭包

该文研究了随机函数列{ t^{λn (ω)} } 在加权Banach空间$C_{\alpha}$中的完备性与闭包.其中$C_{\alpha}$表示在正实轴上连续且满足当,$t\rightarrow +\infty$时,$|f(t)|{\rm e}^{-\alpha(t)}\rightarrow0$的连续复函数组成的Banach空间.     

Limitations of VCG-based mechanisms

We consider computationally-efficient truthful mechanisms that use the VCG payment scheme, and study how well they can approximate the social welfare in auction settings. We present a novel technique for setting lower bounds on the approximation ratio of this type of mechanisms. Our technique is based on setting lower bounds on the communication complexity by analyzing combinatorial properties of the algorithms. Specifically, for combinatorial auctions among submodular (and thus also subadditive) bidders we prove an $\Omega \left( {m^{\tfrac{1} {6}} } \right)$\Omega \left( {m^{\tfrac{1} {6}} } \right) lower bound, which is close to the known upper bound of ${\rm O}\left( {m^{\tfrac{1} {2}} } \right)${\rm O}\left( {m^{\tfrac{1} {2}} } \right), and qualitatively higher than the constant factor approximation possible from a purely computational point of view.     

基于基底合并的分片稀疏恢复

如我们所知,诸如视频和图像等信号可以在某些框架下被表示为稀疏信号,因此稀疏恢复(或稀疏表示)是信号处理、图像处理、计算机视觉、机器学习等领域中被广泛研究的问题之一.通常大多数在稀疏恢复中的有效快速算法都是基于求解$l^0$或者$l^1$优化问题.但是,对于求解$l^0$或者$l^1$优化问题以及相关算法所得到的理论充分性条件对信号的稀疏性要求过严.考虑到在很多实际应用中,信号是具有一定结构的,也即,信号的非零元素具有一定的分布特点.在本文中,我们研究分片稀疏恢复的唯一性条件和可行性条件.分片稀疏性是指一个稀疏信号由多个稀疏的子信号合并所得.相应的采样矩阵是由多个基底合并组成.考虑到采样矩阵的分块结构,我们引入了子矩阵的互相干性,由此可以得到相应$l^0$或者$l^1$优化问题可精确恢复解的稀疏度的新上界.本文结果表明.通过引入采样矩阵的分块结构信息.可以改进分片稀疏恢复的充分性条件.以及相应$l^0$或者$l^1$优化问题整体稀疏解的可靠性条件.     

Unrelated parallel-machine scheduling with deterioration effects and deteriorating multi-maintenance activities for minimizing the total completion time

This paper investigates scheduling problems with simultaneous considerations of deterioration effects and deteriorating multi-maintenance activities on unrelated parallel machines. We examine two models of scheduling with the deterioration effect, namely the job-dependent and position-dependent deterioration model and the time-dependent deterioration model. We assume that each machine may be subject to several maintenance activities over the scheduling horizon, and the duration of maintenance on a machine depends on its running time. Moreover, due to the restriction of the budget of maintenance, the upper bound of the total maintenance frequencies on all the machines is assumed to be known in advance. The objective is to find jointly the optimal maintenance frequencies, the optimal maintenance positions, and the optimal job sequences such that the total completion time is minimized. If the number of machines is fixed, we introduce polynomial time solutions for all the versions of the problem under study.     

关于带运输的单机调度在线问题的研究

本文研究了带运输机的单机在线调度问题。问题假设工件实时在线到达,系统中有一台运输机,该运输机每次最多运输$k$个工件,每个工件需要先在单机上完成加工,然后再被运输机运往目的地,问题的优化目标为最小化完工时间,即所有工件被加工完并且运往目的地的时间最短。针对该问题,作者研究了工件满足一致性条件的模型,并且基于贪心思想给出了竞争比为$\frac{\sqrt{5}+1}{2}$的在线算法,并且证明该算法是最优在线算法。     

Hardy-Orlicz 空间到 Bloch-Orlicz 型空间上的复合算子

Let φ be an analytic self-map of D. The composition operator C_φ is the operator defined on H(D) by C_φ(f) = f ? φ. In this paper, we investigate the boundedness and compactness of the composition operator C_φ from Hardy-Orlicz spaces to Bloch-Orlicz type spaces.     

关于带运输的单机调度在线问题的研究

本文研究了带运输机的单机在线调度问题。问题假设工件实时在线到达,系统中有一台运输机,该运输机每次最多运输$k$个工件,每个工件需要先在单机上完成加工,然后再被运输机运往目的地,问题的优化目标为最小化完工时间,即所有工件被加工完并且运往目的地的时间最短。针对该问题,作者研究了工件满足一致性条件的模型,并且基于贪心思想给出了竞争比为$\frac{\sqrt{5}+1}{2}$的在线算法,并且证明该算法是最优在线算法。     

On Poincaré-Friedrichs Type Inequalities for the Broken Sobolev Space ${\rm W}^{2,1}$

We are concerned with the derivation of Poincaré-Friedrichs type inequalities in the broken Sobolev space $W^{2,1}$($Ω$; $\mathcal{T}_h$) with respect to a geometrically conforming, simplicial triagulation $\mathcal{T}_h$ of a bounded Lipschitz domain $Ω$ in $\mathbb{R}^d$ , $d$ $∈$ $\mathbb{N}$. Such inequalities are of interest in the numerical analysis of nonconforming finite element discretizations such as ${\rm C}^0$ Discontinuous Galerkin (${\rm C}^0$${\rm DG}$) approximations of minimization problems in the Sobolev space $W^{2,1}$($Ω$), or more generally, in the Banach space $BV^2$($Ω$) of functions of bounded second order total variation. As an application, we consider a ${\rm C}^0$${\rm DG}$ approximation of a minimization problem in$BV^2$($Ω$) which is useful for texture analysis and management in image restoration.