In this article, we propose a parameter vertex method to determine the upper and lower bounds of the dynamic response of structures with interval parameters, which can be regarded as an extension of the matrix vertex ...In this article, we propose a parameter vertex method to determine the upper and lower bounds of the dynamic response of structures with interval parameters, which can be regarded as an extension of the matrix vertex method proposed by Qiu and Wang. The matrix vertex method requires considerable computation time and encounters the dependency problem in practice,thereby limiting its application in engineering. The proposed parameter vertex method can avoid the dependency problem, and the number of possible vertex combinations in the proposed method is significantly less than that in the matrix vertex method.The parameter vertex method requires that each matrix element in the dynamic differential equation is monotonic with respect to the uncertain parameter, and that the dynamic response reaches its extreme value when the uncertain parameter is at its endpoint.To further reduce the runtime, both vertical and transversal parallel algorithms are introduced and integrated into the parameter vertex method to improve its computational efficiency. Two numerical examples are presented to demonstrate the proposed method combined with both parallel algorithms. The performances of the two parallel algorithms are thoroughly studied. The parameter vertex method combined with parallel algorithm can be used for large-scale computing.展开更多
The aim of this paper is to evaluate the effects of uncertain-but-bounded parameters on the dynamic response of structures. By combining the interval mathematics and the finite element analysis, the mass matrix, dampi...The aim of this paper is to evaluate the effects of uncertain-but-bounded parameters on the dynamic response of structures. By combining the interval mathematics and the finite element analysis, the mass matrix, damping matrix, stiffness matrix and the external loads are represented as interval matrices and vector. With the help of the optimization theory, we present the vertex solution theorem for determining both the exact upper bounds or maximum values and the exact lower bounds or minimum values of the dynamic response of structures, in which these parameters reach their extreme values on the boundary of the interval mass, damping, stiffness matrices and the interval extemal loads vector. Three examples are used to illustrate the computational aspects of the presented vertex solution theorem.展开更多
二分图受约束最小点覆盖问题作为一个NP-完全问题,无法在多项式时间内得到最优解,除非P=NP。基于此,本文提出了一种基于链暗示技术的二分图受约束最小点覆盖问题的近似算法,具体为:当二分图受约束最小点覆盖问题实例中存在满足约束条件...二分图受约束最小点覆盖问题作为一个NP-完全问题,无法在多项式时间内得到最优解,除非P=NP。基于此,本文提出了一种基于链暗示技术的二分图受约束最小点覆盖问题的近似算法,具体为:当二分图受约束最小点覆盖问题实例中存在满足约束条件的最小点覆盖(ku,kl)时,对任意给定的近似率δ=1+ε>1,一定可以找到一个受约束近似点覆盖(ku,kl),对应的近似率为max{ku/ku,kl/kl}≤1+ε,整个近似算法的运行时间复杂度为O(22/ε)。显然,它是二分图受约束最小点覆盖问题的一个多项式时间近似方案(polynomial time approximation scheme,PTAS算法)。展开更多
This paper deals with the FEEDBACK VERTEX SET problem on undirected graphs, which asks for the existence of a vertex set of bounded size that intersects all cycles. Due it is theoretical and practical importance,the p...This paper deals with the FEEDBACK VERTEX SET problem on undirected graphs, which asks for the existence of a vertex set of bounded size that intersects all cycles. Due it is theoretical and practical importance,the problem has been the subject of intensive study. Motivated by the parameter ecology program we attempt to classify the parameterized and kernelization complexity of FEEDBACK VERTEX SET for a wide range of parameters.We survey known results and present several new complexity classifications. For example, we prove that FEEDBACK VERTEX SET is fixed-parameter tractable parameterized by the vertex-deletion distance to a chordal graph. We also prove that the problem admits a polynomial kernel when parameterized by the vertex-deletion distance to a pseudo forest, a graph in which every connected component has at most one cycle. In contrast, we prove that a slightly smaller parameterization does not allow for a polynomial kernel unless NP coNP=poly and the polynomial-time hierarchy collapses.展开更多
基金supported by the Defense Industrial Technology Development Program(Grant Nos.2016YFB0200700,JCKY2016601B001,and JCKY2016204B101)the Program of Introducing Talents of Discipline to Universities of China(111 Project)(Grant No.B07009)National Nature Science Foundation of China(Grant Nos.11372025,11432002,and11572024)
文摘In this article, we propose a parameter vertex method to determine the upper and lower bounds of the dynamic response of structures with interval parameters, which can be regarded as an extension of the matrix vertex method proposed by Qiu and Wang. The matrix vertex method requires considerable computation time and encounters the dependency problem in practice,thereby limiting its application in engineering. The proposed parameter vertex method can avoid the dependency problem, and the number of possible vertex combinations in the proposed method is significantly less than that in the matrix vertex method.The parameter vertex method requires that each matrix element in the dynamic differential equation is monotonic with respect to the uncertain parameter, and that the dynamic response reaches its extreme value when the uncertain parameter is at its endpoint.To further reduce the runtime, both vertical and transversal parallel algorithms are introduced and integrated into the parameter vertex method to improve its computational efficiency. Two numerical examples are presented to demonstrate the proposed method combined with both parallel algorithms. The performances of the two parallel algorithms are thoroughly studied. The parameter vertex method combined with parallel algorithm can be used for large-scale computing.
基金the National Outstanding Youth Science Foundation of China (10425208)111 Project (B07009) FanZhou Science and Research Foundation for Young Scholars (No. 20080503)
文摘The aim of this paper is to evaluate the effects of uncertain-but-bounded parameters on the dynamic response of structures. By combining the interval mathematics and the finite element analysis, the mass matrix, damping matrix, stiffness matrix and the external loads are represented as interval matrices and vector. With the help of the optimization theory, we present the vertex solution theorem for determining both the exact upper bounds or maximum values and the exact lower bounds or minimum values of the dynamic response of structures, in which these parameters reach their extreme values on the boundary of the interval mass, damping, stiffness matrices and the interval extemal loads vector. Three examples are used to illustrate the computational aspects of the presented vertex solution theorem.
文摘二分图受约束最小点覆盖问题作为一个NP-完全问题,无法在多项式时间内得到最优解,除非P=NP。基于此,本文提出了一种基于链暗示技术的二分图受约束最小点覆盖问题的近似算法,具体为:当二分图受约束最小点覆盖问题实例中存在满足约束条件的最小点覆盖(ku,kl)时,对任意给定的近似率δ=1+ε>1,一定可以找到一个受约束近似点覆盖(ku,kl),对应的近似率为max{ku/ku,kl/kl}≤1+ε,整个近似算法的运行时间复杂度为O(22/ε)。显然,它是二分图受约束最小点覆盖问题的一个多项式时间近似方案(polynomial time approximation scheme,PTAS算法)。
基金supported by the European Research Council through Starting Grant 306992 "Parameterized Approximation"
文摘This paper deals with the FEEDBACK VERTEX SET problem on undirected graphs, which asks for the existence of a vertex set of bounded size that intersects all cycles. Due it is theoretical and practical importance,the problem has been the subject of intensive study. Motivated by the parameter ecology program we attempt to classify the parameterized and kernelization complexity of FEEDBACK VERTEX SET for a wide range of parameters.We survey known results and present several new complexity classifications. For example, we prove that FEEDBACK VERTEX SET is fixed-parameter tractable parameterized by the vertex-deletion distance to a chordal graph. We also prove that the problem admits a polynomial kernel when parameterized by the vertex-deletion distance to a pseudo forest, a graph in which every connected component has at most one cycle. In contrast, we prove that a slightly smaller parameterization does not allow for a polynomial kernel unless NP coNP=poly and the polynomial-time hierarchy collapses.
