Incorporação média de distorção

11

(X,d)(Y,f)μ:XYμ

ρ=maxp,qX{d(x,y)f(μ(x),μ(y)),f(μ(x),μ(y))d(x,y)}

Existem outras medidas de qualidade: Dhamdhere et al . Estudam a distorção "média":

σ=d(x,y)f(μ(x),μ(y)).

No entanto, a medida em que estou interessado aqui é a usada pelos métodos do tipo MDS, que analisam o erro aditivo médio :

ε2=|d(x,y)f(μ(x),μ(y))|2

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 ( Y=R ) (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.

Suresh Venkat
fonte

Respostas:

3

Esta é uma boa pergunta. Não conheço algoritmos de aproximação, mas os resultados de dureza conhecidos para a aproximação da distorção mínima (e problemas relacionados, como a rotulagem métrica) também devem mostrar que é difícil aproximar .ϵ2

A razão é que eles fornecem uma redução de um problema NP-rígido, de modo que, no caso SIM, a distorção é e, no caso NÃO, a distorção é por pelo menos uma fração constante das arestas. Portanto, no caso SIM, será um fator menor que no caso NÃO. Para detalhes, veja, por exemplo, o artigo de Khot-Saket: www.cs.cmu.edu/~rsaket/pubs/approx.pdfΩ ( k ) ϵ 2 kO(1)Ω(k)ϵ2k

Não tenho muita certeza de qual fator de dureza segue o artigo deles, mas não deve ser difícil descobrir. (Eu acho que pelo menos o fator que você obtém para rotular métricas deve seguir.)logc(n)

Moritz
fonte
essa é uma boa sugestão. Definitivamente vou analisar o trabalho de rotulagem métrica. Sabe-se que mesmo a incorporação na linha é difícil para o MAX SNP, mas seria interessante (embora decepcionante) obter resultados mais fortes.
Suresh Venkat
2

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)2f(μ(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

aditya
fonte
Bom ponto. Eu mudei minha resposta.
Moritz
isso depende da formulação. Se você colocar o problema como minimizador para um subespaço de destino de dimensão fixa, as restrições de classificação causam alguns problemas. Se você usar a formulação "estilo JL" (ou seja, corrigir o erro e encontrar a dimensionalidade correta), algo poderá ser possível. ϵ
Suresh Venkat
Uma quantidade que pode ser útil para "competir" é . Considere o problema de incorporar em (sugeri anteriormente, mas ele possui o sqrt confuso). Devemos visar claramente a obtenção de incorporações que tenham sendo (em um sentido vago, isso significa que estamos fora multiplicativamente para a maioria de . Podemos obter essa incorporação para, digamos (grau const) expansores (ou provar que não é possível?)?1 2 ϵ 2 o ( S ) ( 1 + o ( 1 ) ) x , yS:=d(x,y)212ϵ2o(S)(1+o(1))x,y
aditya