Encontre um argmax aproximado usando apenas consultas máximas aproximadas

10

Considere o seguinte problema.

Existem valores desconhecidos v 1 , , v nR . A tarefa é encontrar o índice do maior usando apenas consultas do seguinte formulário. Uma consulta é especificada por um conjunto S { 1 , , n } e a resposta correspondente é max i S v i . O objetivo é usar o menor número possível de consultas.nv1,,vnRS{1,,n}maxiSvi

Esse problema é fácil: podemos usar a pesquisa binária para encontrar o argmax com consultas . isto é, construa uma árvore binária completa com n folhas correspondentes aos índices. Comece pela raiz e desça até uma folha da seguinte maneira. Em cada nó, consulte o valor máximo nas subárvores direita e esquerda e, em seguida, vá para a criança ao lado com a resposta maior. Ao alcançar uma folha, produza seu índice.O(logn)n

A seguinte versão barulhenta desse problema surgiu em minha pesquisa.

Não há valores desconhecidos v 1 , , v n . Estes podem ser acedidos com consultas em que um conjunto S { 1 , , n } é especificado e uma amostra a partir de N ( max i S v i , 1 ) é devolvido. O objectivo é o de identificar i *{ 1 , , n } de tal modo que E [ v i * ]nv1,,vnS{1,,n}N(maxiSvi,1)i{1,,n} usando o menor número de consultas possível. (A expectativa é superior à escolha de i , que depende das moedas do algoritmo e das respostas ruidosas da consulta.)E[vi]maxivi1i

E[vi]maxiviO(logn)1O(log2n)O(log3n)

O(log2n)Ω(log2n)O~(logn)Ω(1)0O(logn)

Thomas
fonte
11/nc20
@daniello Isso funciona quando existe uma lacuna entre os valores maiores e os segundos maiores. O caso geral parece ser mais difícil.
Thomas
note to self: leia toda a pergunta antes de comentar #
daniello

Respostas:

1

B=Θ(logn){v1,,vn}={1nB,,n1nB,B}

Bn1nB

B1

logn(logn)2

Bn

Desculpe, isso está meio cozido, mas espero que possa ser útil!

usul
fonte
Ω(logn)Ω(log2n)
Ω(log2n)