|
|||||
|
|
Parametric simplex algorithms for a class of NP-Complete problems whose average number of steps is polynomial |
|
| Authors: | Hiroshi Konno Takahito Kuno Yasutoshi Yajima |
| Institution: | (1) Institute of Human and Social Sciences, Tokyo Institute of Technology, Tokyo, Japan;(2) Institute of Information Sciences and Electronics, University of Tsukuba, Tsukuba, Japan;(3) Department of Industrial Engineering and Management, Tokyo Institute of Technology, Tokyo, Japan |
| Abstract: | We will show that the average number of steps of parametric simplex algorithms for obtaining global minima of rank-one and rank-two bilinear-programming problems are lower-order polynomial functions of the problem size under the standard assumptions on the distribution of the data imposed in the probabilistic analysis of the simplex method. This means that there exist algorithms for some special class of NP-complete problems, whose average number of arithmetics are polynomial order of the problem size. |
| Keywords: | global optimization parametric simplex algorithm bilinear-programming complexity probabilistic analysis |
| 本文献已被 SpringerLink 等数据库收录！ | |