In this presentation we show the results from Buchbinder et al. FOCS 2012 paper. In this paper is considered the Unconstrained Sub modular Maximization problem in which it is given a non-negative sub modular function $f:2^{N} -> R^+$, and the objective is to find a subset $S\subseteq N$ maximizing $f(S)$. This is one of the most basic sub modular optimization problems, having a wide range of applications. Some well known problems captured by Unconstrained Sub modular Maximization include Max-Cut, Max-DiCut, and variants of Max-SAT and Maximum Facility Location.

The paper presents a simple randomized linear time algorithm achieving a tight approximation guarantee of $1/2$, that matches the known hardness result of Feige et al. The algorithm is based on an adaptation of the greedy approach which exploits certain symmetry properties of the problem. This method is particularly interesting, since it is known that the greedy algorithm fails to achieve any bounded approximation factor for the problem.

In this presentation we will present Valiant-Vazirani theorem and its extension for the probabilistic model.
We will start by proving the original result of Valiant and Vazirani ‘86, that reduces probabilistically a NP-complete problem to a problem in UP, complexity class in which there exists a single witness that leads acceptance of yes-instances. This implies that if it is possible to solve UP problems in polynomial time, then NP = RP.
Then, we will show how Aharonov et al ‘08 extended the result to MA, showing how to deal with pseudo-witnesses.
We will finish the talk presenting an open problem in this context, envolving perfect completeness of MA.

O número de cruzamentos de um grafo é o número mínimo de cruzamentos de arestas de um desenho plano de um grafo.
Nesta palestra, falaremos sobre as distintas técnicas utilizadas para obter informação do número de cruzamento. Falaremos sobre o número de cruzamento dos grafos bipartidos completos e dos grafos completos. Também apresentaremos algumas das distintas variantes existentes sobre o número de cruzamento.

Propõe-se um protocolo seguro combinando Funções Fisicamente não Clonáveis (PUFs) com protocolos de Acordo Autenticado de Chaves baseados em Senha (PAKE). O protocolo oferece autenticação mútua entre cliente e servidor e estabelece uma chave de sessão entre as partes autenticadas, características importantes que não foram encontradas simultaneamente na literatura de autenticação de transações. A combinação aprimora o estado da arte, garantindo que a chave de sessão esteja apenas disponível para detentores legítimos da PUF, sem a possibilidade de vazamento de segredos armazenados explicitamente; e também garante proteção contra ataques de dicionário sobre a senha de autenticação. O protocolo é seguro caso a saída da PUF seja imprevisível e permite ao cliente notificar o servidor em situações de emergência.

O trabalho está sendo desenvolvido em conjunto com a orientanda Amanda Resende no âmbito de projeto de cooperação entre Intel e Universidade de Brasília.

Conjectura de Albertson diz que se um grafo tem número cromático $k$ então o seu número de cruzamentos é maior ou igual o número de cruzamentos do grafo completo com $k$ vértices. Até o momento, esta conjectura foi provada para todos os grafo com número cromático menor ou igual a 18. Esta palestra tem como objetivo apresentar algumas técnicas utilizadas para provar resultados sobre a conjectura.

No Problema da Localizaçao de Instalações com Capacidades, são dados um conjunto de instalações $F$ e um conjunto de clientes $D$ em um espaço métrico. Cada instalação $i$ tem um custo de abertura $f_i$ e uma capacidade $u_i$ que especifica o número máximo de clientes que pode atender, cada cliente $j$ tem uma demanda $d_j$ e cada par cliente $j$ e instalaçao $i$ tem um custo $c_{ij}$ que corresponde à distância entre os mesmos. Desejamos abrir algumas instalaçoes do conjunto F de modo a atender a demanda dos clientes com o menor custo total possivel.

O artigo de Levi, Shmoys e Swamy[1] apresenta uma 5-aproximaçao para esse problema NP-dificil, no caso em que os custos de aberta $f_i = f$ para toda instalaçao $i$, arredondando a soluçao obtida relaxaçao do PL correspondente.

Referência(s):
[1] Levi, R., Shmoys, D., Swamy, C.: LP-based approximation algorithms for capacitated facility location. Mathematical Programming, Volume 131, Issue 1-2, pp 365-379 (2012).

Uma coloração total semiforte de um grafo simples $G$ é uma atribuição de cores aos vértices e às arestas de $G$ de modo que: (1) quaisquer dois vértices ou duas arestas adjacentes possuam cores distintas; (2) cada vértice tenha cor diferente das cores das arestas que nele incidem; e (3) para quaisquer dois vértices adjacentes $v_1$ e $v_2$, o conjunto das cores que colorem $v_1$ e suas arestas incidentes é distinto do conjunto das cores que colorem $v_2$ e suas arestas incidentes.

Em 2005, Zhang et al. conjeturaram que qualquer grafo simples $G$ admite uma coloração total semiforte com no máximo $D(G)+3$ cores, onde $D(G)$ é o grau máximo do grafo $G$. Essa conjetura é denominada Conjetura da Coloração Total Semiforte e continua aberta para grafos arbitrários. Neste seminário, será apresentada a validade desta conjetura para classes de grafos tais como: grafos equipartidos completos, grafos tripartidos e algumas famílias de grafos com $D(G)=3$.

Nos últimos anos, houve vários estudos sobre problemas que envolvem a defesa de um grafo contra ataques. Tais problemas têm sua origem nas antigas estratégias empregadas por Constantino para defender o extenso Império Romano. Em um destes problemas, que denominamos Conjunto Dominante Eterno, é preciso lidar com ataques que ocorrem nos vértices do grafo. Nesta apresentação, abordamos Conjunto Dominante Eterno para a classe dos grafos de intervalo próprios.

O Problema do Caixeiro Viajante é um dos mais fundamentais e mais estudados problemas em algoritmos de aproximação. Para o caso especial de métricas gráficas, Mömke e Svensson obtiveram um fator de aproximação de $\frac{14(\sqrt{2}−1)}{(12\sqrt{2}−13)} \approx 1.461$ para o TSP com métricas gráficas, bem como o fator $3-\sqrt{2}+\epsilon \approx 1.586 + \epsilon$ para o mais geral Travelling Salesman Path Problem (TSPP) com métricas gráficas. Marcin Mucha apresenta uma análise melhorada dessa abordagem, gerando um limite de $\frac{13}{9}$ sobre o fator de aproximação para o TSP, bem como um limite de $\frac{19}{12} + \epsilon$, para qualquer $\epsilon > 0$, para o TSPP.

We consider a general class of non-cooperative games related to combinatorial covering and facility location problems. A game is based on an integer programming formulation of the corresponding optimization problem, and each of the k players wants to satisfy a subset of the constraints. For that purpose, resources available in integer units must be bought, and their cost can be shared arbitrarily between players. We consider the existence and cost of exact and approximate pure-strategy Nash equilibria. In general, the prices of anarchy and stability are in Θ(k) and deciding the existence of a pure Nash equilibrium is NP-hard. We also present algorithms that compute simultaneously near-stable and near-optimal approximate Nash equilibria in polynomial time.

Dado um grafo $G$ o problema da árvore geradora com poucas ramificações é encontrar uma árvore geradora de $G$ com número mínimo de vértices com grau maior do que 2. Aplicações práticas do problema são encontradas por exemplo em projetos de redes de fibra ótica. Sabe-se que esse problema é NP-difícil. Apresentamos um algoritmo aproximado de Chimani e Spoerhase baseado em busca local com fator de aproximação de 6/11.

Neste seminário será apresentado o problema da Partição em Cliques Dominantes. Esse problema é uma variante do problema da Partição Dominante, cujo objetivo é encontrar uma partição do conjunto de vértices do grafo, de cardinalidade máxima, tal que que cada parte seja um conjunto dominante. No caso do problema da Partição em Cliques Dominantes é adicionada a restrição de que cada uma das partes também seja uma clique. Serão apresentados resultados para algumas classes de grafos, entre elas, a classe dos grafos bipartidos e subclasses de grafos obtidos pelas operações de produto direto e produto cartesiano de grafos.

Uma cadeia de DNA pode ser representada por uma sequência de pontos no espaço tridimensional, associando-se cada base (letra) a um vértice de um tetraedro. Essa sequência de pontos pode ser filtrada (suavizada) e interpolada, resultando em um curva tridimensional no interior do tetraedro. A forma dessa curva é relativamente robusta em relação a mutações pontuais e pequenas inserções ou deleções. Com filtragem adequada, a curva pode ser representada com um número de pontos bem menor que o número de bases na cadeia original, o que reduz o tempo e espaço necessários para a comparação de cadeias.

Este é um trabalho conjunto com Helena C. G. Leitão e Rafael F. V. Saracchini.

The two-dimensional knapsack problem with items that correspond to polygons with holes is studied, so an algorithm based on no-fit polygon computation is proposed. First, we discuss the use of no-fit polygon to get feasible positioning of items in the generated packing. Next, a hybrid heuristic, which combines GRASP with Simulated Annealing, is presented. For each initial greedy-randomized solution, a local search is executed to improve it, although the neighborhood of solutions with low occupancy ratio may be also investigated observing an acceptance probability function. In local search, operations to remove, include and change the position of items while maximizing the occupancy area are applied. Computational experiments showed the competitiveness of the algorithm, since recent results about this problem are improved.

Let us consider the doubly continuous Terrain Guarding Problem (TGP), in which we want to guard a 1.5D terrain with a minimum number of guards. The entire terrain has to be guarded and we may place guards anywhere on the terrain.

Our result is is a discretization, i.e., finite sets of guard candidate points G and witnesses (points to be guarded) W which allows us to solve the discrete version of the terrain guarding problem: We guard only the points in W using only the guard candidates in G and still obtain an optimal, feasible solution for the continuous version of the problem. Furthermore, we talk about an integer linear programming approach and an implementation aiming at exact solutions for the TGP.

CGAL, the Computational Geometry Algorithms Library, follows the exact geometric-computation (EGC) paradigm. A naive attempt could realize this by carrying out each and every arithmetic operation using an expensive unlimited-precision number type. However, only the discrete decisions in an algorithm, namely the predicates, must be correct. This is a significant relaxation from the naive concept of numerical exactness. This way it is possible to use fast inexact arithmetic (e.g. double-precision floating-point arithmetic), while analyzing the correctness. If the computation reaches a stage of uncertainty, the computation is redone using unlimited precision. In cases where such a state is never reached, expensive computation is avoided, while the result is still certified.

The talk will discuss different filtering solutions to avoid expensive exact arithmetic in most cases while still ensuring exactness of the algorithm. In CGAL, these solutions are encapsulated in classes that provide the basic geometric objects and operations, so called kernels. The goal is to understand the different options as selecting the right kernel can make a huge difference in performance.

Uma empresa que vende produtos precisa escolher os seus preços corretamente já que preços baixos podem levar a um lucro baixo e preços altos podem inibir a compra dos produtos. Por isso, uma área importante de estudo da economia é a de precificação de bens e serviços. Existem diversos modelos na literatura que abordam esse modelo. Um tal modelo é o Problema da Compra Máxima, onde temos $n$ produtos a serem vendidos e $m$ consumidores interessados. Cada consumidor $b$ acredita que um determinado produto $i$ tem valor $v(i,b) \geq 0$ e o vendedor deseja escolher um preço $p(i)$ para cada produto com o objetivo de maximizar o lucro. Nesse modelo, consideramos que cada consumidor $b$ irá comprar um produto $i$ com $p(i)$ máximo entre aqueles que satisfazem $p(i) \leq v(i,b)$, isto é, aqueles produtos que não são muito caros do ponto de vista do consumidor $b$.
Em particular, apresentaremos algoritmos de aproximação para versões do problema onde os produtos têm oferta limitada, isto é, cada produto pode ser vendido para no máximo um determinado número de consumidores. Tais resultados foram apresentados na conferência LATIN 2014 [1].

Referência(s):
[1] Fernandes C.G., Schouery R.C.S. Approximation Algorithms for the Max-Buying Problem with Limited Supply. Proceedings of the 11th Latin American Symposium on Theoretical Informatics (LATIN’2014). LNCS volume 8392, p. 707-718, 2014.

Dada uma permutação $\pi = (\pi_1 \pi_2 … \pi_n)$ dos inteiros de $1$ a $n$ e um conjunto de operações, nosso objetivo é encontrar a sequência mínima de tais operações que ordenam $\pi$, isto é, que transformam-na na permutação identidade $(1 2 \ldots n)$. Um dos problemas mais conhecidos é o Problema das Panquecas, no qual as operações permitidas são as reversões de prefixo, que invertem a ordem dos elementos de uma sequência $\pi_1 \ldots \pi_i$ de $\pi$. Neste seminário, apresentarei o Problema das Panquecas e problemas relacionados, bem como características desses problemas e algoritmos de aproximação para eles.

Uma superfície $S$ é um espaço topológico de Hausdorff compacto e conexo tal que todos os pontos de $S$ tem uma vizinhança homeomórfica a um disco aberto no plano. Exemplos de superfícies incluem a esfera, o plano projetivo, o toro e a garrafa de Klein. O número de cruzamentos de um grafo $G$ na superfície $S$ é o menor número de cruzamentos entre arestas dentre todos os desenhos de $G$ na superfície $S$. Neste seminário, darei uma breve introdução sobre o problema de desenhar grafos em superfícies arbitrárias. Em específico, tratarei sobre os avanços atuais na determinação do número de cruzamentos do grafo bipartido completo em superfícies arbitrárias.

Um $k$-fluxo inteiro para um grafo direcionado $D$ é uma associação de pesos inteiros do conjunto ${1, 2, \ldots, k-1}$ às arestas de $D$ de forma que em todo vértice $v$ a soma dos pesos das arestas que saem de $v$ é equilibrada pela soma dos pesos das arestas que entram em $v$. O estudo de fluxos inteiros em grafos, iniciado por William T. Tutte, surgiu como uma generalização para grafos não necessariamente planares do conceito de coloração de faces, o qual é restrito a grafos planares. É um assunto com uma surpreendente concentração de teoremas e equivalências simples e elegantes, daquelas que, segundo Paul Erdos, devem estar no “Livro de Deus” das demonstrações. Esse fato inspirou Daniel H. Younger a chamar este tópico, permeado de teoremas de natural beleza e preciosidade, de “As Minas Gerais da Teoria dos Grafos”. Neste seminário serão apresentados alguns desses belos teoremas.

Aplicações “Big Data” interativas, como por exemplo visualizações e mapas, jogos de computador e simulações, ou sistemas financeiros, estão se tornando cada vez mais importantes em nossa sociedade. Nessa palestra, descrevemos lições aprendidas durante a nossa pesquisa com essas aplicações. Primeiro, exploramos o desafio de selecionar dados para mapas de múltiplas escalas. Segundo, discutimos como lidar com latência quando implantamos essas aplicações em nuvens computacionais. Em ambos os casos, métodos de solução de problemas NP-difíceis estão no cerne das abordagens algorítmicas utilizadas para os problemas encontrados.
Bio resumida: Marcos Vaz Salles é professor assistente do Departamento de Informática (DIKU) da Universidade de Copenhague. Sua pesquisa objetiva o desenvolvimento de sistemas de gerência de dados declarativos e eficientes para novas aplicações, unindo técnicas de gerência de dados e engenharia de software. Seu trabalho recente está focado em bancos de dados de memória principal bem como gerência de dados espaciais, e é motivado por aplicações como visualizações geográficas, simulações comportamentais, jogos de computador, e sistemas financeiros. Marcos fez o seu pós-doutorado na universidade de Cornell, EUA, seu doutorado na ETH Zurich, Suíça, seu mestrado na PUC-Rio, Brasil, e sua graduação no Instituto de Computação da UNICAMP, Brasil.

Uma partição em caminhos de um digrafo é uma partição do conjunto de vértices deste em caminhos dirigidos. Dada uma métrica sobre as partições em caminhos, chamada $k$-norma, dizemos que uma partição é $k$-ótima se ela possui a menor $k$-norma dentre todas as partições possíveis. Em 1982, Claude Berge conjecturou que para toda partição $k$-ótima existe um conjunto de $k$ conjuntos independentes disjuntos que interceptam, de certa forma, o maior número possível de caminhos desta partição. Tal conjectura ficou conhecida como a Conjectura de Berge Sobre a Partição em Caminhos. Neste seminário, apresentaremos tal conjectura e alguns problemas/conjecturas relacionados.

Nessa apresentação será abordada uma nova variante do Problema de Roteamento de Veículos (VRP), denominada Problema de Roteamento Dominante de Veículos (DVRP). Essa variante consiste na composição de dois problemas NP-difíceis: o VRP e o Problema do Conjunto Dominante. Brevemente, o objetivo do DVRP consiste em encontrar um conjunto de rotas de mínimo custo em um grafo não-direcionado, partindo de um nó depósito. As rotas são trafegadas por uma frota de veículos com capacidade limitada atendendo a demanda de um conjunto dominante de nós (clientes). A motivação do estudo do DVRP consiste em sua aplicação prática para empresas de distribuição de energia, gás ou água; em particular, no processo de definição das rotas para a leitura dos consumos desses serviços. Serão discutidas formulações matemáticas para o DVRP, que formarão a base de uma metodologia de solução exata. Também será discutida uma abordagem de solução por metaheurísticas, dado a elevada complexidade da solução exata do DVRP. Finalmente, serão apresentados resultados preliminares de experimentos computacionais para o DVRP, a partir de formulações de PLI para o VRP e para o Problema do Conjunto Dominante.

Seja $f(k)$ o menor inteiro tal que todo digrafo $f(k)$-cromático contém todas as árvores orientadas de ordem $k$. Burr conjecturou que $f(k)=2k-2$, i.e. toda árvore orientada de ordem $k$ é $(2k-2)$-universal. Burr também provou que cada digrafo $(8k-7)$-cromático contém todas as árvores antidirecionadas de ordem $k$. Neste seminário, apresentarei como os dois limites foram melhorados, mostrando que $f(k) \leq \frac{k^2}{2} - \frac{k}{2} +1$ e que toda árvore antidirecionada de ordem $k$ está contida em digrafo $(5k-9)$-cromático. A conjectura é provada para árvores antidirecionadas de diâmetro 3.

The Connected Facility Location (CFL) is a network design problem that arises from a combination of the Uncapacitated Facility Location (FL) and the Steiner Tree (ST) problems. The Online Connected Facility Location problem (OCFL) is an online version of the CFL. In this presentation we describe a randomized algorithm for the OCFL and show that it is $O(\log{n})$-competitive. Since there is a lower bound of $\Omega(\log{n})$ for this problem, this result achieves the best possible competitive ratio, asymptotically.

O problema da árvore geradora com muitas folhas é um problema NP-difícil que consiste em encontrar uma árvore geradora de um grafo G com número máximo de folhas. Nesta seminário, apresentaremos um modelo de programação linear inteira mista baseado em fluxo para esse problema e alguns resultados preliminares que mostram que o modelo proposto é competitivo com outras abordagens da literatura.

Problemas de otimização são denominados offline quando se tem conhecimento de toda a entrada, e não são impostas restrições de causalidade na estrutura da solução. Em contraposição, são definidos na literatura modelos de otimização denominados dinâmicos, nos quais o conhecimento sobre a entrada é limitado e/ou são impostas restrições de causalidade entre soluções parciais. Exemplos desses modelos incluem a computação online, a otimização estocástica e, mais recentemente, a otimização incremental e a otimização universal.
Neste seminário será apresentado o modelo de otimização incremental, conforme definido por Alexa Sharp e Jeff Hartline em suas teses de doutorado (Cornell, 2007 e 2008, respectivamente). Serão discutidos a estrutura desse modelo, suas aplicações, e alguns resultados genéricos para problemas de cobertura. Será discutida também, em especial, a relação com o modelo de computação online, para o qual a otimização incremental provê um entendimento mais completo sobre a complexidade dos problemas.

A spline is a function defined by parts. Namely, the domain of interest is divided into a mesh with a finite number $n$ of cells, and within each cell the function is defined by a separate mathematical formula, such as a polynomial of bounded degree. Splines are widely used in numerical computing, since they can be evaluated very quickly, and can approximate complicated functions to arbitrary accuracy, even when the accuracy requirement is not uniform over the domain.
In many applications, the splines are required to satisfy some continuity or other constraints between adjacent parts. It is often the case that the space $S$ of all valid (constrained) splines is much smaller than the space $U$ of all unconstrained splines with the same mesh and type. It is therefore advisable to precompute a basis for the space $S$; that is, a minimal list $B[1..m]$ of splines from $S$ that can generate all the valid splines by linear combination. Once the basis $B$ is chosen, each valid spline $s$ in $S$ can be represented by the list of its $m$ coefficients $a[1..m]$ relative to $B$.
To evaluate a spline $s$, given in that representation, at some domain point $x$, one should first locate the cell $C$ of the mesh that contains $x$, then compute the polynomial $P = \sum k : a[k](B[k]|C)$, and then evaluate $P$ at $x$. Note that one needs to include in the sum only those elements of $B$ that are not identically zero in the cell $C$. Therefore, it is desirable to choose the elements of $B$ so that they have *compact support, that is, non-zero only in a small number of cells. Indeed, it is desirable to minimize the weight of $B$, defined as the number of cells where each element is not zero, summed over all elements.
Traditionally, the search for compact bases is done by hand, case by case, by constructions that are specific to each type of meshand degree. For many cases of practical interest, the existence of a compact basis is not known, or it is not known whether a known compact basis is optimal.
Surprisingly, there is an algorithm that will find a minimal-weight basis for any constrained spline space $S$, that runs in polynomial time when a compact basis exists. The algorithm relies on the fact that the constrained splines define a matroid, and therefore the minimum-weight basis can be found by the classical greedy algorithm of Edmonds.
The algorithm requires enumerating every subset $Z$ of cells that is connected in the dual graph of the mesh, in order of increasing cardinality, and enumerating the elements of the basis whose support is $Z$ and are not combinations of previously found elements. Although the number of subsets $Z$ of a fixed cardinality $z$ is proportional to $n^z$, the number of connected subsets is only $O(n)$, with a constant factor that depends only on $z$ and the maximum degree of the dual graph. The algorithm is fast enough to be useful in practical applications.
These results are part of the PhD thesis project of Ana Paula Malheiro.

Nesta palestra trataremos algumas das ideias discutidas por Yu-Chang Liang, Tsai-Lien Wong e Xuding Zhu no artigo: “Anti-magic labering of trees”, onde uma rotulação anti-mágica de um grafo $G$ é tratado como sendo uma correspondência de um pra um, entre $E(G)$ e ${1, 2, 3,\ldots,|E|}$, tal que a soma dos rótulos atribuídos à arestas incidentes para um determinado vértice seja diferente. Hartsfield e Ringel conjecturaram que toda árvore que não é $K_2$ tem uma rotulação anti mágica. Kaplan, Lev e Roditty provaram que se uma árvore $T$ tem no máximo grau 2, então ele é anti-mágica.

Nesta apresentação sera abordado o problema de Árvores de Steiner Estocásticas de duas fases SSTP, o qual faz parte dos problema que pertencem ao 11th DIMACS challenge.

No SSTP existe um numero finito de cenários, nos quais o conjunto de terminais e os custos das arestas são sujeitos à incerteza. No primeiro estágio, temos a informação probabilística em termos de possíveis cenários. Para casa cenário é dado um conjunto de terminais, o custo das arestas para aquele cenário, e a probabilidade do mesmo acontecer. O objetivo é escolher arestas para serem compradas no primeiro estágio que minimizem o custo esperado da solução total.

Para tal problema propomos uma metodologia heurística que utiliza BRKGA, com população inicial criada a partir de uma heurística construtiva, baseada na informação do custo reduzido das arestas. Tal metodologia foi largamente testada com instâncias da literatura e do repositório DIMACS, o qual inclui instâncias grandes, com 20 vezes mais cenários que as testadas previamente. Os resultados mostram que o BRKGA obteve soluções próximas da ótima, para as instâncias da literatura, e obteve redução de custo considerável para instâncias do DIMACS.

The class QMA plays a fundamental role in quantum complexity theory and it has found surprising connections to condensed matter physics and in particular in the study of the minimum energy of quantum systems. In this paper, we further investigate the class QMA and its related class QCMA by asking what makes quantum witnesses potentially more powerful than classical ones. We provide a definition of a new class, SQMA, where we restrict the possible quantum witnesses to the “simpler” subset states, i.e. a uniform superposition over the elements of a subset of n-bit strings. Surprisingly, we prove that this class is equal to QMA, hence providing a new characterisation of the class QMA. We also prove the analogous result for QMA(2) and describe a new complete problem for QMA and a stronger lower bound for the class QMA_1.