Жақын желілердегі қосымша төбелер туралы

Кіріспе

Қысқа байланыс желілерінде қосымша төбелер туралы

Комбинаторлық математикада Штайнер ағашы мәселесі немесе Якоб Штайнер есімімен аталған ең төменгі Штайнер ағашы мәселесі – комбинаторлық оптимизациядағы проблемалар класын білдіретін жалпы термин. Штайнер ағашы мәселелері әртүрлі жағдайларда қойылса да, олардың барлығы белгілі бір объектілер жиыны үшін және алдын ала анықталған мақсатты функция үшін оңтайлы байланысты талап етеді. Штайнер ағашы мәселесі терминімен жиі синоним ретінде қолданылатын белгілі бір түрі – графтардағы Штайнер ағашы мәселесі. Берілген бағытталмаған графта, оның қабырғаларының салмағы теріс емес және төбелердің ішкі жиыны (әдетте терминалдар деп аталады), графтардағы Штайнер ағашы мәселесі барлық терминалдарды қамтитын (бірақ қосымша төбелерді де қамтуы мүмкін) ең төменгі салмақты ағашты және оның қабырғаларының жалпы салмағын азайтуды талап етеді. Тағы бір танымал түрлері – Эвклидтік Штайнер ағашы мәселесі және тікбұрышты ең төменгі Штайнер ағашы мәселесі. Графтардағы Штайнер ағашы мәселесін басқа екі белгілі комбинаторлық оптимизация мәселесінің жалпылауы ретінде қарастыруға болады: (теріс емес) ең қысқа жол мәселесі және ең төменгі жайылмалы ағаш мәселесі. Егер графтардағы Штайнер ағашы мәселесінде дәл екі терминал болса, онда ол ең қысқа жолды табуға дейін тоғысып қалады. Ал егер барлық төбелер терминалдар болса, онда графтардағы Штайнер ағашы мәселесі ең төменгі жайылмалы ағашқа тең болады. Дегенмен, теріс емес ең қысқа жол және ең төменгі жайылмалы ағаш мәселелері полиномиалдық уақытта шешілсе, Штайнер ағашы мәселесі үшін мұндай шешім белгісіз. Оның шешімдік түрі, яғни берілген кірісте белгілі бір шектен төмен салмақты ағаш бар ма жоқ па деген сұрақ, NP-толық, бұл оптимизациялық түрі, яғни берілген графтағы ең төменгі салмақты ағашты табу, NP-қиын екенін білдіреді. Шындығында, шешімдік түрі Карптың бастапқы 21 NP-толық мәселесінің бірі болды. Графтардағы Штайнер ағашы мәселесі схемалық орналасуда немесе желілік дизайнда қолданылады. Алайда, практикалық қолданыстар көбінесе өзгерістерді қажет етеді, бұл Штайнер ағашы мәселесінің көптеген түрлеріне әкеледі. Штайнер ағашы мәселесінің көптеген түрлері NP-қиын, бірақ кейбір шектеулі жағдайларды полиномиалдық уақытта шешуге болады. Ең нашар жағдайдағы күрделілігіне қарамастан, бірнеше Штайнер ағашы мәселесінің түрлері, соның ішінде графтардағы Штайнер ағашы мәселесі және тікбұрышты Штайнер ағашы мәселесі, тіпті ірі масштабты нақты әлемдік мәселелер үшін де практикада тиімді шешіледі.

In combinatorial mathematics, the Steiner tree problem, or minimum Steiner tree problem, named after Jakob Steiner, is an umbrella term for a class of problems in combinatorial optimization. While Steiner tree problems may be formulated in a number of settings, they all require an optimal interconnect for a given set of objects and a predefined objective function. One well known variant, which is often used synonymously with the term Steiner tree problem, is the Steiner tree problem in graphs. Given an undirected graph with non negative edge weights and a subset of vertices, usually referred to as terminals, the Steiner tree problem in graphs requires a tree of minimum weight that contains all terminals (but may include additional vertices) and minimizes the total weight of its edges. Further well known variants are the Euclidean Steiner tree problem and the rectilinear minimum Steiner tree problem. The Steiner tree problem in graphs can be seen as a generalization of two other famous combinatorial optimization problems: the (non negative) shortest path problem and the minimum spanning tree problem. If a Steiner tree problem in graphs contains exactly two terminals, it reduces to finding the shortest path. If, on the other hand, all vertices are terminals, the Steiner tree problem in graphs is equivalent to the minimum spanning tree. However, while both the non negative shortest path and the minimum spanning tree problem are solvable in polynomial time, no such solution is known for the Steiner tree problem. Its decision variant, asking whether a given input has a tree of weight less than some given threshold, is NP complete, which implies that the optimization variant, asking for the minimum weight tree in a given graph, is NP hard. In fact, the decision variant was among Karp's original 21 NP complete problems. The Steiner tree problem in graphs has applications in circuit layout or network design. However, practical applications usually require variations, giving rise to a multitude of Steiner tree problem variants. Most versions of the Steiner tree problem are NP hard, but some restricted cases can be solved in polynomial time. Despite the pessimistic worst case complexity, several Steiner tree problem variants, including the Steiner tree problem in graphs and the rectilinear Steiner tree problem, can be solved efficiently in practice, even for large scale real world problems.

Евклидтік Штайнер ағашы

Бастапқы мәселе Евклидтік Штайнер ағашы проблемасы немесе геометриялық Штайнер ағашы проблемасы ретінде белгілі болған түрінде қойылды: Жазықтықта N нүкте берілген болса, мақсаты – оларды ең аз жалпы ұзындығы бар сызықтармен байланыстыру, осылайша кез келген екі нүкте тікелей немесе басқа нүктелер мен сызық сегменттері арқылы бір-бірімен байланыса алатындай ету. Бұл мәселені алғаш рет 1811 жылы Жозеф Диз Гергонн былай формулировкалады: «Жазықтықта белгілі орындарда орналасқан бірнеше қалалар бар; мәселе – оларды жалпы ұзындығы ең аз болатын каналдар жүйесімен байланыстыру». Байланыстыратын сызық сегменттері тек соңғы нүктелерде ғана қиылыспайды және ағаш құрайды, сондықтан проблеманың осы атауы берілген. N = 3 жағдайындағы мәселе ұзақ уақыт бойы зерттелді және тез арада барлық N берілген нүктелерге жалғанатын, ең аз жалпы ұзындығы бар бір орталықты жұлдыз тәрізді желіні табу мәселесіне дейін кеңейтілді. Дегенмен, толық Штайнер ағашы проблемасы Гаусс хатында тұжырымдалған болса да, оның алғашқы толық зерделенуі 1934 жылы Войтех Ярник және басқалар жазған чех тіліндегі мақалада болды. Бұл мақала ұзақ уақыт бойы назардан тыс қалды, бірақ ол кейіннен басқа зерттеушілерге, соның ішінде проблеманың жазықтықтан жоғары өлшемдерге жалпылануына жатқызылған «Штайнер ағаштарының барлық негізгі қасиеттерін» қамтиды. Евклидтік Штайнер проблемасы үшін графқа қосылған нүктелердің (Штайнер нүктелері) дәрежесі үш болуы керек, ал мұндай нүктеге түсетін үш қабырға үш 120 градустық бұрыш құруы керек (Ферма нүктесін қараңыз). Осыдан Штайнер ағашындағы Штайнер нүктелерінің максималды саны N - 2-ге тең, мұнда N – бастапқы берілген нүктелердің саны. (Бұл қасиеттердің барлығы Гергоннмен бұрыннан анықталған.) N = 3 үшін екі мүмкін жағдай бар: егер берілген нүктелер құрайтын үшбұрыштың барлық бұрыштары 120 градустан кіші болса, шешім Ферма нүктесінде орналасқан Штайнер нүктесімен беріледі; әйтпесе, шешім үшбұрыштың 120 градус немесе одан да үлкен бұрышта кездесетін екі қабырғасымен беріледі. Жалпы N үшін Евклидтік Штайнер ағашы проблемасы NP қиын, сондықтан полиномиалдық уақыт алгоритмін қолдану арқылы оңтайлы шешім табуға бола ма, жоқ па, белгісіз. Алайда, Евклидтік Штайнер ағаштары үшін полиномиалдық уақытқа жуықтап шешу схемасы (PTAS) бар, яғни полиномиалдық уақыт ішінде жақын оңтайлы шешім табуға болады. Евклидтік Штайнер ағашының NP толық екендігі белгісіз, себебі оның NP күрделілік класына жататындығы белгісіз.

The original problem was stated in the form that has become known as the Euclidean Steiner tree problem or geometric Steiner tree problem: Given N points in the plane, the goal is to connect them by lines of minimum total length in such a way that any two points may be interconnected by line segments either directly or via other points and line segments. While the problem is named after Steiner, it has first been posed in 1811 by Joseph Diez Gergonne in the following form: "A number of cities are located at known locations on a plane; the problem is to link them together by a system of canals whose total length is as small as possible". It may be shown that the connecting line segments do not intersect each other except at the endpoints and form a tree, hence the name of the problem. The problem for N = 3 has long been considered, and quickly extended to the problem of finding a star network with a single hub connecting to all of the N given points, of minimum total length. However, although the full Steiner tree problem was formulated in a letter by Gauss, its first serious treatment was in a 1934 paper written in Czech by Vojtěch Jarník and cs. This paper was long overlooked, but it already contains "virtually all general properties of Steiner trees" later attributed to other researchers, including the generalization of the problem from the plane to higher dimensions. For the Euclidean Steiner problem, points added to the graph (Steiner points) must have a degree of three, and the three edges incident to such a point must form three 120 degree angles (see Fermat point). It follows that the maximum number of Steiner points that a Steiner tree can have is N − 2, where N is the initial number of given points. (all these properties were established already by Gergonne.) For N = 3 there are two possible cases: if the triangle formed by the given points has all angles which are less than 120 degrees, the solution is given by a Steiner point located at the Fermat point; otherwise the solution is given by the two sides of the triangle which meet on the angle with 120 or more degrees. For general N, the Euclidean Steiner tree problem is NP hard, and hence it is not known whether an optimal solution can be found by using a polynomial time algorithm. However, there is a polynomial time approximation scheme (PTAS) for Euclidean Steiner trees, i. e., a near optimal solution can be found in polynomial time. It is not known whether the Euclidean Steiner tree problem is NP complete, since membership to the complexity class NP is not known.

Тікелей Штайнер ағашы

Тікелей Штайнер ағашы мәселесі – жазықтықтағы геометриялық Штайнер ағашы мәселесінің бір түрі, онда евклидтік қашықтық тікбұрышты қашықтықпен алмастырылады. Бұл мәселе электрондық дизайнды автоматтандырудың физикалық жобалау кезінде туындайды. VLSI тізбектерінде сымдарды тарту көбінесе дизайн ережелерімен тік және көлденең бағыттарда ғана жүргізілуімен шектеледі, сондықтан тікбұрышты Штайнер ағашы мәселесі екі терминалынан артық нүктелері бар желілерді тартуды модельдеу үшін қолданылуы мүмкін.

Штайнер ағашы графиктер мен нұсқаларда

Штайнер ағаштары салмақты графтар аясында кеңінен зерттелді. Прототипі – графтардағы Штайнер ағашы мәселесі. G = (V, E) – теріс емес жиек салмағы c бар бағытталмаған граф болсын, ал S ⊆ V – терминалдар деп аталатын төбелердің ішкі жиыны болсын. Штайнер ағашы – G-дегі S-ті байланыстыратын ағаш. Мәселе екі түрде келеді: Штайнер ағаштарымен байланысты оптимизация мәселесінде міндет – ең төмен салмақты Штайнер ағашын табу; шешімді табу мәселесінде жиек салмақтары бүтін сандар болып табылады және міндет – жалпы салмағы алдын ала белгіленген k табиғи санынан аспайтын Штайнер ағашының бар-жоғын анықтау. Шешімді табу мәселесі Карптың 21 NP-толық мәселесінің бірі; демек, оптимизация мәселесі NP-қиын. Графтардағы Штайнер ағашы мәселелері ғылыми зерттеулер мен өнеркәсіптегі әртүрлі мәселелерге қолданылады, оның ішінде көптүрлі маршрутизация және биоинформатика. Бұл мәселенің ерекше жағдайы – G толық граф болғанда, әрбір v ∈ V төбесі метрикалық кеңістіктегі нүктеге сәйкес келеді және әрбір e ∈ E жиегі үшін w(e) жиек салмақтары кеңістіктегі қашықтықтарға сәйкес келеді. Басқаша айтқанда, жиек салмақтары үшбұрыш теңсіздігін қанағаттандырады. Бұл нұсқа метрикалық Штайнер ағашы мәселесі деп аталады. (Метрикалық емес) Штайнер ағашы мәселесінің берілген мысалын полиномиал уақытта метрикалық Штайнер ағашы мәселесінің эквивалентті мысалына түрлендіруге болады; түрлендіру жуықтау коэффициентін сақтайды. Евклидтік нұсқа PTAS-ты қабылдаса да, метрикалық Штайнер ағашы мәселесі APX-толық екені белгілі, яғни P = NP болмаса, полиномиал уақытта 1-ге еркін жақын жуықтау коэффициенттерін алу мүмкін емес. Минималды Штайнер ағашын ; коэффициенті шегінде жуықтайтын полиномиал уақыт алгоритмі бар, бірақ коэффициенті шегінде жуықтау NP-қиын. Штайнер ағашының 1 және 2 қашықтықтағы шектеулі мәселесі үшін 1,25 жуықтау алгоритмі белгілі. Карпинский мен Александр Зеликовский Штайнер ағашы мәселелерінің тығыз жағдайлары үшін PTAS құрды. Граф мәселесінің ерекше жағдайында, квази-екі бөлікті графтар үшін Штайнер ағашы мәселесінде S-ге G-дегі әрбір жиектің кем дегенде бір ұшын қосу қажет. Штайнер ағашы мәселесі жоғары өлшемдерде және әртүрлі беттерде зерттелді. Штайнердің минималды ағашын табу алгоритмдері сфера, тор, проекциялық жазықтық, кең және тар конустарда және басқаларында табылды. Штайнер ағашы мәселесінің басқа жалпыламалары – k жиекпен байланысты Штайнер желісі мәселесі және k төбемен байланысты Штайнер желісі мәселесі, мұнда мақсат – k жиекпен немесе k төбемен байланысты графты табу, кез келген байланысты графты емес. Тағы бір жақсы зерттелген жалпылама – тірі қалу желісін жобалау мәселесі (SNDP), онда әрбір төбе жұбын берілген санмен (мүмкін 0) жиек немесе төбелердің ажыратылған жолдарымен қосу міндеті тұрады. Штайнер мәселесі метрикалық кеңістіктердің жалпы жағдайында және мүмкін шексіз көп нүктелер үшін де қойылды.

Steiner trees have been extensively studied in the context of weighted graphs. The prototype is, arguably, the Steiner tree problem in graphs. Let G = (V, E) be an undirected graph with non negative edge weights c and let S ⊆ V be a subset of vertices, called terminals. A Steiner tree is a tree in G that spans S. There are two versions of the problem: in the optimization problem associated with Steiner trees, the task is to find a minimum weight Steiner tree; in the decision problem the edge weights are integers and the task is to determine whether a Steiner tree exists whose total weight does not exceed a predefined natural number k. The decision problem is one of Karp's 21 NP complete problems; hence the optimization problem is NP hard. Steiner tree problems in graphs are applied to various problems in research and industry, including multicast routing and bioinformatics. A special case of this problem is when G is a complete graph, each vertex v ∈ V corresponds to a point in a metric space, and the edge weights w(e) for each e ∈ E correspond to distances in the space. Put otherwise, the edge weights satisfy the triangle inequality. This variant is known as the metric Steiner tree problem. Given an instance of the (non metric) Steiner tree problem, we can transform it in polynomial time into an equivalent instance of the metric Steiner tree problem; the transformation preserves the approximation factor. While the Euclidean version admits a PTAS, it is known that the metric Steiner tree problem is APX complete, i. e., unless P = NP, it is impossible to achieve approximation ratios that are arbitrarily close to 1 in polynomial time. There is a polynomial time algorithm that approximates the minimum Steiner tree to within a factor of ;
however, approximating within a factor is NP hard. For the restricted case of Steiner Tree problem with distances 1 and 2, a 1.25 approximation algorithm is known. Karpinski and Alexander Zelikovsky constructed PTAS for the dense instances of Steiner Tree problems. In a special case of the graph problem, the Steiner tree problem for quasi bipartite graphs, S is required to include at least one endpoint of every edge in G.

The Steiner tree problem has also been investigated in higher dimensions and on various surfaces. Algorithms to find the Steiner minimal tree have been found on the sphere, torus, projective plane, wide and narrow cones, and others. Other generalizations of the Steiner tree problem are the k edge connected Steiner network problem and the ''k'' vertex connected Steiner network problem, where the goal is to find a k edge connected graph or a k vertex connected graph rather than any connected graph. A further well studied generalization is the survivable network design problem (SNDP) where the task is to connect each vertex pair with a given number (possibly 0) of edge or vertex disjoint paths. The Steiner problem has also been stated in the general setting of metric spaces and for possibly infinitely many points.

Штайнер ағашына жақындау

Жалпы график Штайнер ағашы мәселесін 1981 жылы Ку және авторлар жариялағандай, терминалдық төбелерден туындаған график метрикалық жабылуының кіші ағашының ең төмен салмақты ағашын есептеу арқылы жуықтауға болады. График G-нің метрикалық жабылуы – G-дегі төбелер арасындағы ең қысқа жол қашықтығымен салмақталған толық график. Бұл алгоритм салмағы оптималды Штайнер ағашы салмағының 2 − 2/t факторының ішінде болатын ағаш жасайды, мұнда t – оптималды Штайнер ағашындағы жапырақтар саны; бұл оптималды Штайнер ағашы бойынша саяхатшы сатушының айналымын қарастыру арқылы дәлелдеуге болады. Бұл жуықталған шешімді O(|S||V|²) полиномдық уақытта есептеуге болады, алдымен метрикалық жабылуды есептеу үшін барлық жұптар арасындағы ең қысқа жолдар мәселесін шешу арқылы, содан кейін ең төмен салмақты ағаш мәселесін шешу арқылы. Штайнер ағашын графиктерде жуықтау үшін тағы бір танымал алгоритмді 1980 жылы Такахаси және Мацуяма жариялады. Олардың шешімі Штайнер ағашын кездейсоқ төбеден бастап, ағаштан S жиынындағы әлі қосылмаған ең жақын төбеге дейінгі ең қысқа жолды қайта-қайта қосу арқылы біртіндеп құрайды. Бұл алгоритмнің жұмыс уақыты O(|S||V|²) және салмағы 2 − 2/|S| оптималды жуыққа дейін ағаш жасайды. 1986 жылы Ву және авторлар барлық жұптар арасындағы ең қысқа жолдарды алдын ала есептеуді болдырмау арқылы жұмыс уақытын күрт жақсартты. Олар Крускал алгоритміне ұқсас тәсіл қолданады, ең төмен салмақты ағашты есептеу үшін бір-біріне қосылмаған |S| ағаштар жиынынан бастап, оларды бір мезгілде «өсіреді», Дикстра алгоритміне ұқсас ендік бірінші іздеуді қолданады, бірақ бірнеше бастапқы төбелерден басталады. Іздеу кезінде қазіргі ағашқа жатпайтын төбе кездескенде, екі ағаш біріктіріледі. Бұл процесс бір ғана ағаш қалғанша қайталанады. Басымдық кезегін жүзеге асыру үшін қалып (деректер құрылымы) және әрбір кіретін төбенің қай ағашқа жататынын қадағалау үшін бірікпеген жиынтық деректер құрылымын пайдалану арқылы бұл алгоритм O(|E| log |V|) жұмыс уақытын жетеді, бірақ Ку және авторлардың 2 − 2/t салмақ қатынасын жақсартпайды. Бірқатар мақалалар 2 − 2/t қатынасын жақсартатын жуықтау қатынастары бар ең төмен Штайнер ағашы мәселесі үшін жуықтау алгоритмдерін ұсынды. Бұл тізбек 2000 жылы Робинс пен Зеликовскийдің алгоритмімен аяқталды, ол ең төмен шығынды терминалдық кеңейту ағашын итеративті жақсарту арқылы қатынасты 1,55-ке жақсартты. Алайда, жақында Byrka және авторлар сызықтық бағдарламалауды жеңілдету және итеративті, кездейсоқ дөңгелектеу деп аталатын әдіс қолдану арқылы жуықтауды дәлелдеді.

The general graph Steiner tree problem can be approximated by computing the minimum spanning tree of the subgraph of the metric closure of the graph induced by the terminal vertices, as first published in 1981 by Kou et al. The metric closure of a graph G is the complete graph in which each edge is weighted by the shortest path distance between the nodes in G. This algorithm produces a tree whose weight is within a 2 − 2/t factor of the weight of the optimal Steiner tree where t is the number of leaves in the optimal Steiner tree; this can be proven by considering a traveling salesperson tour on the optimal Steiner tree. This approximate solution is computable in O(|S| |V|²) polynomial time by first solving the all pairs shortest paths problem to compute the metric closure, then by solving the minimum spanning tree problem. Another popular algorithm to approximate the Steiner tree in graphs was published by Takahashi and Matsuyama in 1980. Their solution incrementally builds up the Steiner tree by starting from an arbitrary vertex, and repeatedly adding the shortest path from the tree to the nearest vertex in S that has not yet been added. This algorithm also has O(|S| |V|²) running time, and produces a tree whose weight is within 2 − 2/|S| of optimal. In 1986, Wu et al. improved dramatically on the running time by avoiding precomputation of the all pairs shortest paths. Instead, they take a similar approach to Kruskal's algorithm for computing a minimum spanning tree, by starting from a forest of |S| disjoint trees, and "growing" them simultaneously using a breadth first search resembling Dijkstra's algorithm but starting from multiple initial vertices. When the search encounters a vertex that does not belong to the current tree, the two trees are merged into one. This process is repeated until only one tree remains. By using a Heap (data structure) to implement the priority queue and a disjoint set data structure to track to which tree each visited vertex belongs, this algorithm achieves O(|E| log |V|) running time, although it does not improve on the 2 − 2/t cost ratio from Kou et al. A series of papers provided approximation algorithms for the minimum Steiner tree problem with approximation ratios that improved upon the 2 − 2/t ratio. This sequence culminated with Robins and Zelikovsky's algorithm in 2000 which improved the ratio to 1.55 by iteratively improving upon the minimum cost terminal spanning tree. More recently, however, Byrka et al. proved an approximation using a linear programming relaxation and a technique called iterative, randomized rounding.

Штайнер ағашының параметрленген күрделілігі

Жалпы график Штайнер ағашы мәселесі Дрейфус-Вагнер алгоритмі арқылы, терминалдар саны параметр ретінде қарастырылғанда, шешілуге болатындығы белгілі. Дрейфус-Вагнер алгоритмінің орындалу уақыты , мұндағы – графтың төбелерінің саны, ал – терминалдар жиыны. Кез келген үшін уақытта орындалатын, немесе кіші салмақтар болған жағдайда, кез келген қабырғаның ең үлкен салмағы – уақытта орындалатын жылдам алгоритмдер де бар. Аталған алгоритмдердің кемшілігі – олар экспоненциалдық көлемді пайдаланады; уақыт және уақытта жұмыс істейтін полиномдық көлемді алгоритмдер бар. Жалпы график Штайнер ағашы мәселесінде, оңтайлы Штайнер ағашының қабырғаларының саны – болғанда, кез келген үшін уақытта орындалатын параметрленген алгоритмнің жоқ екені белгілі, егер Жиынтық жабу мәселесінде кейбір үшін, мұндағы және – жиынтық жабу мәселесінің мысалындағы элементтер саны және жиындар саны сәйкесінше, алгоритм болса. Сонымен қатар, егер оңтайлы Штайнер ағашының қабырғаларының санымен параметрленгенде және барлық қабырға салмақтары 1-ге тең болса, онда мәселе полиномдық ядроға ие емес екені белгілі.

Штайнер ағашының параметрленген шамалауы

Графтың Штайнер ағашы мәселесі терминалдар санымен параметрленбесе, полиномиялық ядроға ие болмайды, бірақ полиномиялық өлшемдегі жуық ядролық схеманы (PSAKS) қабылдайды: кез келген үшін полиномиялық өлшемдегі ядроны есептеуге болады, бұл шешім сапасында тек бір факторды жоғалтады. Графтың Штайнер ағашы мәселесін оптималдық шешімдегі терминал емес (Штайнер төбелері) саны бойынша параметрлеу кезінде мәселе W[1] қиын (жоғарыда айтылғандай, терминалдар саны бойынша параметрлеуге қарағанда). Сонымен қатар, мәселе APX-толық және сондықтан P = NP болмаса, PTAS-қа ие болмайды. Дегенмен, кез келген үшін уақыт ішінде жуықтап есептейтін параметрленген жуықтау схемасы бар. Сондай-ақ, осы параметрлеу үшін PSAKS бар. Болжам әлі де ашық. Мәселе үшін ең жақсы, кеңінен қабылданған жоғарғы шек – 1.2134.

Тікбұрышты Штайнер ағашы мәселесі үшін Штайнер қатынасы дәл , бұл квадраттың төрт нүктесімен қол жеткізілетін қатынас, онда үш жағы қолданылатын және төрт бұрыштың ортасы арқылы нүктелерді байланыстыратын Штайнер ағашы бар. Нақтырақ айтқанда, қашықтық үшін квадратты координаттық осьтерге қатысты бұру керек, ал қашықтық үшін квадрат осьтерге сәйкес болуы керек.