Gerando um ponto em um polítopo racional

8

Considere um politopo racional que é definido por meio de um oráculo de separação. Ou seja, pode ser descrito implicitamente como , mas como é muito grande, usamos um oracle, que dado um ponto , quer diz ou retorna uma meia-espaço de tal modo que .P P = { x R k : A x b , A Z m × k , b Z m } m x R k x P x SPPP={xRk:Axb,AZm×k,bZm}mxRkxPxS

Meu objetivo é encontrar um ponto em ou determinar se está vazio. Eu estou apontando para um tempo de execução polinomial no tamanho representação de e , onde é o maior valor absoluto em . Ou seja, o algoritmo deve fazer apenas polinômios muitas chamadas para o oráculo de separação.P U k U APPUkUA

Em geral, pode estar contido em um hiperplano de menor dimensão e, portanto, é problemático usar o método elipsóide. Assim, como no truque da Khachiyan, eu alter (e o oráculo separação) para usar , onde é algo como . Intuitivamente, os meios espaços que definem são os mesmos que definem apenas que são traduzidos por . O politopo tem as seguintes propriedades: está vazio se estiver vazio e se não estiver vazio,P P ε ε 1 / L P ε P ε P ε P ε P P P εPPPϵϵ1/UPϵPϵPϵPϵPPPϵ é totalmente dimensional.

Minha pergunta é a seguinte: Suponha que o algoritmo encontre um ponto . É possível gerar um ponto em usando ? P ppPϵPp

Cara
fonte

Respostas:

8

A partir de qualquer escolha de um poliepítopo em R k , ε , e um ponto Q em R k é possível encontrar um poliepítopo P em R k + 1 , em conjunto com uma incorporação de R k em R k + 1 , tal que P está dentro ε distância Hausdorff de (a imagem incorporada de) P e de tal modo que (a imagem incorporada de) q pertence a P εPRkϵqRkP^Rk+1RkRk+1P^ϵPqP^ϵ. Para isso, basta fazer as facetas de P ser quase paralela à imagem incorporada de R k , de modo que traduzi-las por ε em R k + 1 faz com que a sua intersecção com R k a afastar- P por uma maior distância muito .P^RkϵRk+1RkP^

Como foi arbitrário, o conhecimento de q não serve para encontrar um ponto em ou próximo de P ; tudo o que você poderia fazer com ele, você poderia fazer sem ele. Mas, por causa P e P são tão próximos, encontrar um ponto próximo P é equivalente a encontrar um ponto próximo P . Portanto, o conhecimento de q (um ponto em P ε ) é de nenhum uso em encontrar um ponto próximo P .qqPP^PPP^qP^ϵP^

David Eppstein
fonte
Obrigado! Eu adicionei uma suposição de que o politopo é racional, então (espero) agora, não há esperança de encontrar um ponto em P.
Guy
Essa restrição não ajuda; é fácil de fazer P racional na construção de David. P^
Jeffε
Suponho que o questionador esteja realmente perguntando como encontrar um ponto quando P não estiver totalmente dimensional. pPP
Chandra Chekuri 28/07/12
2

Se seu objetivo é encontrar um ponto em ou determinar que P está vazio, por que você não faz o seguinte.PP

Seja um conjunto de semi-espaços, inicialmente vazios.H

Seja um ponto, inicialmente igual a 0 k .x0k

  1. ao oráculo.x

  2. Se o oráculo disse , você já fez.xP

  3. Caso contrário, seja o meio espaço violado retornado pelo oráculo. Vamos y ser a projecção ortogonal de x em S . SyxS

    • Se existe pelo menos um tal que y T , então você fez: P está vazio.THyTP
    • Caso contrário, defina e defina x : = y . H:=H{S}x:=y
  4. Volte para 1.

Giorgio Camerani
fonte
Obrigado pela resposta. Eu acho que ele vai trabalhar, mas, a menos que eu estou faltando alguma coisa, o tempo de execução será porportional a , o número de meias-espaços que definem P . Eu estou esperando por um tempo de execução que é polinomial em k e a representação de U , que é o maior valor absoluto em A . Ou seja, apenas polinômios são chamados para o oráculo. mPkUA
26612 Guy
Você é bem vindo! Você tem certeza de que esse requisito sobre o tempo de execução é evidente lendo a pergunta?
Giorgio Camerani
1
Você está certo. Eu vou adicionar.
26612 Guy