Laplace's method for the laws of heat processes on loop spaces

In this paper, we will consider Laplace's method for a class of heat processes on loop spaces. We will obtain the first term of the asymptotics under assumptions that the function under consideration attains its minimum at a unique point and that the Hessian at the point is non-degenerate. This kind of process was first introduced by P. Malliavin in 1990 for the loop group case and then gradually generalized by various authors. Our tool is the rough path theory of T. Lyons. This technique was pioneered by S. Aida for finite-dimensional processes in his unpublished paper.     

Computational complexity of isothermic DNA sequencing by hybridization

In the paper, the computational complexity of several variants of the problem of isothermic DNA sequencing by hybridization, is analyzed. The isothermic sequencing is a recent method, in which isothermic oligonucleotide libraries are used during the hybridization with an unknown DNA fragment. The variants of the isothermic DNA sequencing problem with errors in the hybridization data, negative ones or positive ones, are proved to be strongly NP-hard. On the other hand, the polynomial time algorithm for the ideal case with no errors is proposed.     

考虑策略型消费者和退货的零售商降价促销决策研究

基于零售商降价促销问题,引入策略型消费者,考虑到异质性消费者有可能对商品不满意,构建两期决策模型,旨在从退货和价格路径优化两方面提高零售商利润。研究给出(不)允许退货时,零售商面对策略型消费者的定价建议,指出零售商制定价格要在一定程度上参考商品类型。订货量相同时,给出策略型消费者降低零售商的期望利润的条件;面对短视型或者策略型消费者时,允许退货可在特定条件下提升零售商利润。消费者退货成本越高,对策略型消费者消极影响的抑制作用越明显,零售商的利润增长越显著。最后,通过数值算例分析了在两种退货决策以及不同退货成本下产品类型对零售商定价的影响,以及退货措施对策略型消费者消极影响的作用。     

Monochromatic k-edge-connection colorings of graphs

A path in an edge-colored graph $G$ is called monochromatic if any two edges on the path have the same color. For $k\ge 2$, an edge-colored graph $G$ is said to be monochromatic $k$-edge-connected if every two distinct vertices of $G$ are connected by at least $k$ edge-disjoint monochromatic paths, and $G$ is said to be uniformly monochromatic $k$-edge-connected if every two distinct vertices are connected by at least $k$ edge-disjoint monochromatic paths such that all edges of these $k$ paths are colored with a same color. We use $m{c}_k\left(G\right)$ and $um{c}_k\left(G\right)$ to denote the maximum number of colors that ensures $G$ to be monochromatic $k$-edge-connected and, respectively, $G$ to be uniformly monochromatic $k$-edge-connected. In this paper, we first conjecture that for any $k$-edge-connected graph $G$, $m{c}_k\left(G\right)=e\left(G\right)-e\left(H\right)+\lfloor \frac{k}{2}\rfloor$, where $H$ is a minimum $k$-edge-connected spanning subgraph of $G$. We verify the conjecture for $k=2$. We also prove the conjecture for $G=K_{k+1}$ and $G=K_{k,n}$ with $n\ge k\ge 3$. When $G$ is a minimal $k$-edge-connected graph, we give an upper bound of $m{c}_k\left(G\right)$, i.e., $m{c}_k\left(G\right)\le k-1$. For the uniformly monochromatic $k$-edge-connectivity, we prove that for all $k$, $um{c}_k\left(G\right)=e\left(G\right)-e\left(H\right)+1$, where $H$ is a minimum $k$-edge-connected spanning subgraph of $G$.     

An Efficient Algorithm for Finding a Maximum Weight k-Independent Set on Trapezoid Graphs

The maximum weight k-independent set problem has applications in many practical problems like k-machines job scheduling problem, k-colourable subgraph problem, VLSI design layout and routing problem. Based on DAG (Directed Acyclic Graph) approach, an O(kn ²) time sequential algorithm is designed in this paper to solve the maximum weight k-independent set problem on weighted trapezoid graphs. The weights considered here are all non-negative and associated with each of the n vertices of the graph.     

On packing 3‐vertex paths in a graph

Let G be a connected graph and let eb(G) and λ(G) denote the number of end‐blocks and the maximum number of disjoint 3‐vertex paths Λ in G. We prove the following theorems on claw‐free graphs: (t1) if G is claw‐free and eb(G) ≤ 2 (and in particular, G is 2‐connected) then λ(G) = ⌊| V(G)|/3⌋; (t2) if G is claw‐free and eb(G) ≥ 2 then λ(G) ≥ ⌊(| V(G) | − eb(G) + 2)/3 ⌋; and (t3) if G is claw‐free and Δ^*‐free then λ(G) = ⌊| V(G) |/3⌋ (here Δ^* is a graph obtained from a triangle Δ by attaching to each vertex a new dangling edge). We also give the following sufficient condition for a graph to have a Λ‐factor: Let n and p be integers, 1 ≤ p ≤ n − 2, G a 2‐connected graph, and |V(G)| = 3n. Suppose that G − S has a Λ‐factor for every S ⊆ V(G) such that |S| = 3p and both V(G) − S and S induce connected subgraphs in G. Then G has a Λ‐factor. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 175–197, 2001     

对Floyd算法的两点注记

本给Floyd算法配置了一种更便于使用的路径标记方法,还给出了在无向网络上减少Floyd算法的计算量的方法。     

带时间窗的车间搬运机器人路径优化建模及算法研究

本文以车间搬运机器人为研究对象,在考虑时间窗的前提下,求解机器人进行物料配送和成品回收场景下的路径优化问题。提出一种强化学习遗传蚁群算法,首先利用扫描法求解初始搬运机器人的数量,并将子路径节点的几何中心设置为虚拟节点,利用嵌入遗传算子的蚁群算法求解连接虚拟节点的最优路径,再利用强化学习算法求解子路径的最优结果;最后将基本成本、运输成本和时间惩罚成本的加权和作为目标解,并最终求出满足约束条件的最优解。通过与基准问题求解结果对比,验证了强化学习遗传蚁群算法的优越性。     

Finding the shortest paths by node combination

By repeatedly combining the source node’s nearest neighbor, we propose a node combination (NC) method to implement the Dijkstra’s algorithm. The NC algorithm finds the shortest paths with three simple iterative steps: find the nearest neighbor of the source node, combine that node with the source node, and modify the weights on edges that connect to the nearest neighbor. The NC algorithm is more comprehensible and convenient for programming as there is no need to maintain a set with the nodes’ distances. Experimental evaluations on various networks reveal that the NC algorithm is as efficient as Dijkstra’s algorithm. As the whole process of the NC algorithm can be implemented with vectors, we also show how to find the shortest paths on a weight matrix.