A branch-and-bound method for the minimum k−enclosing ball problem

The minimum k-enclosing ball problem seeks the ball with smallest radius that contains at least k of m given points. This problem is NP-hard. We present a branch-and-bound algorithm on the tree of the subsets of k points to solve this problem. Our method is able to solve the problem exactly in a short amount of time for small and medium sized datasets.     

Local approximations for maximum partial subgraph problem

We deal with MAXH₀-FREE PARTIAL SUBGRAPH. We mainly prove that 3-locally optimum solutions achieve approximation ratio (δ₀+1)/(B+2+ν₀), where B=max_v∈Vd_G(v), δ₀=min_v∈V(H0)d_H0(v) and ν₀=(|V(H₀)|+1)/δ₀. Next, we show that this ratio rises up to 3/(B+1) when H₀=K₃. Finally, we provide hardness results for MAXK₃-FREE PARTIAL SUBGRAPH.     

A greedy algorithm for multicut and integral multiflow in rooted trees

We present an O(min(Kn,n²)) algorithm to solve the maximum integral multiflow and minimum multicut problems in rooted trees, where K is the number of commodities and n is the number of vertices. These problems are NP-hard in undirected trees but polynomial in directed trees. In the algorithm we propose, we first use a greedy procedure to build the multiflow then we use duality properties to obtain the multicut and prove the optimality.     

图中相互独立的4圈和含4个点的路

设k是一个正整数，G是一个顶点数为|G|=4k的图. 假设σ\-2(G)≥4k-1, 则G有一个支撑子图含k-1个4圈和一条顶点数为4的路，使得所有这些圈和路都是相互独立的. 设G=(V\-1,V \-2;E)是一个二分图使得|V\-1|=|V\-2|=2k. 如果对G中每一对满足x∈V\-1和y∈V\-2的不 相邻的顶点x和y 都有d(x)+d(y)≥2k+1, 则G包含k-1个相互独立的4圈和一条顶点数为4的路，使得所有这些圈和路都是相互独立的，并且此度条件是最好的.     

最小费用k度限制树对策

本在Glover—Klingman算法及最小费用支撑树对策的基础上，讨论了最小费用k度限制树对策问题．利用威胁、旁支付理论制订了两种规则，并利用优超、策略等价理论分别给出了在这两种规则下最小费用k度限制树对策核心中的解，从而证明了在这两种规则下其核心非空．     

The Two-Point Codes with the Designed Distance on a Hermitian Curve in Even Characteristic

In Homma M and Kim SJ [2], the authors considered two-point codes on a Hermitian curve defined over fields of odd characteristic. In this paper, we study the geometry of a Hermitian curve over fields of even characteristic and classify the two-point codes whose minimum distances agree with the designed ones.     

An Improved Extra-Gradient Method for Minimizing a Sum of p-norms—A Variational Inequality Approach

This paper presents a variational inequality (VI) approach to the problem of minimizing a sum of p-norms. First the original problem is reformulated as an equivalent linear VI. Then an improved extra-gradient method is presented to solve the linear VI. Applications to the problem of p-norm Steiner Minimum Trees (SMT) shows that the proposed method is effective. Comparison with the general extra-gradient method is also provided to show the improvements of the new method.     

Quadratically constrained minimum cross-entropy analysis

Quadratically constrained minimum cross-entropy problem has recently been studied by Zhang and Brockett through an elaborately constructed dual. In this paper, we take a geometric programming approach to analyze this problem. Unlike Zhang and Brockett, we separate the probability constraint from general quadratic constraints and use two simple geometric inequalities to derive its dual problem. Furthermore, by using the dual perturbation method, we directly prove the strong duality theorem and derive a dual-to-primal conversion formula. As a by-product, the perturbation proof gives us insights to develop a computation procedure that avoids dual non-differentiability and allows us to use a general purpose optimizer to find an-optimal solution for the quadratically constrained minimum cross-entropy analysis.     

Mixing of electronic states in molybdenum complexes involved in nitrogen activation

The mechanism for nitrogen activation by molybdenum complexes is a complicated one, involving as it does the coupling of a quartet molybdenum reactant with a singlet nitrogen molecule, passing via a series of quartet and doublet encounter complexes to a triplet intermediate, with the subsequent spin crossing to the singlet surface which then leads via a singlet transition state to the final pair of singlet products. We have investigated in detail a variety of levels of theory to describe the crossing of these electronic surfaces and have calculated both lower-bound and actual minimum energy crossing points for the key spin inversion processes.     

Computed Potential Energy Surfaces and Minimum Energy Pathways for Chemical Reactions

Computed potential energy surfaces are often required for computation of such observables as rate constants as a function of temperature, product branching ratios, and other detailed properties. We have found that computation of the stationary points/reaction pathways using CASSCF/derivative methods, followed by use of the internally contracted CI method with the Dunning correlation consistent basis sets to obtain accurate energetics, gives useful results for a number of chemically important systems. Applications to complex reactions leading to NO_x and soot formation in hydrocarbon combustion are discussed.