Знаете ли вы какие-либо современные вики, посвященные задачам оптимизации NP, с их наилучшим приближением и результатом твердости?
Судя по отзывам, можно предположить, что такого ресурса нет (см. В конце этого вопроса два близких варианта). - добавлено 8 февраля.
Поскольку за последние два десятилетия появилось огромное количество результатов и проблем, наличие специальной вики может быть очень полезно для студентов и специалистов, работающих над предметом алгоритмов аппроксимации и сложности аппроксимации.
Мне предложили начать новую вики. Мне нравится эта идея, но перед тем, как начать, мне нужны отзывы:
Вас интересует вики, посвященная вышеуказанной теме, и собираетесь ли вы что-то добавить? Какой формат вы предпочитаете для этой вики (см. Мой предпочтительный формат в комментариях)? Должны ли мы использовать вики-ферму или вики-движок? В последнем случае, что вы предлагаете для вики-движка? Обсуждение MediaWiki?
Два ближайших варианта, которые мне известны, это:
1- «Сборник проблем оптимизации NP», под редакцией Пьерлуиджи Крещенци и Вигго Канна: Этот сборник, похоже, устарел. Я думаю, что объем текущих результатов не может управляться несколькими людьми, и если мы хотим обновленный список, у нас должна быть вики.
2- Википедия: эта вики предназначена для широкой аудитории, и у вас не может быть короткой страницы, включающей только описание проблемы и наилучшее приближение и результат твердости.
Ответы:
Когда вы ссылаетесь на сборник Кресценци-Канна, я не уверен, имеете ли вы в виду книгу или веб-сайт . Книга устарела, но авторы стараются постоянно обновлять сайт. Казалось бы, логичной отправной точкой является обращение к Кресценци и Канну с вашим предложением.
источник
Сложность Сад это вики, посвященная вычислительным задачам и их отношения к классам сложности. Как и предполагалось здесь, я планировал начать новую вики для алгоритмических результатов, но я подумал, что когда есть одна вики для вычислительных задач, мы можем хранить всю информацию в одном месте. Итак, я связался с людьми из зоопарка и с их разрешения изменил сферу деятельности Сада, чтобы включить также алгоритмические результаты.
Теперь мне нужна небольшая группа людей, чтобы помочь мне заполнить вики такого размера, чтобы мы могли публично объявить об этом и привлечь больше участников. Поскольку в этой вики используется та же система, что и в википедии, в среднем требуется 15-25 минут, чтобы добавить проблему. Таким образом, даже при том, что группа из 5 человек вносит только 3 проблемы в слабость (т.е. около 1 часа на каждого слабого), мы можем добавить 60 задач в месяц и иметь в общей сложности 100 проблем в Саду сложности.
источник
Да, и я обязательно буду рекламировать это!
Я сделаю все возможное, но не ожидайте, что я буду среди основных контент-провайдеров. Как указывает Цуёси Ито, это может занять много времени, и я не совсем считаю себя самым знающим человеком в этой области (на этом сайте или в другом месте).
Но контент, безусловно, со временем будет расти вместе с пользовательской базой, поэтому я не думаю, что вам следует слишком сильно беспокоиться о том, чтобы люди посвятили себя, например, 10 страниц в день.
Вопрос в том, сколько контента вы хотите предоставить и на какую аудиторию (ы) вы нацеливаетесь. Если я хочу выяснить, является ли моя проблема сложной, как я писал выше, было бы полезно иметь краткий обзор того, что выглядит как список, в котором элемент будет:ith
Проблемаi
Это то, что используют Garey & Johnson's и Kann & Crescenzi. Проблемы также могут быть помечены с использованием категорий, как мы считаем нужным, чтобы можно было легко создать список проблем по категориям (вроде как на вкусном: нажмите на тег «теория графа» и посмотрите список всех сложных проблем на графике). Теория на сайте).
Более подробную информацию можно затем получить, щелкнув название проблемы в списке, который будет содержать, например, список «простых» случаев, открытых проблем (например, «наилучшее приближение - 3/2, можем ли мы добиться большего успеха?») ссылки на Википедию или другие для более широкой аудитории, специализированное программное обеспечение, ...
Вы также можете, как и G & J, предоставить информацию о том, как были получены результаты («преобразование из X3C»). И тогда вы, вероятно, могли бы сгенерировать график, показывающий сокращение различных проблем, что заставило бы людей задуматься о том, существуют ли более прямые доказательства, но хорошо ... вам нужно где-то остановиться ;-)
Я пропущу последний подвопрос, потому что понятия не имею, как на него ответить.
источник
Я заинтересован и готов внести свой вклад, по крайней мере, немного в моей небольшой области знаний. Я не очень понимаю, почему вы хотите ограничить свое внимание приближением. Например, существует также устаревший сборник параметризованных задач, посвященный алгоритмам с фиксированными параметрами.
Кроме того, последняя часть G & J может рассматриваться как сборник NP-твердости.
ИМХО, вам следует подумать о Компендиуме вычислительных проблем, где для каждой проблемы вы указываете наиболее значимые (хорошие или плохие) результаты.
Я полностью согласен с форматом, предложенным в ответе Энтони Лабарре.
У меня есть небольшое предпочтение самодостаточной вики, но размещённая вики подойдет.
Мое единственное предложение заключается в том, что, если вы выберете ферму вики, обязательно сможете экспортировать все данные. Вы не можете быть уверены, что когда-нибудь ферма будет закрыта.
ИМХО требование - выбрать движок, поддерживающий формат LaTeX. Mediawiki и Dokuwiki являются наиболее распространенными и являются отличным выбором.
Mediawiki немного сложнее в установке и управлении (я бы сказал, умеренно сложный), но его синтаксис, вероятно, знаком большинству потенциальных участников.
Dokuwiki является более легковесным (как для необходимых ресурсов, так и для управления), но синтаксис частично отличается от синтаксиса Mediawiki.
источник