Dado um conjunto \(I = \{1, ..., n\}\) de itens, um conjunto \(B = \{1, ..., m\}\) de compradores, uma valoração \(v\), onde \(v_{ib}\) denota o valor do item \(i\) para o comprador \(b\), o Problema da Compra Máxima consiste em encontrar uma alocação de itens a compradores e uma precificação \(p\) tal que cada comprador recebe no máximo um item e se o comprador \(b\) recebe o item \(i\) então \(p_i \leq v_{ib}\). Aggarwal et al. [1] apresentaram uma \(e/(e-1)\)-aproximação para esse problema e posteriormente Briest e Krysta [2] mostraram que tal problema é APX-difícil.

Aggarwal et al. consideraram também a variante onde a precificação é não crescente, isto é, \(p_1 \geq \dots \geq p_n\) e apresentaram um PTAS para tal problema. Chamamos tal restrição na precificação de Escada de Preços.

Estamos interessados na versão do problema onde a oferta é limitada. Isto é, cada item \(i\) tem um inteiro positivo \(C_i\) associado e podemos atribuir \(i\) a no máximo \(C_i\) compradores (em contraste com o caso acima, onde a oferta é ilimitada). Fernandes e Schouery apresentaram uma \(e/(e-1)\)-aproximação para a versão sem Escada de Preços. Para a versão com Escada de Preços, Fernandes e Schouery apresentaram, para todo \(\epsilon > 0\), uma \((2+\epsilon)\)-aproximação. Porém, é curioso que a melhor razão de aproximação conhecida para esse problema é maior do que a melhor razão de aproximação conhecida para a versão sem Escada de Preços. Isso contradiz a intuição de que a versão com Escada de Preços deveria ser mais 'fácil' de aproximar, como acontece no caso de oferta ilimitada. Em particular, é possível que exista um PTAS para a versão com Escada de Preços.

[1] G. Aggarwal, T. Feder, R. Motwani e A. Zhu. Algorithms for multi-product pricing. Em Proc. of the 31th Int. Colloquium on Automata, Languages and Programming (ICALP), volume 3142 of Lecture Notes in Computer Science, páginas 72–83, 2004.

[2] Patrick Briest e Piotr Krysta. Buying cheap is expensive: hardness of non-parametric multi-product pricing. Em Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007.

Este trabalho investiga um novo problema integrado que envolve a localização de facilidades com o roteamento de veículos considerando restrições de empacotamento bidimensionais. Propõe-se um modelo de programação inteira que combina restrições do problema de localização de facilidades e do roteamento de veículos capacitados, além de algumas desigualdades válidas. Por fim, as restrições de empacotamento são tratadas como corte durante o processo de otimização.

Resumo

Resumo

Apresentamos problemas motivados pela seguinte questão levantada por Gallai em 1966: É verdade que em um grafo conexo existe um vértice comum a todos os seus caminhos mais longos? Sabe-se que a resposta a essa pergunta é negativa. Há porém, algumas classes de grafos para os quais a resposta é positiva. Apresentamos o caso em que se considera a intersecção de todos os caminhos mais longos, e também o caso em que se considera apenas um número fixo de caminhos mais longos. Outros problemas relacionados que continuam em aberto serão mencionados.

O número de cruzamento de um grafo é o número mínimo de cruzamentos entre pares de arestas com que se pode desenhar o grafo no plano. Um grafo é crítico em número de cruzamento se qualquer subgrafo próprio tem número de cruzamento menor. Nesta apresentação falaremos sobre se ser crítico é uma propiedade do grafo o pode-se "induzir" nele.

ResuUma decomposição \(D\) de um grafo \(G\) é um conjunto de subgrafos de \(G\) tal que cada aresta de \(G\) está em exatamente um elemento de \(D\). Kotzig provou que um grafo \(3\)-regular admite uma decomposição em caminhos de comprimento \(3\) se e somente se contém um emparelhamento perfeito. Este resultado foi generalizado para decomposição de grafos \(3m\)-regulares em caminhos de comprimento \(3\); e para decomposição de grafos \((2d+1)\)-regulares em d-biestrelas. Provamos recentemente que todo grafo \(m(2d+1)\)-regular G admite decomposição balanceada em \(d\)-biestrelas se e somente se \(G\) contém um emparelhamento perfeito. Apresentaremos um esboço da demonstração deste último resultado.

Dada uma coloração dos arcos de um grafo dirigido \(D\), dizemos que um vértice \(v\) é uma \emph{fonte monocromática} de \(D\) se, para todo \(w\in D\), existe um caminho monocromático de \(w\) a \(v\). Vamos discutir a seguinte conjectura, proposta em [B. Sands, N. Sauer, and R. Woodrow, On monochromatic paths in arc-coloured digraphs, J. Combin. Theory Ser. B 33 (1982), no. 3, 271–275.]: Seja \(T\) um torneio. É verdade que, para toda \(3\)-coloração dos arcos de \(T\) tal que \(T\) não contém triângulos direcionados multicoloridos, \(T\) possui uma fonte monocromática? Sabemos que todo torneio \(2\)-colorido contém uma fonte monocromática. Ademais, para todo \(n\geq 6\), existem torneios \(T_n\) com \(n\) vértices tal que existe uma \(4\)-coloração dos arcos de \(T_n\) de modo que \(T_n\) não contém fontes monocromáticas.

Vou definir a versão online do problema Steiner Tree Star, descrever um algoritmo para ele e mostrar que este é \(O(\log^2{n})\)-competitivo.

Recentemente, Aros-Vera et al. [1] introduziram uma formulação de Programação Linear Inteira Mista (PLIM) para o problema de "Multinomial Logit Facility Location" e consideraram sua aplicação na alocação de estacionamentos próximos a estações de trem/metrô e terminais de ônibus, na qual o objetivo é maximizar a quantidade de usuários do transporte coletivo. A função objetivo considera é não-linear e o trabalho de Aros-Vera et al. [1] mostra como é possível obter uma formulação linear para o problema.

Neste seminário, apresentaremos um resumo de parte do artigo de Aros-Vera et al. [1] e os resultados que obtivemos para este problema em colaboração com o Eduardo Moreno e o Wilfredo Yushimito, ambos da Universidad Adolfo Ibañez, Santiago, Chile. Apresentaremos uma melhoria na formulação de Aros-Vera et al., uma nova formulação e um algoritmo de branch-and-bound para o problema. Resultados computacionais mostram que em muitos casos nosso algoritmo é literalmente mil vezes mais rápido do que a formulação de Aros-Vera et al.

[1] (2013) p-Hub approach for the optimal park-and-ride facility location problem. Felipe Aros-Vera and Vladimir Marianov and John E. Mitchell. European Journal of Operational Research. DOI: 10.1016/j.ejor.2012.11.006

Resumo