Discrete optimization problems with interval parameters

V. A. Perepelitsa, F. B. Tebueva

Karachaevo-Cherkessk State Academy of Technology, Stavropol'skaya ul. 36, Cherkessk, 357100 Russia

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.

Key words: discrete optimization problems with interval parameters, polynomial solvability, approximate algorithms.

UDC: 519.626

Received: 27.02.2007
Revised: 04.12.2009

 English version: Computational Mathematics and Mathematical Physics, 2010, 50:5, 795–804

Bibliographic databases:

• 
• 
•