Existem outras medidas de qualidade: Dhamdhere et al . Estudam a distorção "média":
No entanto, a medida em que estou interessado aqui é a usada pelos métodos do tipo MDS, que analisam o erro aditivo médio :
Embora os métodos semelhantes ao MDS sejam estudados extensivamente fora da comunidade da theoryCS, estou ciente de apenas um artigo ( de Dhamdhere et al ) que examina a otimização sob essa medida, e também para o problema limitado de incorporação na linha ( ) (observação: a tese de 2005 de Tasos Sidiropoulos tem uma boa revisão de trabalhos anteriores)
Existe algum trabalho mais recente que as pessoas estejam cientes sobre a análise rigorosa da qualidade sob essa noção de erro? Embora esses problemas geralmente sejam difíceis de lidar com NP, o que mais me interessa são aproximações de qualquer tipo.
fonte
Posso estar faltando alguma coisa, mas por que ? Estamos interessados em aproximar-se de forma aditiva, portanto não podemos escalar para criar para todos os , certo?ϵ2≤(ρ−1)∑d(x,y)2 f(μ(x),μ(y))≥d(x,y) x,y
Uma vantagem aqui é que podemos fazer mal em comprimentos curtos e, em última análise, ficar bem. Além disso, o problema é fácil (para aproximar, até) se, digamos, queremos incorporar o ? (podemos escrever um programa matemático para capturar a pergunta?)ℓ2
fonte