Коллекция APX-сложные проблемы

11

Все знают «Garey & Johnson», и я всегда обращаюсь к ним, когда мне нужно выполнить преобразование для доказательства NP-твердости. Однако недавно я нуждался в доказательстве твердости APX, и мне интересно, есть ли подобный (и более современный ...?) Набор проблем, которые, как было показано, являются APX-сложными.

Кто-нибудь знает что-нибудь подобное? Мне трудно поверить, что не существует веб-сайта, систематически собирающего такие проблемы, но мои навыки работы с Google кажутся недостаточными.

Лукас Барт
источник

Ответы:

5

Я использовал этот сборник несколько раз ... Это то, к чему вы стремились?

Parzan
источник
Это уже очень приятно, спасибо! Тем не менее, оптимальным будет что-то еще более всестороннее и доступное для поиска APX-жесткости ... Я посмотрю, появится ли что-нибудь еще.
Лукас Барт
1
Можете ли вы предоставить какую-либо информацию о цитировании, которая поможет найти эту информацию, если ссылка перестанет работать? Мы хотим, чтобы ответы оставались полезными, даже если ссылка перестала работать (и мы предпочли бы не быть просто фермой ссылок).
DW
Похоже, эта коллекция является частью книги, а именно: Ausiello, Giorgio, et al. Сложность и аппроксимация: комбинаторные задачи оптимизации и их аппроксимирующие свойства. Springer Science & Business Media, 2012. springer.com/us/book/9783540654315 DOI: 10.1007 / 978-3-642-58412-1
Лукас Барт,