对偶平行体与对偶Steiner点

结合平行体及径向加的定义,给出了星体的对偶平行体.研究了对偶平行体与平均弦长之间的关系,并得出了对偶平行类在某度量下的性质,此外,还证明了对偶Steiner点在对偶平行类上的连续性及赋值性质.     

线性不等式组的简单对偶非线性方法

将线性不等式组问题转化为一个形式简单的对偶空间非线性极值问题,本提出了一类新的求解线性不等式组的方法-简单对偶非线性方法,它在理论上是多项式算法,并可以从任意点启动,可以应用共轭梯度方法有效地求解大规模线性不等式组问题。本给出了不同的算法实现,数值实验结果表明,简单对偶非线性方法是有效的。     

系列平行图上带时间约束的Steiner最小树问题

对一类特殊系列平行图上带有时间约束的Steiner最小树问题,证明了其复杂性为NPC,并给出了一个完全多项式时间近似方案.     

Hermite插值多项式在不同基下的显式表示

本文利用对偶基的概念,导出了 Ｈｅｒｍ ｉｔｅ 插值多项式在不同基下的显式表示,这给人们对 Ｈｅｒｍ ｉｔ插值多项式在不同基下从一种表示转换到另一种表示带来极大的方便     

有限链环上的循环码及其Mattson-Solomn多项式

研究了有限链环上的循环码的结构及其Mattson-Solomn多项式,用循环码的Mattson-Solomn多项式和定义集刻画循环码及其对偶码的性质。     

两类花束图的部分对偶欧拉亏格多项式

[European J.Combin.,2020,86:Paper No.103084,20 pp.]在带子图中引入了部分对偶欧拉亏格多项式的概念,并给出插值猜想,即任意不可定向带子图的部分对偶欧拉亏格多项式是插值的.[European J.Combin.,2022,102:Paper No.103493,7 pp.]给出了两类反例否定了插值猜想,这两类花束图含有的侧面环只有一条或者两条不可定向环.本文是在[European J.Combin.,2022,102:Paper No.103493,7 pp.]的基础上,进一步计算其它两类花束图的部分对偶欧拉亏格多项式,其中一类是非插值的,它的侧面环有任意条不可定向环;而另一类是插值的,它的侧面环有任意条可定向环和不可定向环.     

对偶Brunn-Minkowski型不等式

本文研究了对偶Brunn-Minkowski不等式问题.利用对偶混合体和Blaschke径向和的性质,建立了对偶混合体均质积分的Brunn-Minkowski不等式的隔离形式,推广了对偶Brunn-Minkowski理论的几个不等式.     

Hermite插值多项式在不同基下的显式表示

本利用对偶基的概念,导出了Hermite插值多项式在不同基下的显式表示,这给人们对Hermit插值多项式在不同基下从一种表示转换到另一种表示带来极大的方便。     

凸体截面的稳定性

证明了如果两个凸体被过原点的任何一个超平面所截得到的截面具有相等的平均弦长和相同的对偶Steiner点,则这两个凸体是重合的,并且得到此定理的一个的稳定性版本.     

指数多项式不等式的自动证明北大核心CSCD

讨论了指数多项式不等式的自动证明问题,运用Taylor展开式将目标不等式的证明转化为一系列的一元多项式不等式的验证,然后借助代数不等式证明工具(如Bottema)完成最后的工作.运用Maple实现了上述算法,算法对所有指数多项式不等式终止,并且可以输出"可读"的证明过程.     

Facets of two Steiner arborescence polyhedra

The Steiner arborescence (or Steiner directed tree) problem concerns the connection of a set of target vertices of a digraph to a given root vertex. This problem is known to be NP-hard. In the present paper we study the facial structure of two polyhedra associated with the problem. Several classes of valid inequalities are considered, and a new class with arbitrarily large coefficients is introduced. All these inequalities are shown to define distinct facets of both the Steiner polyhedra considered. This is achieved by exploiting two lifting theorems which also allow generalization of the new inequalities. Composition theorems are finally given and used to derive large families of new facet-inducing inequalities with exponentially large coefficients.     

The Euclidean Steiner tree problem in Rn: A mathematical programming formulation

A nonconvex mixed-integer programming formulation for the Euclidean Steiner Tree Problem (ESTP) in Rⁿ is presented. After obtaining separability between integer and continuous variables in the objective function, a Lagrange dual program is proposed. To solve this dual problem (and obtaining a lower bound for ESTP) we use subgradient techniques. In order to evaluate a subgradient at each iteration we have to solve three optimization problems, two in polynomial time, and one is a special convex nondifferentiable programming problem. This revised version was published online in June 2006 with corrections to the Cover Date.     

The Steiner tree polytope and related polyhedra

We consider the vertex-weighted version of the undirected Steiner tree problem. In this problem, a cost is incurred both for the vertices and the edges present in the Steiner tree. We completely describe the associated polytope by linear inequalities when the underlying graph is series—parallel. For general graphs, this formulation can be interpreted as a (partial) extended formulation for the Steiner tree problem. By projecting this formulation, we obtain some very large classes of facet-defining valid inequalities for the Steiner tree polytope.Research supported by Air Force contract AFOSR-89-0271 and DARPA contract DARPA-89-5-1988.     

The Steiner tree problem II: Properties and classes of facets

This is the second part of two papers addressing the study of the facial structure of the Steiner tree polyhedron. In this paper we identify several classes of facet defining inequalities and relate them to special classes of graphs on which the Steiner tree problem is known to be NP-hard.Corresponding author.The author appreciates partial support from National Science Foundation Grants Nos. DSM-8606188 and ECS 8800281.     

On better heuristics for Steiner minimum trees

Finding a shortest network interconnecting a given set of points in a metric space is called the Steiner minimum tree problem. The Steiner ratio is the largest lower bound for the ratio between lengths of a Steiner minimum tree and a minimum spanning tree for the same set of points. In this paper, we show that in a metric space, if the Steiner ratio is less than one and finding a Steiner minimum tree for a set of size bounded by a fixed number can be performed in polynomial time, then there exists a polynomialtime heuristic for the Steiner minimum tree problem with performance ratio bigger than the Steiner ratio. It follows that in the Euclidean plane, there exists a polynomial-time heuristic for Steiner minimum trees with performance ratio bigger than . This solves a long-standing open problem.Part of this work was done while this author visited the Department of Computer Science, Princeton University, supported in part by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center, under NSF grant STC88-09648, supported in part by NSF grant No. CCR-8920505, and also supported in part by the National Natural Science Foundation of China.     

SOME INEQUALITIES ABOUT DUAL MIXED VOLUMES OF STAR BODIES

The authors establish some inequalities about the dual mixed volumes of star bodies in R^n. These inequalities are the analogue in the Brunn-Minkowski theory of the inequalities of Marcus-Lopes and Bergstrom about symmetric functions of positive reals.     

An efficient algorithm for the Steiner Tree Problem with revenue,bottleneck and hop objective functions

This paper considers a tricriteria Steiner Tree Problem arising in the design of telecommunication networks. The objective functions consist of maximizing the revenue and of minimizing the maximal distance between each pair of interconnected nodes, as well as the maximal number of arcs between the root and each node. A polynomial algorithm is developed for the generation of a minimal complete set of Pareto-optimal Steiner trees. Optimality proofs are given and computational experience on a set of randomly generated problems is reported.