perguntas gerais sobre como selecionar o melhor elemento de algum conjunto de alternativas disponíveis.
Estou um pouco confuso com a literatura de otimização contínua e a literatura do TCS sobre quais tipos de programas matemáticos (contínuos) (MPs) podem ser resolvidos com eficiência e quais não. A comunidade de otimização contínua parece afirmar que todos os programas convexos podem ser resolvidos...
Na minha formação em ciência da computação, percebo cada vez mais que a maioria dos problemas discretos é NP-completa (pelo menos), enquanto a otimização de problemas contínuos é quase sempre facilmente alcançável, geralmente através de técnicas de gradiente. Existem exceções para...
O que se sabe sobre a complexidade do seguinte problema: Dado: números racionais x1<x2<…<xnx1<x2<…<xnx_1 < x_2 < \dotso < x_n . Saída: números inteiros y1≤y2≤…≤yny1≤y2≤…≤yny_1 \le y_2 \le \dotso \le y_n . Objetivo: minimizar ∑1≤i<j≤ne(i,j),∑1≤i<j≤ne(i,j),\sum_{1 \le i < j...
Computadores quânticos são muito bons para distribuições de amostragem que não sabemos como amostrar usando computadores clássicos. Por exemplo, se f é uma função booleana (de a - 1 , 1 ) que pode ser calculada em tempo polinomial, então com computadores quânticos, podemos amostrar eficientemente...
Considere problemas de otimização do seguinte formulário. Seja uma função computável em tempo polinomial que mapeie uma sequência em um número racional. O problema de otimização é este: qual é o valor máximo de sobre as cadeias de bits ?x f ( x ) n xf(x)f(x)f(x)xxxf(x)f(x)f(x)nnnxxx Digamos que...
Estou interessado no problema de empacotar cópias idênticas de retângulos (bidimensionais) em um polígono convexo (bidimensional) sem sobreposições. No meu problema, você não tem permissão para girar os retângulos e pode assumir que eles estão orientados paralelamente aos eixos. Você recebe as...
O código de Huffman para uma distribuição de probabilidade ppp é o código de prefixo com a palavra de código ponderado média comprimento mínimo ∑piℓi∑piℓi\sum p_i \ell_i , onde ℓiℓi\ell_i é o comprimento do iii th codword. É um teorema bem conhecido que o comprimento médio por símbolo do código de...
Como sabemos, a função -clique pega um subgrafo ( estendendo-se ) de um gráfico -vertex completo , e gera se contém um -clique . As variáveis nesse caso correspondem às arestas de . Sabe-se (Razborov, Alon-Boppana) que, para , essa função requer circuitos monotônicos de tamanho em torno de . C L...
Você recebe um gráfico com n vértices. Pode ser bipartido, se você quiser. Existem m conjuntos de arestas E 1 , … , E m ⊆ E (digamos disjuntos). Estou interessado no problema de encontrar um subconjunto S ⊆ V , o menor possível (ou até menor), de modo que o gráfico induzido G S tenha pelo menos uma...
Meu filho de 8 anos se cansou de criar labirintos convencionais e passou a criar variantes que se parecem com isso: A idéia é começar de x e alcançar o através das regras normais. Além disso, você pode "saltar" de qualquer número inteiro para qualquer outro número inteiro b , mas você deve pagar...
É possível testar algoritmicamente se um número computável é racional ou inteiro? Em outras palavras, seria possível para uma biblioteca que implementa números computáveis fornecer as funções isIntegerou isRational? Suponho que isso não seja possível e que isso esteja de alguma forma relacionado...
Considere este problema: Dada uma lista de conjuntos finitos, localize os pedidos que minimizam .s1,s2,s3,…s1,s2,s3,…s_1, s_2, s_3, \ldots|s1|+|s1∪s2|+|s1∪s2∪s3|+…|s1|+|s1∪s2|+|s1∪s2∪s3|+…|s_1| + |s_1 \cup s_2| + |s_1 \cup s_2 \cup s_3| + \ldots Existem algoritmos conhecidos para isso? Qual é a...
Sabemos que os programas lineares (LP) podem ser resolvidos exatamente em tempo polinomial usando o método elipsóide ou um método de ponto interior como o algoritmo de Karmarkar. Alguns LPs com número super-polinomial (exponencial) de variáveis / restrições também podem ser resolvidos em tempo...
Há muitos anos, ouvi dizer que calcular o mínimo de AFN (autômato finito não determinístico) a partir de um AFD (determinístico) era uma questão em aberto, em oposição à direção vice-versa conhecida há décadas e que é bem pesquisada com um eficiente ( n lg n ) algoritmo. Alguém criou um algoritmo?O...
Considere o seguinte problema: Entrada : um hiperplano H = { y ∈ R n : a T y = b }H={y∈Rn:aTy=b}H = \{ \mathbf{y} \in \mathbb{R}^n: \mathbf{a}^T\mathbf{y} = {b}\} , dado por um vetor a ∈ Z na∈Zn\mathbf{a} \in \mathbb{Z}^n e b ∈ Zb∈Zb \in \mathbb{Z} na representação binária padrão. Saída : x ∈ Z n...
Eu fiz essa pergunta no Stack Overflow há um tempo atrás: Problema: a venda de Bob . Alguém sugeriu postar a pergunta aqui também. Alguém já fez uma pergunta relacionada a esse problema aqui - subfloresta de peso mínimo de determinada cardinalidade - mas, pelo que entendi, não me ajuda com o meu...
Considere o espaço dimensional e deixe ser uma restrição linear no formato , em que , e .{ 0 , 1 } n c a 1 x 1 + a 2 x 2 + a 3 x 3 + . . . + a n - 1 x n - 1 + a n x n ≥ k a i ∈ R x i ∈ { 0 , 1 } k ∈
Recentemente, fiquei interessado no problema geral de otimizar o uso da memória em uma situação em que há mais de um tipo de memória disponível e há uma troca entre a capacidade de um determinado segmento de memória e a velocidade de acesso a ele. O exemplo familiar é um programa que decide quando...
Estou preparando algum material do curso sobre heurística para otimização e tenho estudado métodos de descida coordenada. A configuração é aqui uma função multivariada que você deseja otimizar. tem a propriedade restrita a qualquer variável, é fácil otimizar. Portanto, a descida de coordenadas...
Sabemos que, se o intervalo entre os valores de um programa inteiro e seu dual (o "gap de dualidade") é zero, os relaxamentos de programação linear do programa inteiro e o dual do relaxamento admitem soluções integrais (integralidade zero " Gap = Vão"). Quero saber se o inverso vale, pelo menos em...