The Bertini irreducibility theorem for higher codimensional slices

In [3], Poonen and Slavov recently developed a novel approach to Bertini irreducibility theorems over an arbitrary field, based on random hyperplane slicing. In this paper, we extend their work by proving an analogous bound for the dimension of the exceptional locus in the setting of linear subspaces of higher codimensions.     

Quantum algorithm for neighborhood preserving embedding

Neighborhood preserving embedding (NPE) is an important linear dimensionality reduction technique that aims at preserving the local manifold structure. NPE contains three steps, i.e., finding the nearest neighbors of each data point, constructing the weight matrix, and obtaining the transformation matrix. Liang et al. proposed a variational quantum algorithm (VQA) for NPE [Phys. Rev. A 101 032323 (2020)]. The algorithm consists of three quantum sub-algorithms, corresponding to the three steps of NPE, and was expected to have an exponential speedup on the dimensionality n. However, the algorithm has two disadvantages: (i) It is not known how to efficiently obtain the input of the third sub-algorithm from the output of the second one. (ii) Its complexity cannot be rigorously analyzed because the third sub-algorithm in it is a VQA. In this paper, we propose a complete quantum algorithm for NPE, in which we redesign the three sub-algorithms and give a rigorous complexity analysis. It is shown that our algorithm can achieve a polynomial speedup on the number of data points m and an exponential speedup on the dimensionality n under certain conditions over the classical NPE algorithm, and achieve a significant speedup compared to Liang et al.'s algorithm even without considering the complexity of the VQA.     

全局优化问题的一个新的无参数填充函数

求全局最优化问题的填充函数算法被提出以来，参数的选取和调整一直是制约算法有效性的因素。如何在实际的计算过程中选取合适的参数，直接影响和决定了运算速度和效率。因此，构造不含参数的填充函数就显得极为重要。提出一个新的无参数的填充函数，对其理论性质进行了分析，并给出相应的填充函数算法，数值计算验证了算法的有效性。     

Performance guarantees of forward and reverse greedy algorithms for minimizing nonsupermodular nonsubmodular functions on a matroid

This letter studies the problem of minimizing increasing set functions, equivalently, maximizing decreasing set functions, over the base matroid. This setting has received great interest, since it generalizes several applied problems including actuator and sensor placement problems in control, task allocation problems, video summarization, and many others. We study two greedy heuristics, namely, the forward and reverse greedy. We provide two novel performance guarantees for the approximate solutions obtained by them depending on both submodularity ratio and curvature.     

基于Caputo导数的分数阶非线性振动系统响应计算

研究了含分数阶Caputo导数的非线性振动系统响应的数值计算方法。首先，由Caputo分数阶导数算子的叠加关系，得到含分数阶导数项非线性振动系统状态方程的标准形式。其次，基于Caputo导数与Riemann-Liouville导数和Grunwald-Letnikov导数间的关系，推导计算了Caputo导数的一般数值迭代格式。本文方法不要求状态方程中各分数阶导数阶数相等，弱化了已有算法中对分数阶导数阶数的限制，并可推广到多自由度的情形。随后，选择若干有解析解的算例验证了本文方法的正确性。最后，以多吸引子共存的分数阶Duffing振子系统为例，比较Caputo和GL两种算法所得结果，说明了用GL算法求解存在的问题。     

Gear shifting multi-objective optimization to improve vehicle performance,fuel consumption,and engine emissions

In the present work, the Adaptive-Weight Genetic Algorithm was employed in order to determine the gear shifting strategies that allow an automobile to work in the best compromise among fuel consumption, engine emissions, and vehicle performance. For the assessment of each of the three objective functions, a simulation model based on engine data and on the well-established equations of the longitudinal dynamics was developed. The driving cycle chosen for the calculations was the FTP-75, which takes into account both cold and hot starts, meaning that the transient operation during the warm-up of the catalyst is also considered.     

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.     

求解矩阵方程AXB+CXD=F参数迭代法的最优参数分析

本文针对求矩阵方程AXB+CXD=F唯一解的参数迭代法，分析当矩阵A，B，C，D均是Hermite正（负）定矩阵时，迭代矩阵的特征值表达式，给出了最优参数的确定方法，并提出了相应的加速算法.     

Linearly χ-bounding (P6, C4)-free graphs*

Given two graphs and , a graph is -free if it contains no induced subgraph isomorphic to or . Let and be the path on vertices and the cycle on vertices, respectively. In this paper we show that for any -free graph it holds that , where and are the chromatic number and clique number of , respectively. Our bound is attained by several graphs, for instance, the 5-cycle, the Petersen graph, the Petersen graph with an additional universal vertex, and all -critical -free graphs other than (see Hell and Huang [Discrete Appl. Math. 216 (2017), pp. 211–232]). The new result unifies previously known results on the existence of linear -binding functions for several graph classes. Our proof is based on a novel structure theorem on -free graphs that do not contain clique cutsets. Using this structure theorem we also design a polynomial time -approximation algorithm for coloring -free graphs. Our algorithm computes a coloring with colors for any -free graph in time.     

关于负超几何分布期望与方差算法的注记

研究了非还原取样模型中负超几何随机变量的联合分布,得到了若干有用的推论.据此给出了负超几何分布的期望和方差的一种分解算法.