Discrete optimization problems with interval parameters |
| |
| Authors: | V. A. Perepelitsa F. B. Tebueva |
| |
| Affiliation: | (1) Lawrence Livermore National Laboratory, Livermore, CA, USA;(2) Sandia National Laboratories, Albuquerque, NM, USA;(3) Argonne National Laboratory, Argonne, IL, USA;(4) University of Minnesota, Minneapolis, MN, USA |
| |
| Abstract: | Optimization problems on graphs with interval parameters are considered, and exponential and polynomial bounds for their computational complexity are obtained. For a certain subclass of polynomially solvable problems, two algorithms are proposed—one of them for finding an optimal solution and the other one for finding a suboptimal solution. Sufficient conditions for the statistical efficiency of the algorithm for finding a suboptimal solution are obtained. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
