Finding a Noncrossing Steiner Forest in Plane Graphs Under a 2-Face Condition

Let G = (V,E) be a plane graph with nonnegative edge weights, and let be a family of k vertex sets , called nets. Then a noncrossing Steiner forest for in G is a set of k trees in G such that each tree connects all vertices, called terminals, in net N _i, any two trees in do not cross each other, and the sum of edge weights of all trees is minimum. In this paper we give an algorithm to find a noncrossing Steiner forest in a plane graph G for the case where all terminals in nets lie on any two of the face boundaries of G. The algorithm takes time if G has n vertices and each net contains a bounded number of terminals.     

The approximation of an unbiased test with a small level for the bioequivalence problem

In the bioequivalence problem. Brown. Hwang and Munk (1997) constructed an unbiased level a test and other tests which are uniformly more powerful than the two one-sided tests procedures when a iscomparatively larger. In this paper, for a small level, an unbiased test is shown to be approxirnately constructeQ lor tnis prooiem oy using tneir Metnog. ine numerical construction is also given.     

移动商务中面向客户细分的KSP混合聚类算法

数据挖掘技术中的聚类算法是解决客户细分问题的重要算法之一。为解决传统聚类算法在客户细分问题中分类精度较低、收敛速度较慢的问题,着重对比分析传统聚类算法中K-m eans、自组织映射网络和粒子群3种算法的不足,提出融合3种算法优点的混合型聚类算法,该算法利用K-m eans和自组织映射网络对初始聚类中心进行优化,结合粒子群优化和K-m eans优化聚类迭代过程,并在迭代优化过程中设计避免算法因早熟而停滞的机制。针对移动电子商务环境下的餐饮业客户细分问题,建立移动餐饮业客户细分模型,并利用混合型聚类算法、K-m eans、层级自组织映射网络和基于粒子群的K-m eans等4种算法对实际案例进行对比分析。研究结果表明,混合型聚类算法的聚类精度分别比其他3种算法高,同时还具有最快的收敛性能,更适用于客户细分问题。     

Average-case competitive analyses for one-way trading

Consider a trader who exchanges one dollar into yen and assume that the exchange rate fluctuates within the interval [m,M]. The game ends without advance notice, then the trader is forced to exchange all the remaining dollars at the minimum rate m. El-Yaniv et al. presented the optimal worst-case threat-based strategy for this game (El-Yaniv et al. 2001). In this paper, under the assumption that the distribution of the maximum exchange rate is known, we provide average-case analyses using all the reasonable optimization measures and derive different optimal strategies for each of them. Remarkable differences in behavior are as follows: Unlike other strategies, the average-case threat-based strategy that minimizes E[OPT/ALG] exchanges little by little. The maximization of E[ALG/OPT] and the minimization of E[OPT]/E[ALG] lead to similar strategies in that both exchange all at once. However, their timing is different. We also prove minimax theorems with respect to each objective function.     

Synchronic and diachronic variation in the use of spatial frames of reference: An analysis of Japanese route instruction

By focusing on everyday use of spatial ‘frames of reference’ (FOR) in route instruction, we propose some possible explanations for the seemingly contradictory trends observed in FOR‐based and deixis‐based spatial expressions in Japanese. We examined the data obtained in a series of longitudinal surveys conducted in Japan over 50 years (1953, 1972 and 2008). Our GoldVarb analysis confirmed what is called a ‘retrograde’ lifespan change. This indicates that, first, synchronically, the preference for External FOR (that is, based on North‐South‐East‐West) increases as community members grow older. This means they shift toward the local norm through ‘age‐grading’. Secondly, diachronically, the preference for Internal FOR (based on Right‐Left‐Front‐Back) has gradually increased over the past century. There is, therefore, a ‘generational change’ motivated by the linguistic marketplace. In contrast, as a community‐wide preference for Internal FOR expressions prevails, there is an accompanying gradual decrease in the use of deictic expressions such as ‘here/there/over there’. This indicates a partially complementary relationship between deixis and Internal FOR.