Estimates of the Deviation of Approximate Solutions from an Optimal Solution in Certain Problems of Discrete Optimization

摘要

For discrete optimization problems, estimates of the deviations from the optimal solution of the solution that is the closest to it with respect to the value of the goal function are considered. The general scheme for forming such estimates, which is refined for the one-dimensional knapsack problem and traveling salesman problem on a plane, is developed. The Boolean knapsack problem is experimentally investigated.