贪婪格点路径的一些性质

设{Xv:v∈Zd}是一族独立同分布的随机变量序列,对Zd上的任意一路径π,定义S(π)=∑v∈πXv,记Mn=maxπ∈Π0(n)S(π),Π0(n)表示从原点出发大小为n的自不相交的路径的全体.论文讨论Mn的性质,得到了类似完全收敛性的结果,即对任意的ε>0,∑∞n=11nPMnn-M>ε<∞.另外还讨论了Xv允许取负值的情形,得到类似的结果,从而推广了Gandolfi和Kesten所研究的贪婪格点路径模型.     

CO2在Cu表面还原成碳氢化合物的DFT计算研究

应用密度泛函理论（DFT）反应能计算及最小能量路径分析研究了CO2在气相和电化学环境中于Cu(111)单晶表面的还原过程。气相中,CO2还原为碳氢化合物的反应路径可能为：CO2(g) + H* → COOH* → (CO +OH)* → CHO*;CHO + H* → CH2O* → (CH2 + O)*;CH2* + 2H* → CH4或2CH2* → C2H4。整个反应由CO2(g) + H* → COOH* → (CO +OH)*,(CO + H)* → CHO*和CH2O* → (CH2 + O)*等几个步骤联合控制。在-0.50V (vs RHE) 以正的电势下,CO2在Cu(111)表面电化学还原主要形成HCOO-和CO吸附物;随着电势逐渐负移,CO2加氢解离形成CO的反应越来越容易,CO成为主要产物;随电势进一步变负,形成碳氢化合物的趋势逐渐变强。与CO2的气相化学还原不同的是,电化学环境下CO质子化形成的CHO中间体倾向于解离形成CH,而在气相中CHO中间体则倾向于进一步质子化形成CH2O中间体。     

Reactive domains of energy hypersurfaces and the stability of minimum energy reaction paths

Special properties of the Riemannian metric for energy hypersurfaces, defined within the framework of the Born-Oppenheimer approximation, are utilized in devising a partitioning scheme for domains of nuclear coordinates. The chemically important coordinate domains are distinguished from domains of lesser importance by their curvature properties. Conditions are derived for the stability of minimum energy reaction paths, and the effects of instability regions are investigated. Instability domains along minimum energy paths may allow small vibrational perturbations to alter the outcome of the chemical reaction.     

Approximating disjoint-path problems using packing integer programs

In a packing integer program, we are given a matrix $A$ and column vectors $b,c$ with nonnegative entries. We seek a vector $x$ of nonnegative integers, which maximizes $c^{T}x,$ subject to $Ax \leq b.$ The edge and vertex-disjoint path problems together with their unsplittable flow generalization are NP-hard problems with a multitude of applications in areas such as routing, scheduling and bin packing. These two categories of problems are known to be conceptually related, but this connection has largely been ignored in terms of approximation algorithms. We explore the topic of approximating disjoint-path problems using polynomial-size packing integer programs. Motivated by the disjoint paths applications, we introduce the study of a class of packing integer programs, called column-restricted. We develop improved approximation algorithms for column-restricted programs, a result that we believe is of independent interest. Additional approximation algorithms for disjoint-paths are presented that are simple to implement and achieve good performance when the input has a special structure.Work partially supported by NSERC OG 227809-00 and a CFI New Opportunities Award. Part of this work was done while at the Department of Computer Science, Dartmouth College and partially by NSF Award CCR-9308701 and NSF Career Award CCR-9624828.This work was done while at the Department of Computer Science, Dartmouth College and partially supported by NSF Award CCR-9308701 and NSF Career Award CCR-9624828.     

LP formulations of the shortest path tree problem

Based on a pair of primal-dual LP formulations of the shortest path tree problem, the first algorithmic approach to reoptimizing the shortest paths subject to changes in the edge weights was proposed by S. Pallottino and M.G. Scutellá in 2003. We shall here focus solely on their introductory sections, propose some simplifications of the models considered, and finally relate the resulting models to the presentation of single-source shortest path problems in textbooks treating this subject with but limited or no reference to LP.Received: April 2004, Revised: August 2004, MSC classification: 90C05, 90C35, 90B10 Dedicated to the memory of Stefano Pallottino     

Disjoint Paths in Graphs III,Characterization

Let G be a graph, $ \{a, b, c\}\subseteq V(G) $, and $ \{a', b', c'\}\subseteq V(G) $ such that $ \{a, b, c\}\neq \{a', b', c'\} $. We say that $ (G, \{a, c\}, \{a', c'\}, (b, b')) $ is an obstruction if, for any three vertex disjoint paths from {a, b, c} to {a', b', c'} in G, one path is from b to b'. In this paper we characterize obstructions. As a consequence, we show that no obstruction can be 8-connected, unless b = b' or {a, c} = {a', c'}.AMS Subject Classification: 05C38.     

A branch-and-price algorithm for the Vehicle Routing Problem with Deliveries,Selective Pickups and Time Windows

In the Vehicle Routing Problem with Deliveries, Selective Pickups and Time Windows, the set of customers is the union of delivery customers and pickup customers. A fleet of identical capacitated vehicles based at the depot must perform all deliveries and profitable pickups while respecting time windows. The objective is to minimize routing costs, minus the revenue associated with the pickups. Five variants of the problem are considered according to the order imposed on deliveries and pickups. An exact branch-and-price algorithm is developed for the problem. Computational results are reported for instances containing up to 100 customers.