Efficient interval partitioning for constrained global optimization

A new efficient interval partitioning approach to solve constrained global optimization problems is proposed. This involves a new parallel subdivision direction selection method as well as an adaptive tree search. The latter explores nodes (intervals in variable domains) using a restricted hybrid depth-first and best-first branching strategy. This hybrid approach is also used for activating local search to identify feasible stationary points. The new tree search management technique results in improved performance across standard solution and computational indicators when compared to previously proposed techniques. On the other hand, the new parallel subdivision direction selection rule detects infeasible and suboptimal boxes earlier than existing rules, and this contributes to performance by enabling earlier reliable deletion of such subintervals from the search space.     

Constructive characterizations of （γp, γ）- and （γp, γpr）-trees

Let G =(V,E) be a graph without isolated vertices.A set S  V is a domination set of G if every vertex in V -S is adjacent to a vertex in S,that is N[S] = V .The domination number of G,denoted by γ(G),is the minimum cardinality of a domination set of G.A set S  V is a paired-domination set of G if S is a domination set of G and the induced subgraph G[S]has a perfect matching.The paired-domination number,denoted by γpr(G),is defined to be the minimum cardinality of a paired-domination set S in G.A subset S  V is a power domination set of G if all vertices of V can be observed recursively by the following rules:(i) all vertices in N[S] are observed initially,and(ii) if an observed vertex u has all neighbors observed except one neighbor v,then v is observed(by u).The power domination number,denoted by γp(G),is the minimum cardinality of a power domination set of G.In this paper,the constructive characterizations for trees with γp = γ and γpr = γp are provided respectively.     

The variance equity measure in locational decision theory

Classical location theories and models were initially developed for the private sector, so that the related operational research literature has emphasized performance measures of efficiency and effectiveness. For public sector applications, measures of equity become important, yet such measures have received little formal treatment. This paper suggests a locational equity measure, the variance measure, and investigates its properties for tree networks. A fast algorithm (O(M)) to locate the minimum variance point on a tree network is developed, and some numerical results illustrate the variance optimal location.This work is dedicated to the memory of Professor Jonathan Halpern     

Undirected simple connected graphs with minimum number of spanning trees

We show that for positive integers n, m with n(n−1)/2≥m≥n−1, the graph L_n,m having n vertices and m edges that consists of an (n−k)-clique and k−1 vertices of degree 1 has the fewest spanning trees among all connected graphs on n vertices and m edges. This proves Boesch’s conjecture [F.T. Boesch, A. Satyanarayana, C.L. Suffel, Least reliable networks and reliability domination, IEEE Trans. Commun. 38 (1990) 2004-2009].     

NUMERICAL ANALYSIS ON BINOMIAL TREE METHODS FOR AMERICAN LOOKBACK OPTIONS

1　IntroductionLookback options are path-dependent options whose payoffs depend on the maximumor the minimum of the underlying asset price during the life of the options( see[6] [1 0 ][1 4] ) .Here the maximum or minimum realized asset price may be monitored either con-tinuously or discretely.An American lookback call( put) option allows to be exercised atany time prior to expiry and gives the holder the rightto buy( sell) atthe historical mini-mum( maximum) of the underlying asset price on ex…     

Path Decomposition of Graphs with Given Path Length

A path decomposition of a graph G is a list of paths such that each edge appears in exactly onepath in the list.G is said to admit a {P_l}-decomposition if G can be decomposed into some copies of P_l,whereP_l is a path of length l-1.Similarly,G is said to admit a {P_l,P_k}=decomposition if G can be decomposed intosome copies of P_l or P_k.An k-cycle,denoted by C_k,is a cycle with k vertices.An odd tree is a tree of which allvertices have odd degree.In this paper,it is shown that a connected graph G admits a {P_3,P_4}-decompositionif and only if G is neither a 3-cycle nor an odd tree.This result includes the related result of Yan,Xu andMutu.Moreover,two polynomial algorithms are given to find {P_3}-decomposition and {P_3,P_4}-decompositionof graphs,respectively.Hence,{P_3}-decomposition problem and {P_3,P_4}-decomposition problem of graphs aresolved completely.     

HPLC in the investigation of taxonomic problems. Classification of poplar genotypes

Summary The RP-HPLC technique has been applied to the analysis of the flavonoid content of leaf extracts from various genotypes ofPopulus nigra andPopulus deltoides and from several of their hybrids. Two elution procedures different either as regards gradient program or the type of organic modifier used were checked to optimize the reliability of the results obtained. Before making any identification, the chromatographic profiles proved so typical of each species as to allow of their use as fingerprints in this type of taxonomic problem. Individual identifications were carried out by spiking real samples with known amounts of standard substances. The presence of flavonoid compounds previously identified was confirmed and a few new identifications were proposed.     

Cross-correlations in volume space: Differences between buy and sell volumes

We study the cross-correlations of buy and sell volumes on the Korean stock market in high frequency. We observe that the pulling effects of volumes are as small as that of returns. The properties of the correlations of buy and sell volumes differ. They are explained by the degree of synchronization of stock volumes. Further, the pulling effects on the minimal spanning tree are studied. In minimal spanning trees with directed links, the large pulling effects are clustered at the center, not uniformly distributed. The Epps effect of buy and sell volumes are observed. The reversal of the cross-correlations of buy and sell volumes is also detected.     

Risk models for the Prize Collecting Steiner Tree problems with interval data

Given a connected graph G=(V,E)with a nonnegative cost on each edge in E,a nonnegative prize at each vertex in V,and a target set V′V,the Prize Collecting Steiner Tree(PCST)problem is to find a tree T in G interconnecting all vertices of V′such that the total cost on edges in T minus the total prize at vertices in T is minimized.The PCST problem appears frequently in practice of operations research.While the problem is NP-hard in general,it is polynomial-time solvable when graphs G are restricted to series-parallel graphs.In this paper,we study the PCST problem with interval costs and prizes,where edge e could be included in T by paying cost xe∈[c e,c+e]while taking risk(c+e xe)/(c+e c e)of malfunction at e,and vertex v could be asked for giving a prize yv∈[p v,p+v]for its inclusion in T while taking risk(yv p v)/(p+v p v)of refusal by v.We establish two risk models for the PCST problem with interval data.Under given budget upper bound on constructing tree T,one model aims at minimizing the maximum risk over edges and vertices in T and the other aims at minimizing the sum of risks over edges and vertices in T.We propose strongly polynomial-time algorithms solving these problems on series-parallel graphs to optimality.Our study shows that the risk models proposed have advantages over the existing robust optimization model,which often yields NP-hard problems even if the original optimization problems are polynomial-time solvable.