Жадные алгоритмы аппроксимации: различия между версиями

Жадные алгоритмы аппроксимации (посмотреть исходный код)

67 байт добавлено , 24 апреля 2015

м

4551

правка

Версия от 00:02, 24 апреля 2015 (просмотреть исходный код) Irina (обсуждение \| вклад) м (→‎Основные результаты) ← Предыдущая правка		Версия от 00:03, 24 апреля 2015 (просмотреть исходный код) Irina (обсуждение \| вклад) м (→‎Основные результаты) Следующая правка →
Строка 174:		Строка 174:


	Теперь можно провести корректный анализ жадного алгоритма A для MCDS [4]. Согласно лемме 3,		Теперь можно провести корректный анализ жадного алгоритма A для MCDS [4]. Согласно лемме 3, <math>f(C_i) - f(C_{i + 1}) \ge \frac{f(C_i) - 2}{opt} - 1</math>.