¿Conoces alguna wiki actualizada dedicada a problemas de optimización de NP con su mejor resultado de aproximación y dureza?
Según los comentarios, parece seguro asumir que no existe dicho recurso (consulte el final de esta pregunta para conocer dos opciones cercanas). - agregado el 8 de febrero.
Dado que hay un gran conjunto de resultados y problemas introducidos en las últimas dos décadas, la existencia de un wiki dedicado podría ser de gran ayuda para los estudiantes y profesionales que trabajan en el tema de los algoritmos de aproximación y la dureza de la aproximación.
Me han sugerido comenzar una nueva wiki. Me gusta la idea, pero necesito algún comentario antes de comenzar:
¿Estás interesado en un wiki dedicado al tema anterior y vas a contribuir con algo? ¿Cuál es su formato preferido para este wiki (vea mi formato preferido en los comentarios)? ¿Deberíamos usar una granja wiki o un motor wiki? En el último caso, ¿cuál es su sugerencia para un motor wiki? MediaWiki?
Las dos opciones más cercanas que conozco son:
1- "Un compendio de problemas de optimización de NP", editado por Pierluigi Crescenzi y Viggo Kann: este compendio parece estar desactualizado. Creo que el volumen de resultados actuales no puede ser manejado por algunas personas y si queremos una lista actualizada, deberíamos tener un wiki.
2- Wikipedia: esta wiki es para el público en general y no puede tener una página corta que solo incluya la descripción del problema y el mejor resultado de aproximación y dureza.
Respuestas:
Cuando se refiere al compendio Crescenzi-Kann, no estoy seguro de si se refiere al libro o al sitio web . El libro está desactualizado pero los autores intentan mantener el sitio web actualizado continuamente. Parece que el punto de partida lógico es acercarse a Crescenzi y Kann con su propuesta.
fuente
Complexity Garden es un wiki dedicado a problemas computacionales y sus relaciones con las clases de complejidad. Como se sugirió aquí, estaba planeando comenzar un nuevo wiki para los resultados algorítmicos, pero pensé que cuando hay un wiki para problemas computacionales, podemos tener toda la información en un solo lugar. Entonces, contacté a la gente del zoológico y, con su permiso, cambié el alcance del Jardín para incluir también resultados algorítmicos.
Ahora, necesito un pequeño grupo de personas que me ayuden a completar la wiki a un tamaño que podamos anunciar públicamente y atraer a más colaboradores. Como este wiki usa el mismo sistema que wikipedia, se tarda 15-25 minutos en promedio para agregar un problema. Por lo tanto, incluso con un grupo de 5 personas que contribuyen con solo 3 problemas débiles (es decir, alrededor de 1 hora por débil), podemos agregar 60 problemas en un mes y tener un total de 100 problemas en el Jardín de Complejidad.
fuente
Sí, ¡y definitivamente lo anunciaré!
Contribuiré tanto como sea posible, pero no esperes que esté entre los principales proveedores de contenido. Como señala Tsuyoshi Ito, esto puede llevar mucho tiempo, y tampoco me veo como la persona más experta en el área (en este sitio web o en otro lugar).
Pero el contenido ciertamente crecerá con la base de usuarios, por lo que no creo que deba preocuparse demasiado por tener personas comprometidas a contribuir, por ejemplo, 10 páginas al día cada una.
Existe la pregunta de cuánto contenido desea proporcionar y a qué público (s) se dirige. Si quiero averiguar si mi problema es difícil, como escribí anteriormente, es bueno tener una visión general rápida de lo que parece ser una lista donde estaría el elemento :ith
Problemai
Que es lo que usan Garey & Johnson y Kann & Crescenzi. Los problemas también se pueden etiquetar usando categorías como mejor nos parezca, de modo que se pueda generar fácilmente una lista de problemas por categoría (algo así como delicioso: haga clic en la etiqueta "teoría de gráficos" y vea la lista de cada problema difícil en el gráfico teoría en el sitio web).
Se podría proporcionar información más detallada haciendo clic en el nombre del problema en la lista, que contendría, por ejemplo, una lista de casos "fáciles", problemas abiertos (por ejemplo, "la mejor aproximación es 3/2, ¿podemos hacerlo mejor?") enlaces a Wikipedia u otros para una audiencia más amplia, software especializado, ...
También puede, como lo hizo G&J, proporcionar información sobre cómo se obtuvieron los resultados ("transformación de X3C"). Y luego probablemente podría generar un gráfico que muestre reducciones entre los diferentes problemas, lo que llevaría a la gente a preguntarse si existen más pruebas directas, pero bueno ... tiene que detenerse en algún lugar ;-)
Me saltearé la última subpregunta porque no tengo idea de cómo responderla.
fuente
Estoy interesado y estoy dispuesto a contribuir, al menos un poco en mi pequeño dominio de experiencia. Realmente no entiendo por qué quieres restringir tu atención a la aproximación. Por ejemplo, también hay un Compendio de problemas con parámetros obsoletos dedicado a los algoritmos de parámetros fijos.
Además, la última parte de G&J puede verse como un compendio de dureza NP.
En mi humilde opinión, debe pensar en un Compendio de problemas computacionales donde, para cada problema, indique los resultados más relevantes (buenos o malos).
Estoy totalmente de acuerdo con el formato propuesto en la respuesta de Anthony Labarre.
Tengo una ligera preferencia por un wiki autohospedado, pero un wiki alojado estaría bien.
Mi única sugerencia es que, en caso de que elija una granja wiki, asegúrese de poder exportar todos los datos. No puede estar seguro de que la granja se cerrará algún día.
En mi humilde opinión, un requisito es elegir un motor que admita el formato LaTeX. Mediawiki y Dokuwiki son los más extendidos y son excelentes opciones.
Mediawiki es un poco más complejo de instalar y administrar (diría que moderadamente complejo) pero es probable que su sintaxis sea familiar para la mayoría de los posibles contribuyentes.
Dokuwiki es más liviano (tanto en recursos necesarios como en esfuerzo de gestión) pero la sintaxis es en parte diferente de Mediawiki.
fuente