A generic lazy evaluation scheme for exact geometric computations

We present a generic C++ design to perform exact geometric computations efficiently using lazy evaluations. Exact geometric computations are critical for the robustness of geometric algorithms. Their efficiency is also important for many applications, hence the need for delaying the costly exact computations at run time until they are actually needed, if at all. Our approach is generic and extensible in the sense that it is possible to make it a library that users can apply to their own geometric objects and primitives. It involves techniques such as generic functor-adaptors, static and dynamic polymorphism, reference counting for the management of directed acyclic graphs, and exception handling for triggering exact computations when needed. It also relies on multi-precision arithmetic as well as interval arithmetic. We apply our approach to the whole geometry kernel of Cgal.     

Dominating set is fixed parameter tractable in claw-free graphs

We show that the Dominating Set problem parameterized by solution size is fixed-parameter tractable (FPT) in graphs that do not contain the claw (K_1,3, the complete bipartite graph on four vertices where the two parts have one and three vertices, respectively) as an induced subgraph. We present an algorithm that uses 2^O(k2)n^O(1) time and polynomial space to decide whether a claw-free graph on n vertices has a dominating set of size at most k. Note that this parameterization of Dominating Set is W[2]-hard on the set of all graphs, and thus is unlikely to have an FPT algorithm for graphs in general.The most general class of graphs for which an FPT algorithm was previously known for this parameterization of Dominating Set is the class of K_i,j-free graphs, which exclude, for some fixed i,j∈N, the complete bipartite graph K_i,j as a subgraph. For i,j≥2, the class of claw-free graphs and any class of K_i,j-free graphs are not comparable with respect to set inclusion. We thus extend the range of graphs over which this parameterization of Dominating Set is known to be fixed-parameter tractable.We also show that, in some sense, it is the presence of the claw that makes this parameterization of the Dominating Set problem hard. More precisely, we show that for any t≥4, the Dominating Set problem parameterized by the solution size is W[2]-hard in graphs that exclude the t-claw K_1,t as an induced subgraph. Our arguments also imply that the related Connected Dominating Set and Dominating Clique problems are W[2]-hard in these graph classes.Finally, we show that for any t∈N, the Clique problem parameterized by solution size, which is W[1]-hard on general graphs, is FPT in t-claw-free graphs. Our results add to the small and growing collection of FPT results for graph classes defined by excluded subgraphs, rather than by excluded minors.     

Component-based construction of bio-pathway models: The parameter estimation problem

Constructing and analyzing large biological pathway models is a significant challenge. We propose a general approach that exploits the structure of a pathway to identify pathway components, constructs the component models, and finally assembles the component models into a global pathway model. Specifically, we apply this approach to pathway parameter estimation, a main step in pathway model construction. A large biological pathway often involves many unknown parameters and the resulting high-dimensional search space poses a major computational difficulty. By exploiting the structure of a pathway and the distribution of available experimental data over the pathway, we decompose a pathway into components and perform parameter estimation for each component. However, some parameters may belong to multiple components. Independent parameter estimates from different components may be in conflict for such parameters. To reconcile these conflicts, we represent each component as a factor graph, a standard probabilistic graphical model. We then combine the resulting factor graphs and use a probabilistic inference technique called belief propagation to obtain the maximally likely parameter values that are globally consistent. We validate our approach on a synthetic pathway model based on the Akt-MAPK signaling pathways. The results indicate that the approach can potentially scale up to large pathway models.     

基于区间二型模糊集合的语言动力系统稳定性

运用区间二型模糊集合(Interval type-2 fuzzy sets, IT2 FSs) 的扩展原理将常规的数值函数转化为对应的区间二型模糊函数, 并给出了相应的词计算(Computing with words, CW)方法与算法,最后分析了严格单调情况下基于区间二型模糊集合的单输入单输出系统的语言动力系统(Linguistic dynamic systems, LDS)稳定性.     

Induced and uncertain heavy OWA operators

In this paper, we analyse in detail the ordered weighted averaging (OWA) operator and some of the extensions developed about it. We specially focus on the heavy aggregation operators. We suggest some new extensions about the OWA operator such as the induced heavy OWA (IHOWA) operator, the uncertain heavy OWA (UHOWA) operator and the uncertain induced heavy OWA (UIHOWA) operator. For these three new extensions, we consider some of their main properties and a wide range of special cases found in the weighting vector such as the heavy weighted average (HWA) and the uncertain heavy weighted average (UHWA). We further generalize these models by using generalized and quasi-arithmetic means obtaining the generalized heavy weighted average (GHWA), the induced generalized HOWA (IGHOWA) and the uncertain IGHOWA (UIGHOWA) operator. Finally, we develop an application of the new approach in a decision-making problem.     

基于发展趋势和认知程度的区间灰数预测

以GM(1,1)模型为代表的灰色预测模型实际上是对白数的建模和预测,而不是对区间灰数的建模和预测.发展趋势和认知程度两个维度可以很好地描述区间灰数序列,对此,可先将区间灰数序列转化成相应的发展趋势序列和认知程度,然后对区间灰数序列进行预测.这样,既避免了区间灰数预测过程中的灰数运算问题,又充分利用了区间灰数序列自身所包含的信息.通过具体实例验证了所建模型的有效性.     

A family of high-order multistep methods with vanished phase-lag and its derivatives for the numerical solution of the Schrödinger equation

Many simulation algorithms (chemical reaction systems, differential systems arising from the modelling of transient behaviour in the process industries etc.) contain the numerical solution of systems of differential equations. For the efficient solution of the above mentioned problems, linear multistep methods or Runge-Kutta single-step methods are used. For the simulation of chemical procedures the radial Schrödinger equation is used frequently. In the present paper we will study a class of linear multistep methods. More specifically, the purpose of this paper is to develop an efficient algorithm for the approximate solution of the radial Schrödinger equation and related problems. This algorithm belongs in the category of the multistep methods. In order to produce an efficient multistep method the phase-lag property and its derivatives are used. Hence the main result of this paper is the development of an efficient multistep method for the numerical solution of systems of ordinary differential equations with oscillating or periodical solutions. The reason of their efficiency, as the analysis proved, is that the phase-lag and its derivatives are eliminated. Another reason of the efficiency of the new obtained methods is that they have high algebraic order     

A graph theoretic-based heuristic algorithm for responsive supply chain network design with direct and indirect shipment

The configuration of the supply chain network has a strong influence on the overall performance of the supply chain. A well designed supply chain network provides a proper platform for efficient and effective supply chain management. The supply chain network should be designed in the way that could meet the customer needs with an efficient cost. This paper studies the responsive, multi-stage supply chain network design (SCND) problem under two conditions: (1) when direct shipment is allowed and (2) when direct shipment is prohibited. First, two mixed integer programming models are proposed for multi-stage, responsive SCND problem under two abovementioned conditions. Then, to escape from the complexity of mixed integer mathematical programming models, graph theoretic approach is used to study the structure of the SCND problems and it is proven that both of SCND problems considered in this paper could be modeled by a bipartite graph. Finally, since such network design problems belong to the class of NP-hard problems, a novel heuristic solution method is developed based on a new solution representation method derived from graph theoretic view to the structure of the studied problem. To assess the performance of the proposed heuristic solution method, the associated results are compared to the exact solutions obtained by a commercial.     

直觉模糊多属性决策方法综述

直觉模糊多属性决策是当前决策领域的一个研究热点,在实际决策中有着广泛的应用.按照直觉模糊集的发展形式:直觉模糊集、区间直觉模糊集、直觉三角模糊数和直觉梯形模糊数,分别介绍它们在多属性决策与群决策中的研究现状,并对其未来的发展方向进行了探讨与展望.