MacNeille completions and canonical extensions

Let be a variety of monotone bounded lattice expansions, that is, bounded lattices endowed with additional operations, each of which is order preserving or reversing in each coordinate. We prove that if is closed under MacNeille completions, then it is also closed under canonical extensions. As a corollary we show that in the case of Boolean algebras with operators, any such variety is generated by an elementary class of relational structures.

Our main technical construction reveals that the canonical extension of a monotone bounded lattice expansion can be embedded in the MacNeille completion of any sufficiently saturated elementary extension of the original structure.

     

A (2+ϵ)-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective

We give a $(2+?)$-approximation algorithm for minimizing total weighted completion time on a single machine under release time and precedence constraints. This settles a recent conjecture on the approximability of this scheduling problem (Skutella, 2016).     

Approximating total weighted completion time on identical parallel machines with precedence constraints and release dates

We present a $(2+2ln2+\epsilon )$-approximation algorithm for the classical nonpreemptive scheduling problem to minimize the total weighted completion time of jobs on identical parallel machines subject to release dates and precedence constraints, improving upon the previously best known 4-approximation algorithm from 1998. The result carries over to the more general problem with precedence delays and generalizes a recent result by Li (2017) for the problem without release dates or delays.     

Toeplitz矩阵填充的四种流形逼近算法比较

 本文提出Toeplitz矩阵填充的四种流形逼近算法。在左奇异向量空间中对已知部分运用最小二乘法逼近,形成新的可行矩阵;并将对角线上的元素分别用均值,l₁范数,l_∞范数和中间数四种方法逼近使得迭代后的矩阵仍保持Toeplitz结构,节约了奇异向量空间的分解时间。最终找到合理的低秩矩阵来逼近未知的高秩矩阵,进而精确地完成Toeplitz矩阵的填充。理论上,分析了在一定条件下算法的收敛性。实验上,通过取不同的采样密度进行数值实验展示了四种算法的优劣。实验结果说明均值算法和l_∞范数算法大多用的时间较少,但是当采样密度和矩阵规模较大时,中间数算法的精度较高。     

Completing orientations of partially oriented graphs

We initiate a general study of what we call orientation completion problems. For a fixed class of oriented graphs, the orientation completion problem asks whether a given partially oriented graph P can be completed to an oriented graph in by orienting the (nonoriented) edges in P. Orientation completion problems commonly generalize several existing problems including recognition of certain classes of graphs and digraphs as well as extending representations of certain geometrically representable graphs. We study orientation completion problems for various classes of oriented graphs, including k‐arc‐strong oriented graphs, k‐strong oriented graphs, quasi‐transitive‐oriented graphs, local tournaments, acyclic local tournaments, locally transitive tournaments, locally transitive local tournaments, in‐tournaments, and oriented graphs that have directed cycle factors. We show that the orientation completion problem for each of these classes is either polynomial time solvable or NP‐complete. We also show that some of the NP‐complete problems become polynomial time solvable when the input‐oriented graphs satisfy certain extra conditions. Our results imply that the representation extension problems for proper interval graphs and for proper circular arc graphs are polynomial time solvable. The latter generalizes a previous result.     

求解低秩矩阵填充的改进的交替最速下降法

矩阵填充是指利用矩阵的低秩特性而由部分观测元素恢复出原矩阵,在推荐系统、信号处理、医学成像、机器学习等领域有着广泛的应用。采用精确线搜索的交替最速下降法由于每次迭代计算量小因而对大规模问题的求解非常有效。本文在其基础上采用分离地精确线搜索,可使得每次迭代下降更多但计算量相同,从而可望进一步提高计算效率。本文分析了新算法的收敛性。数值结果也表明所提出的算法更加有效。     

序半群Quantale完备化的进一步结果

本文给出了序半群上幂集Quantale的最大拓扑闭包的具体形式,即序半群的最小Quantale完备化.在此基础上,证明了Quantale范畴Quant是序半群范畴OSGrp*的满的反射子范畴.最后,给出了序半群Quantale完备化的一个应用.     

Scheduling two agents with controllable processing times

We consider several two-agent scheduling problems with controllable job processing times, where agents A and B have to share either a single machine or two identical machines in parallel while processing their jobs. The processing times of the jobs of agent A are compressible at additional cost. The objective function for agent B is always the same, namely a regular function _fmax$f_{\text{max}}$. Several different objective functions are considered for agent A, including the total completion time plus compression cost, the maximum tardiness plus compression cost, the maximum lateness plus compression cost and the total compression cost subject to deadline constraints (the imprecise computation model). All problems are to minimize the objective function of agent A subject to a given upper bound on the objective function of agent B. These problems have various applications in computer systems as well as in operations management. We provide NP-hardness proofs for the more general problems and polynomial-time algorithms for several special cases of the problems.     

The Spectrum of （gv,g, 3, λ）-dDF in Zgv

In this paper, several recursive constructions for directed difference family and perfect directed difference family are presented by means of difference matrix and incomplete difference matrix. Finally the necessary and sufficient conditions for the existence of a （gv, g, 3, λ）-directed difference family in Zgv are established. As a consequence, the necessary and sufficient conditions for the existence of a cyclic directed group divisible design with block size three and type gv are obtained.