Traveller minimax problem in plane: Complexity of approximate solution

被引：0

作者：

Sarvanov, VI

机构：

来源：

DOKLADY AKADEMII NAUK BELARUSI | 1995年 / 39卷 / 06期

关键词：

D O I：

暂无

中图分类号：

O [数理科学和化学]; P [天文学、地球科学]; Q [生物科学]; N [自然科学总论];

学科分类号：

07 ; 0710 ; 09 ;

摘要：

It is shown that for any epsilon > 0 an optimal solution of the planar bottleneck travelling salesman problem cannot be approximated in polynomial time within factor (2-epsilon) unless P = NP.

引用

页码：16 / 19

页数：4

共 50 条

[31] The malicious host: a minimax solution of the Monty Hall problem
Schuller, Jan C.
JOURNAL OF APPLIED STATISTICS, 2012, 39 (01) : 215 - 221
[32] On the numerical solution of a minimax control problem with a positional functional
M. I. Gomoyunov
D. V. Kornev
N. Yu. Lukoyanov
Proceedings of the Steklov Institute of Mathematics, 2015, 291 : 77 - 95
[33] A SUITABLE APPROXIMATE SOLUTION OF NEUMANN PROBLEM
LECOMTE, D
BATSALE, JC
INTERNATIONAL JOURNAL OF HEAT AND MASS TRANSFER, 1991, 34 (03) : 894 - 897
[34] An approximate analytic solution of the Blasius problem
Ahmad, Faiz
Al-Barakati, Wafaa H.
COMMUNICATIONS IN NONLINEAR SCIENCE AND NUMERICAL SIMULATION, 2009, 14 (04) : 1021 - 1024
[35] APPROXIMATE SOLUTION TO A BUBBLE GROWTH PROBLEM
KEHOE, P
CHEMICAL ENGINEERING SCIENCE, 1972, 27 (10) : 1895 - &
[36] Solution of the minimax interference filtering problem for angular measurements
Sokolov, S.V.
Telecommunications and Radio Engineering (English translation of Elektrosvyaz and Radiotekhnika), 1993, 48 (12): : 109 - 113
[37] Compact approximate solution to the Kondo problem
Bergmann, Gerd
Zhang, Liye
PHYSICAL REVIEW B, 2007, 76 (06):
[38] AN APPROXIMATE SOLUTION OF AN INVERSE STEFAN PROBLEM
DOUGLAS, J
SIAM REVIEW, 1966, 8 (04) : 563 - &
[39] AN APPROXIMATE SOLUTION OF THE ANNULAR CRACK PROBLEM
MASTROJANNIS, EN
KERMANIDIS, TB
INTERNATIONAL JOURNAL FOR NUMERICAL METHODS IN ENGINEERING, 1981, 17 (11) : 1605 - 1611
[40] Approximate solution of the inverse Richards' problem
Vocciante, Marco
Reverberi, Andrea P.
Dovi, Vincenzo G.
APPLIED MATHEMATICAL MODELLING, 2016, 40 (9-10) : 5364 - 5376

← 1 2 3 4 5 →