Por que as taxas de aproximação diferencial não são bem estudadas em comparação às taxas padrão, apesar dos benefícios reivindicados?

16

supAOPTMINAAOPTinfΩAΩOPTΩ

  • fornece a mesma taxa de aproximação para problemas como cobertura mínima de vértices e conjunto independente máximo, que são conhecidos por serem apenas realizações diferentes do mesmo problema;
  • fornece a mesma proporção para as versões max e min do mesmo problema. Ao mesmo tempo, sabemos na teoria padrão MIN TSP e MAX TSP têm proporções muito diferentes.
  • Ele mede a distância não apenas ao ideal, mas também ao pessimum Ω . Assim, no caso da teoria de aproximação padrão Vertex Cover, diz que 2 é o melhor limite superior. Mas essencialmente 2 é a razão máxima entre o pessimista e o ideal. Assim, é garantido que esse algoritmo produza a solução com o pior valor.

Meu argumento é: na análise assintótica, não levamos em consideração constantes e termos de ordem inferior (aqui, lembrei a citação de Avi Widgerson: "Somos bem-sucedidos porque usamos o nível correto de abstração") e esse é o nível de abstração para comparar o uso de recursos do algoritmo. Mas quando estudamos a aproximação, por algum motivo, introduzimos a diferença nos lugares onde podemos evitá-la.

Minha pergunta é

por que a teoria da aproximação diferencial é tão pouco estudada. Ou os argumentos envolvidos não são fortes o suficiente?

Oleksandr Bondarenko
fonte
2
Eu nunca vi essa noção antes e acho que é pelo menos interessante. Muito curioso pelas respostas! (embora a verdadeira razão pode ser tão trivial como "Doh, nunca pensei sobre isso" ou "As provas são cada vez mais difícil" ou "Não é possível compará-lo com outros resultados quando eu começar")
Raphael

Respostas:

3

Há duas interpretações da afirmação "o algoritmo encontra uma aproximação do problema "UMAαP :

  1. O problema é fácil de resolver razoavelmente bem, pois temos um algoritmo que encontra uma boa aproximação.P
  2. O algoritmo é bom , pois encontra uma boa aproximação.UMA

Penso que a definição clássica do fator de aproximação enfatiza a primeira interpretação. Classificamos os problemas de acordo com a facilidade de resolução deles.

A taxa de aproximação diferencial parece colocar um pouco mais de peso na segunda interpretação: não queremos "recompensar" algoritmos triviais (por exemplo, algoritmos que acabam de gerar um conjunto vazio ou o conjunto de todos os nós).

Obviamente, ambos são pontos de vista válidos, mas são pontos de vista diferentes .


Também podemos estudar a questão de uma perspectiva um pouco mais prática. Infelizmente, as coberturas de vértices, como tal, não têm muitos usos diretos, mas, por uma questão de argumento, vamos considerar essas duas aplicações (um tanto inventadas):

  • Capa de vértice: nós são computadores e bordas são links de comunicação; queremos monitorar todos os links de comunicação e, portanto, pelo menos um ponto final de cada borda precisa executar um processo especial.

  • Conjunto independente: nós são trabalhadores e arestas modelam conflitos entre suas atividades; queremos encontrar um conjunto de atividades sem conflitos que possa ser executado simultaneamente.

Agora, ambos os problemas têm uma solução trivial: o conjunto de todos os nós é uma cobertura de vértice e o conjunto vazio é um conjunto independente.

A principal diferença é que, com o problema de cobertura de vértices, a solução trivial faz o trabalho . Claro, estamos usando mais recursos do que o necessário, mas pelo menos temos uma solução que podemos usar na prática. No entanto, com o problema do conjunto independente, a solução trivial é completamente inútil . Não estamos fazendo nenhum progresso. Ninguém está fazendo nada. A tarefa nunca é concluída.

Da mesma forma, podemos comparar soluções quase triviais: vértice tampa que consiste nas extremidades de uma correspondência máxima, e conjunto independente que é o complemento de . Novamente, certamente realiza o trabalho em nosso aplicativo e, desta vez, não estamos desperdiçando recursos por mais do que o fator dois. No entanto, ser novamente um conjunto vazio, que é completamente inútil.CEuCCEu

Portanto, a definição padrão da garantia de aproximação nos diz diretamente se a solução é útil ou não. Uma aproximação 2 da cobertura de vértice faz o trabalho. Um conjunto independente sem qualquer garantia de aproximação pode ser completamente inútil.

Em certo sentido, a taxa de aproximação diferencial tenta medir "quão não trivial" é a solução, mas isso importa em qualquer uma dessas aplicações? (Isso importa em algum aplicativo?)

Jukka Suomela
fonte
Não entendi seu ponto na segunda parte. Qualquer escolha exagerada de vértices é uma cobertura viável, não precisamos saber que o algoritmo é uma aproximação de 2 para isso. Por outro lado, mesmo uma aproximação 2 para um conjunto independente pode muito bem produzir uma solução inviável. Portanto, parece que o perigo de inviabilidade está vinculado ao problema, e não aos limites de aproximação (não) conhecidos.
Raphael
@ Rafael: Uma aproximação de 2 do conjunto independente máximo é, por definição, um conjunto independente (e razoavelmente grande; certamente não é um conjunto vazio).
Jukka Suomela
Não importa, leia muito rapidamente. Mas ainda assim, acho que seu argumento deve ser formulado da seguinte maneira: um algoritmo sem garantia de aproximação realiza o trabalho no caso do VC, mas não no IS. (Você está comparando maçãs e peras lá, não é?) Mas então, como esse estudo se relaciona com a escolha da garantia? Qualquer um faria para obter soluções viáveis.
Raphael
@Raphael: Não, estou dizendo que o VC trivial tem uma garantia de aproximação finita (algo como ), e ele faz o trabalho, enquanto o IS trivial não tem uma garantia de aproximação finita, e não faça o trabalho. Portanto, as garantias de aproximação dizem pelo menos algo sobre a utilidade da solução. O(Δ)
Jukka Suomela
11
+1 porque os exemplos são divertidos. Eu não acho que exista uma diferença bem definida entre "o problema é fácil" e "existe um bom algoritmo", mas eu meio que o entendo em um nível vago.
Tsuyoshi Ito 30/01
3

Não estou familiarizado com a noção de aproximação diferencial e não tenho nenhuma teoria sobre por que ela não é bem estudada. No entanto, gostaria de salientar que nem sempre é desejável descrever o desempenho de um algoritmo de aproximação por uma única medida. Nesse sentido, acho difícil concordar que uma medida é melhor que outra.

Por exemplo, como você afirmou, a cobertura mínima de vértices admite um algoritmo de 2 aproximações em tempo polinomial, enquanto que é difícil para NP aproximar o conjunto independente máximo a qualquer razão constante. Embora eu entenda que isso pode ser surpreendente à primeira vista, ele tem um significado legítimo: (1) a cobertura mínima de vértices pode ser bem aproximada quando pequena, mas (2) não pode ser bem aproximada quando grande. Quando afirmamos que é NP-difícil aproximar a cobertura mínima de vértices (e o conjunto independente máximo) com qualquer razão de aproximação diferencial constante positiva, estamos efetivamente ignorando a propriedade (1). Provavelmente é bom o suficiente para alguns propósitos ignorar a propriedade (1), mas certamente nem sempre é o caso.

Observe que nem sempre usamos a taxa de aproximação para descrever o desempenho dos algoritmos de aproximação. Por exemplo, para declarar um resultado de inadequação baseado no teorema do PCP em sua total generalidade, precisamos da formulação baseada em problemas de lacuna. Veja minha resposta a outra pergunta para obter detalhes. Nesse caso, nem o uso da taxa de aproximação padrão nem a taxa de aproximação diferencial nos permitem declarar o resultado na generalidade total.

Tsuyoshi Ito
fonte
0 02OPTn/2
@Oleksandr: “No caso de Vertex Cover, embora a aproximação coincida com a pior solução quando OPT⩾n / 2, temos a razão 2.” Se você considera isso uma desvantagem ou não, é um ponto de vista. Pode-se argumentar que se toda solução tem o valor objetivo dentro de um fator de 2, então não importa muito qual solução um algoritmo produz. A taxa de aproximação padrão modela a situação como esta.
Tsuyoshi Ito 28/01
Se esse fator de 2 ou qualquer outro fator pequeno for a pior solução, esse resultado será de pouca utilidade.
Oleksandr Bondarenko
11
@Oleksandr: Como eu disse, esse é um ponto de vista.
Tsuyoshi Ito 28/01
3

Como Tsuyoshi aponta, o problema pode ser para que tipo de argumento você deseja usar o limite obtido. A seguir, tentarei desenvolver duas motivações diferentes.

α=UMAOPT

α=Ω-UMAΩ-OPTα100%

Portanto, dependendo do tipo de instrução que o limite derivado deve retornar, você deve escolher a alternativa adequada.

[Ω,OPT]

Rafael
fonte