The Steiner Ratio Gilbert–Pollak Conjecture Is Still Open

The aim of this note is to clear some background information and references to readers interested in understanding the current status of the Gilbert–Pollak Conjecture, in particular, to show that A.O. Ivanov and A.A. Tuzhilin were the first who understood the nature of the real gaps in Du–Hwang proof, what has reflected in their publications starting from 2002.     

A proof of the Gilbert-Pollak conjecture on the Steiner ratio

LetP be a set ofn points on the euclidean plane. LetL _s(P) andL _m (P) denote the lengths of the Steiner minimum tree and the minimum spanning tree onP, respectively. In 1968, Gilbert and Pollak conjectured that for anyP,L _s (P)≥(√3/2)L _m (P). We provide a proof for their conjecture in this paper.     

A proof of the Gilbert-Pollak conjecture on the Steiner ratio

LetP be a set ofn points on the euclidean plane. LetL _s(P) andL _m (P) denote the lengths of the Steiner minimum tree and the minimum spanning tree onP, respectively. In 1968, Gilbert and Pollak conjectured that for anyP,L _s (P)(3/2)L _m (P). We provide a proof for their conjecture in this paper.supported by NSF under grant STC88-09648.supported in part by the National Natural Science Foundation of China.     

The Turing Machine May Not Be the Universal Machine

Minds and Machines -     

The General Steiner Tree-Star problem

The Steiner tree problem is defined as follows—given a graph G=(V,E) and a subset X⊂V of terminals, compute a minimum cost tree that includes all nodes in X. Furthermore, it is reasonable to assume that the edge costs form a metric. This problem is NP-hard and has been the study of many heuristics and algorithms. We study a generalization of this problem, where there is a “switch” cost in addition to the cost of the edges. Switches are placed at internal nodes of the tree (essentially, we may assume that all non-leaf nodes of the Steiner tree have a switch). The cost for placing a switch may vary from node to node. A restricted version of this problem, where the terminal set X cannot be connected to each other directly but only via the Steiner nodes V?X, is referred to as the Steiner Tree-Star problem. The General Steiner Tree-Star problem does not require the terminal set and Steiner node set to be disjoint. This generalized problem can be reduced to the node weighted Steiner tree problem, for which algorithms with performance guarantees of Θ(lnn) are known. However, such approach does not make use of the fact that the edge costs form a metric. In this paper we derive approximation algorithms with small constant factors for this problem. We show two different polynomial time algorithms with approximation factors of 5.16 and 5.     

Fuzzy Static Output Feedback May Be Possible in LMI Framework

Takagi-Sugeno (T--S) fuzzy-model-based static output-feedback controller design is a challenging issue due to the nonconvexity in the Lyapunov stability condition. Recently, a convexified linear matrix inequality (LMI) condition was proposed for the problem by additionally importing as many equality constraints as the number of the fuzzy rules with a variable in the paper from the study of Fang et al. However, numerical experiences seem to imply the infeasibility of the proposed LMI. This letter shows that their LMI problem may be feasible.     

The Resolution of Keller’s Conjecture

Journal of Automated Reasoning - We consider three graphs, $$G_{7,3}$$ , $$G_{7,4}$$ , and $$G_{7,6}$$ , related to Keller’s conjecture in dimension 7. The conjecture is false for this...     

开放型模块化高性价比ATS的自主研发

结合VXI／PXI／LXI、多DSP并行处理、FPGA和ISP（In System Programming）、高速缓存、VI（Virtual Instrument）等先进技术,按照测量、控制、通信、计算机（MC^3）一体化系统的思路,针对频带宽、动态范围大、瞬时性强、信号种类繁多等综合参数动态测试应用背景,探讨了开放型模块化高性价比自动测试系统ATS（Automatic Testing System）的研制与开发。     

On the location of Steiner points in uniformly-oriented Steiner trees

We give a fundamental result on the location of Steiner points for Steiner minimum trees in uniform orientation metrics. As a corollary we obtain a linear time algorithm for constructing a Steiner minimum tree for a given full topology when the number of uniform orientations is λ=3m,m?1.     

哥德巴赫猜想的计算机验证

本文介绍的是如何以程序的方式,使计算机自动验证哥德巴赫猜想,其中简要介绍了此程序的 基本思路及其简单的计算机实现方法和程序的特点     

The Log-Rank Conjecture and low degree polynomials

We formulate several questions concerning the intersections of sets of Boolean roots of low degree polynomials. Two of these questions we show to be equivalent to the Log-Rank Conjecture from communication complexity. We further exhibit a slightly stronger formulation which we prove to be false, and a weaker formulation which we prove to be true. These results suggest a possible new approach to the Log-Rank Conjecture.     

冰雹猜想的计算机编程证明

冰雹猜想是一个风靡全球的趣味数学游戏。迄今为止,人们还未能得到这个猜想在数学上的严格证明。可以利用计算机强大的计算能力,根据冰雹猜想的计算规律,编写程序让计算机来证明冰雹猜想的正确性。程序的设计思想是先证明任意一个数的正确性,再证明某个数据区间内所有数据的正确性,通过程序的运行,对一定范围内的所有自然数进行验证,从而证明了冰雹猜想。     

关于四色问题两个重要反例的研究

该文用Tait方法证明了Heawood反例是四色的;用Kempe链方法证明了Tutte反例也是四色的。发现了3-正则平面图的二级Hamilton圈生成机制。为四色问题的非计算机证明找到了一个新的途径。     

The Steiner Problem in Graphs: Topological Methods of Solution

Algorithms for the Steiner problem and its generalizations on large graphs with a relatively small number of terminal vertices are designed by a two-level solution scheme: a network topology (i.e., a tree determining the adjacency of terminal vertices and branching points) is determined in the upper level and the optimal location for branching points with the topology found in the upper level is determined in the lower level.     

Steiner Tree问题的研究进展

Steiner树问题是经典的NP难解问题,在计算机网络布局、电路设计以及生物网络等领域都有很多应用。随着参数计算理论的发展,已经证明了无向图和有向图中的Steiner树问题都是固定参数可解的(FPT)。介绍了无向图和有向图中Steiner树问题的近似算法和参数算法,分析了一些特殊Steiner树问题的研究现状,还讨论了顶点加权Steiner树问题的研究进展。最后,提出了该问题的进一步研究方向。     

静态图像提取文字技术

从图像中提取文字属于信息智能化处理的前沿课题,是当前人工智能与模式识别领域中的研究热点.由于文字具有高级语义特征,对图片内容的理解、索引、检索具有重要作用,因此,研究图片文字提取具有重要的实际意义.又由于静态图像文字提取是动态图像文字提取的基础,故着重介绍了静态图像文字提取技术,总结了几种已提出的算法,并利用计算机语言学方法对提取出的文字进行后期处理,大大提高了文字提取的正确率.     

静态图像提取文字技术

从图像中提取文字属于信息智能化处理的前沿课题,是当前人工智能与模式识别领域中的研究热点。由于文字具有高级语义特征,对图片内容的理解、索引、检索具有重要作用,因此,研究图片文字提取具有重要的实际意义。又由于静态图像文字提取是动态图像文字提取的基础,故着重介绍了静态图像文字提取技术,总结了几种已提出的算法,并利用计算机语言学方法对提取出的文字进行后期处理,大大提高了文字提取的正确率。     

静态图像提取文字技术

从图像中提取文字属于信息智能化处理的前沿课题,是当前人工智能与模式识别领域中的研究热点。由于文字具有高级语义特征,对图片内容的理解、索引、检索具有重要作用,因此,研究图片文字提取具有重要的实际意义。又由于静态图像文字提取是动态图像文字提取的基础,故着重介绍了静态图像文字提取技术,总结了几种已提出的算法,并利用计算机语言学方法对提取出的文字进行后期处理,大大提高了文字提取的正确率。     

On a Conjecture of Peter Borwein

We consider several conjectures by Peter Borwein concerning products of the form

Full-size image

.