48
правок
Изменения
Нет описания правки
{{В разработке}}
Гиперобъем является индикатором Парето -фронта, набирающим в последнее время популярность. Важной составляющей многих оптимизирующих алгоритмов, использующих индикатор гиперобъема, является вычисление вклада одного элемента Парето -фронта. К сожалению, даже вычисление минимального вклада (Minimal Contribution, MINCON) и нахождение соответствующего ему элемента (Least Contributor, LC) являются трудными задачами. Более того, даже аппроксимации этих задач являются NP-трудными.
== Используемые обозначения ==
<tex>M_{\lambda} = A \cup \{B\} \cup \{ C_{\lambda} \}</tex>.
Исходные элементы были сдвинуты вдоль первой оси, поэтому вклад этих элементов не изминилсяизменился, так как добавленная часть покрывается новым элементом <tex>B</tex>.
Также отметим, что вклад каждого из элементов множества <tex>A</tex> не превышает <tex>V</tex>.
должность минимального вкладчика, не присутствовавшего в начальном множестве <tex>M</tex>, является элемент <tex>C_{\lambda}</tex>. Его вклад в точности соответствует области
<tex>[0, 1] \times \ldots \times [0, 1] \times [2V, 2V + \lambda]</tex>, объем которой равен <tex>\lambda</tex>.
Таким образом, элемент <tex>C_{\lambda}</tex> является минимальным вкладчиком только, если при условии <tex>\lambda \le \mathrm{MINCON}(M)</tex>.
Так как умея решать задачу LC, мы можем проверять, является ли <tex>C_{\lambda}</tex> минимальным вкладчиком, можно
