Expander graphs are fundamental objects in theoretical computer science and mathematics. They have numerous applications in diverse fields such as algorithm design, complexity theory, coding theory, pseudorandomness, group theory, etc. The goal of this talk is to provide a brief introduction to these amazing objects and to serve as an invitation for further explorations. We will discuss an elegant construction of expander graphs known as the zig-zag product. Depending on time, we will also discuss recent developments of “higher-order” zig-zag.

In many real-world applications, precise problem data is not available to the decision maker. One way to handle this uncertainty is by using chance-constraints, where the probability that at least one constraint is violated is bounded above by some parameter. However, such an approach assumes that the decision maker has access to the true probability distribution which governs the data behavior. In order to weaken such an assumption, the literature defined distributionally robust chance-constrained programs (DRCCP). In this model, we have a set of distributions, called the ambiguity set, and the upper bound on the constraint violation probability should hold for all probability distributions in this ambiguity set. One common ambiguity set is based on a Wasserstein ball centered around an empirical distribution. In this talk, I will introduce all the previously mentioned concepts and discuss an approach to model DRCCP’s so that they can be solved with standard optimization softwares. Computational experiments show the advantages of using DRCCP’s over classical chance-constraints. This presentation is based on the work of Chen, Kuhn and Wiesemann which appeared this month in Operations Research.

O problema da árvore geradora de comunicação ótima (OCT) recebe um grafo com comprimentos não negativos nas arestas e um requerimento não negativo entre cada par de vértices; sendo o objetivo encontrar uma árvore geradora do grafo que minimize o custo de comunicação, que é dado pela soma entre cada par de vértices da distância que os separa na árvore multiplicada pelo requerimento entre eles. OCT é um problema NP-difícil e não admite FPTAS a menos que P=NP, mesmo quando considerados grafos métricos e requerimentos unitários entre todos os pares de vértices. Esta apresentação cobre os principais resultados obtidos para OCT durante o meu doutorado, cujo foco foi o estudo de diferentes casos particulares NP-difíceis do problema. Entre as variantes estudadas, foram introduzidas novas versões generalizando aquelas que foram abordadas previamente na literatura. Os resultados obtidos incluem PTAS para os problemas estudados quando considerados grafos métricos e uma 2-aproximação polinomial em grafos gerais, assim como provas de NP-dificuldade para as novas variantes introduzidas.

No Multiple Allocation k-Hub Center (MAkHC), temos um grafo G com pesos nas arestas, conjuntos de clientes C e terminais H, onde V(G) = C ∪ H, demandas D ⊆ C² e um inteiro k. Uma solução é um conjunto de terminais H’ ⊆ H de tamanho k tal que toda demanda (a, b) é satisfeita por um caminho que começa em a, passa por algum terminal de H’, e termina em b. O objetivo é minimizar o maior comprimento de um caminho. Este problema é uma generalização do k-Center, um famoso problema da área de localização. Neste seminário, exploramos a interseção das áreas de algoritmos de aproximação e algoritmos parametrizados. São apresentados resultados de dificuldade sobre o MAkHC, que são confrontados por uma (2 + ε)-aproximação parametrizada pela treewidth de G, usando técnicas de ambas as áreas.

We present an evolutionary algorithm for multi-objective optimization problems, based on the Biased Random-Key Genetic Algorithm (BRKGA) and on the Elitist Non-dominated Sorting Genetic Algorithm (NSGA-II). Computational experiments applied to the Multi-Objective Flexible Job Shop Scheduling Problem (MOFJJSP) compared our algorithm with other multi-objective meta-heuristics algorithms from the literature, namely the NSGA-II, the Non-dominated Sorting Particle Swarm Optimization (NSPSO), the Multi-Objective Evolutionary Algorithm by Decomposition with Differential Evolution (MOEA/D-DE), the Multi-objective Hypervolume-based Ant Colony Optimizer (MHACO), and the Improved Harmony Search (IHS). The results show that our methodology obtained competitive results with respect to the hypervolumes, the multiplicative epsilon indicator and the modified inverted generational distance from the obtained non-dominated fronts.

The mixed capacitated general routing problem (MCGRP) is concerned with the determination of the optimal vehicle routes to service a set of customers located at nodes and along edges or arcs on a mixed weighted graph representing a complete transportation network. Although MCGRP generalizes many other routing problems and yields better models for several practical problems such as newspaper delivery and urban waste collection, this is still an under-investigated problem. Furthermore, most of the studies have focused on the optimization of just one objective, that is, cost minimization. Keeping in mind the requirement of industries nowadays, MCGRP has been addressed to concurrently optimize two crucial objectives, namely, minimization of routing cost and route imbalance. To solve this bi-objective form of MCGRP, a multi-objective evolutionary algorithm (MOEA), coined as Memetic NSGA II, has been designed. In this talk, I will present the problem, solution algorithm and obtained results on benchmark instances.

Apresentamos o Positional Knapsack Problem (PKP) e mostramos que ele é NP-difícil, mas admite um Fully Polynomial-Time Approximation Scheme (FPTAS). Este problema é uma variante do clássico Knapsack Problem (KP) em que o valor de um item varia de acordo com a posição em que é adicionado. A mudança na valoração adiciona novas propriedades ao problema que não são válidas para o KP, já que o PKP não é uma generalização de KP. Para provar a NP-dificuldade, reduzimos uma variante do Partition Problem a uma instância cuidadosamente construída do PKP para recuperar algumas propriedades normalmente esperadas para variantes do Knapsack Problem. Nosso FPTAS é baseado em um algoritmo de programação dinâmica e usa uma nova abordagem de arredondamento recursivo, que é necessária uma vez que a função objetivo depende do valor e da posição de cada item.

The Least Cost Directed Perfect Awareness Problem (LDPAP) is a combinatorial optimization problem that models the spreading of information on social networks. In this problem, we seek to minimize the cost of recruiting seminal individuals that are sufficient to ascertain that a given news reaches everyone on a network, under certain dissemination restrictions. Using the fact that LDPAP is a generalization of the Perfect Awareness Problem, we obtain relevant results on the complexity of LDPAP as well as a bound for its objective function. We also introduce two integer linear programming formulations and a heuristic based on the metaheuristic GRASP.

A latin square is an n x n grid filled with n elements in such a way that no element occurs more than once in any row or column of the grid. The concept of latin squares was first mathematically defined and studied by Euler in the 17th century, and since then algebraic and combinatorial properties have been extensively investigated. Regarding the structure of latin squares, some natural questions may arise. Given a latin square with some cells left empty, is it possible to complete it? In negative case, how many cells can be filled without violating the latin square constraints? These questions refer respectively to the decidability of latin squares completion and the approximability of latin squares extension, We present some known results concerning these questions from a computational point of view. We show that deciding if a parital latin square is completable is NP-complete, and with respect to the approximability of latin squares extension, we present some approximation algorithms for the problem, namely a greedy algorithm, some matching based algorithms and a local search approach.