<<
>>

Аппроксимация посредством сведения

Прежде чем переходить к разработке алгоритма, мы обсудим один интересный во- прос: задача о вершинном покрытии легко сводится к задаче покрытия множества, для которой мы только что рассмотрели аппроксимирующий алгоритм.
Какие вы- воды можно сделать относительно аппроксимируемости вершинного покрытия? При рассмотрении этого вопроса проявляются некоторые неочевидные аспекты взаимодействия результатов аппроксимации со сведениями с полиномиальным временем.

Начнем с частного случая, в котором все веса равны 1, — иначе говоря, ищется вершинное покрытие минимального размера. Назовем этот случай невзвешенным. Вспомните, что для доказательства ЖР-полноты задачи покрытия множества ис- пользовалось сведение от невзвешенной версии задачи о вершинном покрытии с принятием решения, то есть

Вершинное покрытие

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Аппроксимация посредством сведения:

  1. Статья 422. Разглашение сведений военного характера, составляющих государственную тайну, или потеря документов или материалов, содержащих такие сведения
  2. 16.3. Перечни сведений, составляющих государственную тайну, и сведения, которые не могут относиться к государственной тайне
  3. Доказательство посредством улик.
  4. Конституирование общества посредством коммуникации
  5. Статья 158. Фальсификация избирательных документов, документов референдума или фальсификация итогов голосования, предоставление ложных сведений в органов Государственного реестра избирателей или фальсификация сведений Государственного реестра избирателей
  6. § 13. Исполнение денежного обязательства посредством внесения долга в депозит (п. 2062-2065)
  7. § 14 Условное соглашение. – Предложение и вызов. – Договор посредством публичного торга или состязания. – Одностороннее обещание.
  8. 16.6. Рассекречивание сведений и их носителей
  9. 16.7. Распоряжение сведениями, составляющими государственную тайну
  10. Статья 895. Конфиденциальность сведений о договоре
  11. 16.4. Отнесение сведений к государственной тайне и их засекречивание
  12. Дорогой Мастер Крайон, расскажи, пожалуйста, об асанах, йоге, о том, как посредством тела изменить реальность, пространство, время и т.д. и т.п.?