Изменения
Нет описания правки
максимальным целым числом меньшим <tex>\log_2 \left((1 + \varepsilon)^{-1}\mathrm{MINCON}(M)\right)</tex>.
Таким образом <tex>\lambda = 2^{\kappa} \ge \mathrm{MINCON}(M) / (2(1 + \varepsilon))</tex>, то есть была получена <tex>2(1 + \varepsilon)</tex> аппроксимация задачи MINCON.
Ранее было показано, что аппроксимация задачи MINCON является NP-трудной, таким образом NP-трудность задачи <tex>\varepsilon</tex>-LC доказана.
}}
== Источники ==
# Bringmann K., Friedrich T. Approximating the least hypervolume contributor: NP-hard in general, but fast in practice (2009)
