O que é um algoritmo de aproximação bicritério?

O que é um algoritmo de aproximação bicritério? Isso continua aparecendo no caso de cluster de fluxo de dados. Isso está relacionado à otimização de múltiplos objetivos?

Foi aqui que me deparei com: cis.upenn.edu/~sudipto/mypapers/datastream.pdf. O artigo trata de uma versão em fluxo contínuo do algoritmo k-means. Existem referências no artigo, mas nenhuma delas fornece uma explicação sobre o que é um algoritmo de aproximação bicritério. Parece que não consigo encontrar nada no Google que me dê uma definição precisa.

Expandirei a resposta de Yuval Filmus , fornecendo uma interpretação baseada em problemas de otimização multiobjetivo .

Otimização e aproximação de objetivo único

Em ciência da computação, estudamos frequentemente problemas de otimização com um único objetivo (por exemplo, minimizar f ( x ) sujeito a alguma restrição). Ao provar, digamos, NP-completeness, é comum considerar o problema orçamentário correspondente . Por exemplo, no problema do clique máximo, o objetivo é maximizar a cardinalidade do clique, e o problema do orçamento é o problema de decidir se existe um clique de tamanho pelo menos k , em que k é fornecido como parte da entrada para o problema.

Quando não é possível calcular uma solução ótima com eficiência, como no caso do problema máximo de clique, buscamos um algoritmo de aproximação , uma função que gera uma solução dentro de um fator multiplicativo de uma solução ótima. Você também pode considerar um algoritmo de aproximação para o problema de orçamento, uma função que gera uma solução que satisfaça f ( x ) ≥ ck no caso de um problema de maximização, em que c seja um número menor que um. Nessa situação, a solução pode violar a restrição rígida f ( x ) ≥ k , mas a "gravidade" da violação é limitada por c .

Otimização multi-objetivo e aproximação de dois critérios

Em alguns casos, convém otimizar dois objetivos simultaneamente. Para um exemplo aproximado, convém maximizar minha "receita" e minimizar meu "custo". Em tal situação, não existe um valor ideal único, pois há uma troca entre os dois objetivos; para obter mais informações, consulte o artigo da Wikipedia sobre eficiência de Pareto .

Uma maneira de transformar um problema de otimização de dois objetivos em um problema de otimização de objetivo único (pelo qual podemos raciocinar sobre o valor ideal da função objetivo) é considerar os dois problemas de restrição , um para cada objetivo. Se o problema é maximizar simultaneamente f ( x ) enquanto minimiza g ( x ), o primeiro problema de restrição é minimizar g ( x ) sujeito à restrição f ( x ) ≥ k , onde k é fornecido como parte da entrada para esse problema de otimização de objetivo único. O segundo problema de restrição é definido da mesma forma.

Um algoritmo de aproximação de ( α , β ) - bicritério para o primeiro problema de restrição é uma função que pega um parâmetro de orçamento k como entrada e gera uma solução x tal que

• $f(x) \geq \alpha k$
• $g(x) \leq \beta g(x^*)$

$x^*$

• $f(x) \geq \alpha f(x^*)$
• $g(x) \leq \beta \ell$

Em outras palavras, o algoritmo de aproximação bicritério é simultaneamente uma aproximação para o problema de orçamento no primeiro objetivo e o problema de otimização no segundo objetivo. (Esta definição foi adaptada da página quatro de " Otimização submodular com restrições de capa e mochila submodulares", por Iyer e Bilmes, 2013.)

As desigualdades mudam de direção quando os objetivos mudam de máximo para mínimo ou vice-versa.

$k$$\rho$$k$$V_1,\ldots,V_k$$\rho$$E(V_1,\ldots,V_k)$$\rho$

$f(n),g(n) \geq 1$$f(n),g(n)$$V_1,\ldots,V_k$$f(n)\rho$$g(n)\mathrm{OPT}$$\mathrm{OPT}$$\rho$

Em outras palavras, um algoritmo de aproximação bicritério atinge uma certa taxa de aproximação, violando alguma restrição por uma quantidade limitada. Para um exemplo de algoritmo de aproximação bicritério para o problema descrito, consulte este artigo dos irmãos Makarychev.