论文标题
关于具有间隔目标功能离散优化问题的近似解决方案的代表性
On the representativeness of approximate solutions of discrete optimization problems with interval objective function
论文作者
论文摘要
我们考虑了客观函数系数的间隔不认证的离散优化问题。间隔不确定性模型测量错误。 POS \ sible最佳解决方案是一种解决系数的某些可能值的最佳解决方案。可能解决方案的pro \ -ba \ -bi \ -li \ -ty是获得该解决方案最佳系数的概率。同样，我们用给定的准确性和溶液的概率定义了可能的近似解的概念。可能的近似解决方案是一个近似解决方案，该解决方案是通过某些固定近似算法（例如由贪婪算法。该解决方案的pro \ -ba \ -bi \ -li \ -ty是获得此类系数的概率，即该算法会产生解决方案作为其输出。我们考虑最佳或近似可能的解决方案Un \ -re \ -pre \ -sen \ -ta \ -Ti \ -ve如果其概率小于某些边界值。平均近似解决方案是系数间隔中点的可能近似解决方案。该解决方案可以作为近似解决方案的近似解决方案。我们表明，具有无代表性的近似解决方案的单个离散优化问题实例的份额可能足够宽，对于较小的误差值和边界值。对于任何其他可能的近似解决方案来说，都是如此：所有这些解决方案都可能没有代表性。
We consider discrete optimization problems with interval uncertatinty of objective function coefficients. The interval uncertainty models measurements errors. A pos\-sible optimal solution is a solution that is optimal for some possible values of the coefficients. Pro\-ba\-bi\-li\-ty of a possible solution is the probability to obtain such coefficients that the solution is optimal. Similarly we define the notion of a possible approximate solution with given accuracy and probability of the solution. A possible approximate solution is an approximate solution that is obtained for some possible values of the coefficients by some fixed approximate algorithm, e.g. by the greedy algorithm. Pro\-ba\-bi\-li\-ty of a such solution is the probability to obtain such coefficients that the algorithm produces the solution as its output. We consider optimal or approximate possible solution un\-re\-pre\-sen\-ta\-ti\-ve if its probability less than some boundary value. The mean approximate solution is a possible approximate solution for midpoints of the coefficients intervals. The solution may be treated as approximate solution for exact values of the coefficients. We show that the share of individual discrete optimization problems instances with unrepresentative mean approximate solution may be wide enough for rather small values of error and the boundary value. The same is true for any other possible approximate solution: all of them may be unrepresentative.
