Compêndio dos melhores resultados de aproximação e dureza para problemas de otimização de NP

26

Você conhece algum wiki atualizado dedicado a problemas de otimização de NP com seus melhores resultados de aproximação e dureza?

Com base no feedback, parece seguro presumir que não exista esse recurso (consulte o final desta pergunta para duas opções próximas). - adicionado em 8 de fevereiro.

Como existe um enorme corpo de resultados e problemas introduzidos nas últimas duas décadas, a existência de um wiki dedicado pode ser uma grande ajuda para estudantes e profissionais que trabalham com assuntos de algoritmos de aproximação e dureza de aproximação.

Fui sugerido para iniciar um novo wiki. Gosto da ideia, mas preciso de algum feedback antes de começar:
Você está interessado em um wiki dedicado ao assunto acima e vai contribuir com algo? Qual é o seu formato preferido para este wiki (veja o meu formato preferido nos comentários)? Devemos usar um farm wiki ou um mecanismo wiki? Neste último caso, qual é a sua sugestão para um mecanismo wiki? MediaWiki?

As duas opções mais próximas que eu conheço são:
1- "Um compêndio de problemas de otimização de NP", editado por Pierluigi Crescenzi e Viggo Kann: Esse compêndio parece estar desatualizado. Acho que o volume de resultados atuais não pode ser gerenciado por poucas pessoas e, se queremos uma lista atualizada, devemos ter um wiki.
2- Wikipedia: Este wiki é para o público em geral e você não pode ter uma página curta, apenas incluindo a descrição do problema, e os melhores resultados de aproximação e dureza.

ds.algorithms reference-request approximation-algorithms approximation-hardness Babak Behsaz
fonte
1
Acredito que podemos concluir com segurança que não existe esse recurso.
Jukka Suomela
3
@Suresh Eu estava pensando em uma página curta contendo apenas a descrição do problema (por exemplo, instâncias, soluções e a função objetivo) e os melhores resultados de aproximação e dureza com suas respectivas suposições e não contendo histórico, motivação, descrição do algoritmo etc. esse formato é mais fácil de criar e você pode encontrar os resultados mais recentes mais rapidamente do que uma página da Wikipedia. O compêndio editado por Crescenzi e Kann se encaixa nesse perfil, mas não é um wiki e, portanto, está desatualizado.
Babak Behsaz
8
você precisa de algo como o zoológico de complexidade então. talvez você deva começar um e solicitar voluntários daqui para ajudar a preenchê-lo.
Suresh Venkat
2
Um wiki seria útil. No entanto, eu acho que deveria ser mais do que simplesmente o problema e o resultado mais conhecido. O problema dessa abordagem é que ela será útil principalmente para a teoria das pessoas, enquanto uma página com mais informações provavelmente será útil para os profissionais; pode-se falar de casos especiais conhecidos e resultados relacionados etc. Por que não fazer uso total de links, comentários, referências etc.?
Chandra Chekuri
2
Não importa o que você acabe fazendo, eu recomendo tentar estabelecer links entre resultados como o zoológico de complexidade. É útil saber que uma melhoria na aproximação para o problema X implica algo para Y, e assim por diante. Além disso, a hierarquia de suposições de dureza de David Johnson (em uma coluna recente) também é algo que deveria estar lá.
Suresh Venkat

Respostas:

9

Quando você se refere ao compêndio Crescenzi-Kann, não tenho certeza se você está se referindo ao livro ou ao site . O livro está desatualizado, mas os autores tentam manter o site atualizado continuamente. Parece que o ponto de partida lógico é abordar Crescenzi e Kann com sua proposta.

Timothy Chow
fonte
É bom saber que os autores estão dispostos a manter o site atualizado continuamente. Tive a impressão de que eles pararam de atualizar em março de 2000, porque a maioria das páginas diz que foram atualizadas pela última vez em 20/03/2000.
Tsuyoshi Ito
3
Estou me referindo ao site. Não tenho certeza se eles estão editando mais ativamente. Eu me lembro de relatar uma melhoria na taxa de aproximação de um problema, mas eles não a atualizaram. De qualquer forma, concordo que é lógico entrar em contato com Crescenzi e Kann sobre o status de seu compêndio e a possibilidade de alterá-lo para um wiki.
Babak Behsaz
1
@Suresh @Anthony @Florent @Tsuyoshi @Jukka @Gianluca: Não consegui encontrar informações de contato do (Dr.?) Pierluigi Crescenzi. Então, enviei um email para o professor Kann em 9 de fevereiro e não recebi uma resposta. Em 16 de fevereiro, encaminhei meu e-mail anterior aos subeditores dos professores do compêndio Karpinski e Woeginger, mas novamente não recebi uma resposta. Enviei os dois e-mails com meu endereço de e-mail acadêmico, então acho que eles não acabaram nas suas pastas de spam. Qual é a sua sugestão agora?
Babak Behsaz
Eu acho que então um novo wiki poderia ser iniciado. Se em algum momento os autores do compêndio originais reclamar sobre isso, uma solução será encontrada facilmente (por exemplo, a fusão das duas recursos existentes)
Florent Foucaud
@Babak: No caso de você ainda estiver interessado, você pode encontrar-mail do Prof. Crescenzi aqui
Gianluca Della Vedova
7

Complexity Garden é um wiki dedicado a problemas computacionais e suas relações com classes de complexidade. Como sugerido aqui, eu estava planejando iniciar um novo wiki para os resultados algorítmicos, mas pensei que quando houver um wiki para problemas computacionais, poderemos ter todas as informações em um só lugar. Então, entrei em contato com o pessoal do zoológico e, com sua permissão, mudei o escopo do jardim para incluir também resultados algorítmicos.

Agora, preciso de um pequeno grupo de pessoas para me ajudar a preencher o wiki em um tamanho que possamos publicamente publicá-lo e atrair mais colaboradores. Como este wiki usa o mesmo sistema que a wikipedia, leva em média 15 a 25 minutos para adicionar um problema. Assim, mesmo com um grupo de 5 pessoas contribuindo com apenas 3 problemas fracos (ou seja, cerca de 1 hora por fraco), podemos adicionar 60 problemas em um mês e ter um total de 100 problemas no Jardim da Complexidade.

Babak Behsaz
fonte
1
Qual é o status da sua iniciativa?
Florent Foucaud
Não vejo mais acréscimos nessa página depois de 25 de agosto, portanto, presumo que Babak desanimado por falta de participantes. Perdi esse anúncio e tentarei contribuir o mais rápido possível.
Anthony Labarre
1

Você está interessado em um wiki dedicado ao assunto acima

Sim, e definitivamente vou anunciar!

e você vai contribuir com algo?

Contribuirei o máximo possível, mas não espere que eu esteja entre os principais provedores de conteúdo. Como aponta Tsuyoshi Ito, isso pode consumir muito tempo, e não me vejo como a pessoa mais experiente na área (neste site ou em outro lugar).

Mas o conteúdo certamente crescerá com a base de usuários, portanto, não acho que você deva se preocupar muito em ter pessoas comprometidas em contribuir, por exemplo, 10 páginas por dia cada.

Qual é o seu formato preferido para este wiki (veja o meu formato preferido nos comentários)?

ith

i

  • Instância: ...
  • Pergunta: ...
  • Referências: Para dureza, consulte [i1], para inadequação, consulte [i2], ...

É isso que Garey & Johnson's e Kann & Crescenzi usam. Os problemas também podem ser marcados usando categorias como entendermos, para que uma lista de problemas por categoria possa ser facilmente gerada (como no delicioso: clique na tag "graph-theory") e veja a lista de todos os problemas difíceis no gráfico teoria no site).

Informações mais detalhadas podem ser fornecidas clicando no nome do problema na lista, que conteria, por exemplo, uma lista de casos "fáceis", problemas abertos (por exemplo, "a melhor aproximação é 3/2, podemos fazer melhor?") links para Wikipedia ou outros para um público mais amplo, software especializado, ...

Você também pode, como G&J, fornecer informações sobre como os resultados foram obtidos ("transformação de X3C"). E então você provavelmente poderia gerar um gráfico mostrando reduções entre problemas diferentes, o que levaria as pessoas a pensar se existem provas mais diretas, mas bem ... você precisa parar em algum lugar ;-)

Vou pular a última subquestão porque não tenho idéia de como respondê-la.

Anthony Labarre
fonte
Eu acho que iniciar um wiki não precisa de muito esforço. Você só precisa configurar um mecanismo wiki (não deve ser tão difícil), escrever uma página principal, escrever uma página sobre o formato obrigatório de páginas e compor uma página de exemplo (por exemplo, para o problema de capa do conjunto). O resto pode ser feito ao longo do tempo. Pode parecer um pouco simplista, mas acho que se houver interesse suficiente da comunidade teórica, os problemas serão resolvidos ao longo do tempo e o wiki crescerá.
Babak Behsaz
1
@Babak: Eu acho que você definitivamente precisa de conteúdo real para começar. Esse conteúdo real pode ser copiado e colado do compêndio, se os autores estiverem felizes com isso. É difícil imaginar que uma caixa vazia apenas com um sistema atraia usuários.
Tsuyoshi Ito
@ Acho que, a princípio, a maioria dos usuários será quem quiser contribuir com o wiki, não necessariamente usá-lo. Não tenho certeza de quantos membros da comunidade gostam de contribuir dessa maneira, mas eu mesmo teria feito isso se houvesse um wiki quase vazio. O ponto é que entre duas opções de não ter um wiki ou ter um sistema de trabalho vazio, qual é o melhor. Eu acho que o último é inofensivo. Se pudermos encontrar algumas pessoas que desejam colocar mais esforço no wiki (por exemplo, copiar materiais de compêndio com permissão), isso é ótimo.
Babak Behsaz
Copiar (com permissão) o conteúdo do compêndio não deve ser muito esforço e será suficiente para um ponto de partida. De fato, por que não propor aos autores que transformem o compêndio existente em um wiki?
Florent Foucaud
2
@Babak: Concordo que um sistema de trabalho vazio é inofensivo. Eu só quero maximizar a probabilidade de sucesso. Para fazer isso, acredito que o conteúdo real é um fator-chave. Espero que os autores do compêndio atual estejam dispostos a alterá-lo para um wiki.
Tsuyoshi Ito 14/02
1

Você está interessado em um wiki dedicado ao assunto acima e vai contribuir com algo?

Estou interessado e estou disposto a contribuir, pelo menos um pouco no meu pequeno domínio de especialização. Eu realmente não entendo por que você quer restringir sua atenção à aproximação. Por exemplo, há também um compêndio desatualizado de problemas parametrizados, dedicado aos algoritmos de parâmetro fixo.

Além disso, a última porção de G&J pode ser vista como um compêndio de dureza NP.

IMHO, você deve pensar em um Compêndio de Problemas Computacionais em que, para cada problema, você declara os resultados mais relevantes (bons ou ruins).

Qual é o seu formato preferido para este wiki (veja o meu formato preferido nos comentários)?

Concordo plenamente com o formato proposto na resposta de Anthony Labarre.

Devemos usar um farm wiki ou um mecanismo wiki?

Tenho uma ligeira preferência por um wiki auto-hospedado, mas um wiki hospedado seria bom.

Minha única sugestão é que, caso você escolha um farm wiki, não deixe de exportar todos os dados. Você não pode ter certeza de que a fazenda será fechada algum dia.

Neste último caso, qual é a sua sugestão para um mecanismo wiki? MediaWiki?

IMHO, um requisito é escolher um mecanismo compatível com o formato LaTeX. O Mediawiki e o Dokuwiki são os mais difundidos e são excelentes opções.

O Mediawiki é um pouco mais complexo de instalar e gerenciar (eu diria moderadamente complexo), mas é provável que sua sintaxe seja familiar para a maioria dos possíveis colaboradores.

O Dokuwiki é mais leve (nos recursos necessários e no esforço de gerenciamento), mas a sintaxe é parcialmente diferente da do Mediawiki.

Gianluca Della Vedova
fonte