O Problema do Ciclo Dominante (DCP) é uma generalização de dois problemas NP-difíceis: o Problema do Caixeiro Viajante (TSP) e o Problema do Conjunto $k$-Dominante ($k$-DSP). Neste seminário, apresentaremos uma formulação de programação linear inteira e um algoritmo Branch-and-Cut para o DCP, com duas diferentes estratégias de separação para uma família de desigualdades válidas. As metodologias foram testadas em um conjunto representativo de instâncias geradas de forma aleatória e em uma instância real extraída da cidade de Campinas.

An attractive way to reduce losses in electric power distribution networks is addressing the network reconfiguration problem, which should give a topology for the primary distribution network that minimizes the total losses due to the electrical resistances in the lines and complementary equipment’s (technical losses). Distributed energy resources and additional innovations associated to smart grids allow enhancing the benefits of finding better network topologies. On the other hand, the integration of renewable energy sources with variable random outputs requires expanding the perspective in modeling the network reconfiguration problem and in the shaping of appropriate solution techniques. These issues are the object of this paper. The main new features of the problem are explored with a maquette designed to highlight the consequences of random generation sources in the networks. Following, the paper proposes a formulation for the problem that explicitly considers random energy sources. A state of the art genetic algorithm build under the biased random-key evolution framework (BRKGA) is developed to address this hard combinatorial optimization problem. Case studies with benchmark networks put into perspective the proposed methodology. Results show that random energy values should be explicitly modeled in contemporary approaches to the network reconfiguration problem. This presentation provides the grounds for addressing this new problem and points to additional research paths in the area.

This work proposes a novel many objective optimization method that globally finds a set of efficient solutions, also known as Pareto-optimal solutions, by automatically formulating and solving a sequence of weighted problems. The approach is called MONISE (Many-Objective NISE), because it represents an extension of the well-known non-inferior set estimation (NISE) algorithm, which was originally conceived to deal with two-dimensional objective spaces. Supported by theoretical proofs, we investigated the nice properties of NISE algorithm in two dimensions, as well as it struggles in more than two dimensions. Built over a new perspective of weighted sum method, the proposal is conceived to operate in more than two dimensions, thus properly supporting many objectives. Experimental results are used to validate the proposal and have indicated that MONISE is competitive both in terms of computational cost and considering the overall quality of the non-inferior set, measured by the hypervolume.

Search is one of the most useful procedures employed in numerous situations such as optimization, machine learning, information processing and retrieval. The talk introduces participatory search, a class of population-based search algorithms constructed upon the participatory learning paradigm. Participatory search relies on search mechanisms that progress forming pools of compatible individuals. The individual that is the most compatible with the best individual is always kept in the current population. Random immigrants are added to complete the population at each algorithm step. Different types of recombination are possible. The first is a convex combination, arithmetic-like recombination modulated by the compatibility between individuals. The second is a recombination mechanism based on selective transfer. Mutation is an instance of differential variation modulated by compatibility between selected and recombined individuals. The instance of the algorithm that uses arithmetic recombiation followed by mutation is evaluated using ten benchmark real-valued optimization problems and its performance is compared against population-based optimization algorithms representative of the current state of the art. The participatory search algorithm is also evaluated using a suite of twenty eight benchmark functions of a recent evolutionary, real-valued optimization competition, to compare its performance against the competition winners. Computational results suggest that participatory search algorithm performs best amongst the algorithms evaluated.

Resource allocation problems are a family of problems in which resources must be selected to satisfy given demands. This paper focuses on the two-stage stochastic generalization of resource allocation problems where future demands are expressed in a finite number of possible scenarios. The goal is to select cost effective resources to be acquired in the present time (first stage), and to implement a complete solution for each scenario (second stage), while minimizing the total expected cost of the choices in both stages.

We propose an evolutionary framework for solving general two-stage stochastic resource allocation problems. In each iteration of our framework, a local search algorithm selects resources to be acquired in the first stage. A genetic metaheuristic then completes the solutions for each scenario and relevant information is passed onto the next iteration, thereby supporting the acquisition of promising resources in the following first stage. Experimentation on numerous instances of the two-stage stochastic Steiner tree problem suggests that our evolutionary framework is powerful enough to address large instances of a wide variety of two-stage stochastic resource allocation problems.

Propomos uma discussão informal sobre análise experimental de algoritmos, motivada pela pergunta: “Como conhecimentos de análise teórica de algoritmos podem nos ajudar com experimentação prática?”. Usaremos como guia o artigo de David Johnson [1], que relata experiências e lições aprendidas durante mais de uma década trabalhando nesta área. Iremos apresentar 10 princípios gerais, que de acordo com Johnson, devem guiar a escrita de trabalhos experimentais. Estes princípios serão desenvolvidos a partir da discussão de diversos Pitfalls (tentações e práticas comuns que podem levar a perdas de tempo substanciais) e Pet Peeves (práticas comuns que são particularmente equivocadas).

Referência(s):
[1] Johnson, David S. “A theoretician’s guide to the experimental analysis of algorithms.” Data structures, near neighbor searches, and methodology: fifth and sixth DIMACS implementation challenges 59 (2002): 215-250.

Os modelos probabilísticos de uma linguagem (MPL) são modelos matemáticos onde é definida uma função de probabilidade que calcula a probabilidade de ocorrência de uma cadeia em uma linguagem. Os parâmetros de um MPL, que são as probabilidades de uma cadeia, são aprendidos a partir de uma base de dados (amostras de cadeias) pertencentes à linguagem. Uma vez obtidas as probabilidades, ou seja, um modelo da linguagem, existe uma medida para comparar quanto o modelo obtido representa a linguagem em estudo. Esta medida é denominada perplexidade por palavra. O modelo de linguagem probabilístico que propomos estimar, está baseado nas gramáticas probabilísticas livres do contexto. O método clássico para estimar os parâmetros de um MPL (Inside-Outside) demanda uma grande quantidade de tempo, tornando-o inviável para aplicações complexas. Esta apresentação irá abordar o problema de estimar os parâmetros de um MPL usando métodos de pontos interiores, obtendo bons resultados em termos de tempo de processamento, número de iterações até obter convergência e perplexidade por palavra.

The capacitated arc routing problem (CARP) is an important combinatorial optimization problem that has been extensively studied in the past decades. In summary, the objective is to optimize routes that service demands located in the edges of a graph, given a fleet of homogeneous vehicles with limited capacity that starts and ends its routes at a specific node (depot). This work proposes a new path-scanning heuristic for the CARP which introduces a novel efficiency-based rule to select more promising edges to service. Computational experiments conducted on a set of benchmark instances reveal that the proposed heuristic substantially outperformed all previous path-scanning heuristics from literature.

O Problema de Transporte Multimodal (PTM) consiste em encontrar a melhor rota entre dois pontos considerando uma rede que possua mais de um meio de transporte. Para determinar qual é a melhor rota, pode-se utilizar diversos critérios. Neste trabalho, considera-se dois critérios conflitantes: o custo financeiro e o tempo de viagem. Devido ao conflito entre os objetivos, é necessário utilizar conceitos de Otimização Multiobjetivo para resolução desse problema. A apresentação versará sobre esses conceitos aplicados em algoritmos exatos de caminho mínimo e em um algoritmo heurístico. Após o processo de otimização, aplicou-se um Modelo de Tomada de Decisão Multi-critério sobre o conjunto de soluções com o objetivo de refiná-las e ordená-las para uma melhor apresentação para o usuário. Esses métodos foram submetidos a experimentos computacionais e a partir desses resultados será apresentada uma análise comparativa dos métodos.

O Problema do Brigadista em Grafos (FFP do inglês The Firefighter Problem) é um modelo determinístico e em tempo discreto para simular a propagação e contenção de incêndios em grafos. Ele pode ser descrito da seguinte forma. Na entrada, é dado um inteiro $D$ representando a quantidade de brigadistas disponíveis, um grafo não direcionado e não ponderado $G = (V,E)$ e um subconjunto de vértices $B$ de $V$, os focos de incêndio. Então, inicia-se nos elementos de $B$ um processo iterativo de propagação e contenção de fogo através dos vértices de $G$, em rodadas discretas, o qual termina quando não existem mais vértices que possam ser queimados, ou seja, quando o fogo está contido. O objetivo ao resolver o FFP é maximizar o número de vértices não queimados quando o fogo é contido, com a restrição de que no máximo $D$ vértices podem ser protegidos contra o fogo por rodada.

Nessa apresentação serão expostos os principais resultados e metodologias de um estudo computacional do FFP realizado durante meu mestrado sob orientação dos Profs. Cid Carvalho de Souza e Pedro Jussieu de Rezende. Primeiramente, apresentamos melhorias feitas na primeira formulação PLI proposta para o FFP através de técnicas de preprocessamento e agregação de restrições. Em seguida, introduzimos uma nova matheurística para o FFP, uma abordagem que se baseia na interoperação entre meta-heurísticas e programação matemática. Experimentos foram conduzidos em um benchmark público tanto para configuração de parâmetros quanto para análise de desempenho, através de comparação dos resultados obtidos com aqueles publicados anteriormente. Com respeito às modificações no modelo PLI, um speedup de aproximadamente 2 em média foi alcançado. Com relação à matheurística, através de uma análise estatística rigorosa, verificamos que existe diferença estatisticamente significativa entre nossa estratégia e as demais, ao mesmo tempo que nossa matheurística conseguiu resultados melhores na maioria das instâncias.

Também será discutido, de modo geral, o uso de testes estatísticos para análise comparativa de resultados de múltiplos métodos em várias instâncias e como tais testes podem contribuir para as conclusões de um trabalho experimental.

In many scenarios in the real world, it is common to have people joining together to achieve shared and non-shared goals. As a team, they may achieve goals that otherwise it would be very difficult to accomplish. And they may share resources and payoffs for acting this way. This group structure is usually called a coalition. This concept is also usual in policy, where politicians with similar ideology group themselves in parties so they can have more power and influence. Another example is that in social life, where people arrange themselves into friendship groups considering similarities and other criteria that lead them to appreciate each other.

Hedonic games are a sub-class of coalition formation games with non-transferable utility. In such games, each agent has a (weak) preference order over all possible coalition that she can form with other agents. An agent has a hedonic preference if she only cares about the agents in her coalition. She does not care or is not influenced by the composition of the other coalitions. In the current model of hedonic games, a game outcome is a partition of agents.

This presentation introduces the subject by giving a formal definition of hedonic games and it presents results regarding stable outcomes.

Neste seminário apresentamos o problema de car-sharing proposto por Böhmová et. al [1], no qual $n$ clientes apresentam suas demandas de alocação de veículos com devoluções flexíveis (retirar um veículo em um pátio $A$ no momento $t_A$ e devolvê-lo em um pátio $B$ no tempo $t_B$). O objetivo é atribuir os veículos de modo a maximizar o número de clientes satisfeitos e um cliente é dito satisfeito se todas as suas demandas de alocação de veículos são atendidas. Na apresentação iremos mostrar alguns dos resultados obtidos pelos autores.

Referência(s):
[1] Böhmová et. al. Scheduling Transfers of Resourcesover Time: Towards Car-Sharing with Flexible Drop-Offs, pages 220–234. SpringerBerlin Heidelberg, 2016.

Neste seminário apresentaremos o problema MAXSPACE, proposto por Adler et. al [1]. Nesse problema desejamos dispor um conjunto $A$ de propagandas em um retângulo $B$ e temos $N$ unidades de tempo, chamadas slots, sendo que, em cada unidade de tempo, as propagandas do slot correspondente são exibidas em $B$. Todas as propagandas possuem a largura de um slot e cada propaganda $A_i$ possui uma altura e uma frequência, respectivamente, $s_i$ e $w_i$. A altura da propaganda $A_i$ representa o espaço que $A_i$ ocupa em um slot e a frequência define o número de slots em que $A_i$ deve aparecer. Um limite superior $S$ é especificado para a altura de $B$, dessa forma, nenhum slot pode exceder a altura máxima $S$.

Uma solução viável para o MAXSPACE consiste em um subconjunto $A’$ de $A$ tal que, para todo $A_i$ em $A’$, exatamente $w_i$ cópias de $A_i$ foram adicionadas aos slots, de forma que nenhum slot recebeu mais de uma cópia de $A_i$ e nenhum slot excedeu a altura máxima $S$. O objetivo do MAXSPACE é maximizar o lucro, dado pelo somatório de $s_i \cdot w_i$, para cada propaganda $A_i \in A’$, isso é, o lucro associado à propaganda é a sua altura multiplicada pela sua frequência. Na apresentação iremos mostrar alguns dos resultados existentes na literatura para esse problema.

Referência(s):
[1] Adler, M., Gibbons, P. B., and Matias, Y.(2002). Scheduling space-sharing for inter-net advertising. Proceedings of Journal of Scheduling, 5(2):103–119.

The number of connected cars has increased over the past years, and they became an important component of Internet-of-Things. Such vehicles use the cellular networks for several activities, and among them, the Firmware Over-The-Air updates could be potentially challenging to the network. With millions of connected cars expected to be deployed over the next years, it is essential to understand their impact on cellular networks, as much as create schedules for such downloads. We present a new scheduling model that accommodates the constraints for such scenario, which usually does not appear in other scheduling problems in the literature, and comment on the peculiarities of such solution.

We also discuss briefly, few other optimization problems that have challenged us currently. In the first problem, we want to schedule changes in several physical and virtual elements in the network and the challenges in such scheduling (change management optimization). In the second problem, we want to deploy fixed wireless phones to reduce the cost of the leasing and operation utility poles for copper wire drops, following the regulations of each state.

Dado um grafo $G = (V, E)$, uma rotulação própria de $G$ é um par $(π, c_π)$ onde $π:S \rightarrow {1, 2, \ldots, k}$ é uma atribuição de rótulos numéricos a um conjunto $S$ de elementos do grafo, que podem ser seus vértices, arestas ou ambos, e $c_π$ é uma coloração própria de vértices obtida por meio de funções matemáticas sobre os elementos rotulados. Neste seminário, abordamos a $k$-rotulação de vértices por gap, uma rotulação própria onde a cor de cada vértice é induzida pela maior diferença entre os rótulos dos seus vizinhos (vértices de grau um e vértices isolados são tratados separadamente). Introduzida por Dehghan, Sadeghi e Ahadi em 2013, os autores estudaram a complexidade computacional de problemas de decisão associados à $k$-rotulação de vértices por gap (entre outras). Em particular, eles mostraram que decidir se um grafo bipartido admite uma 2-rotulação de vértices por gap é um problema NP-completo. Entretanto, para algumas subclasses de grafos bipartidos, este mesmo problema de decisão pode ser resolvido em tempo polinomial. Neste seminário, apresentamos alguns avanços sobre a 2-rotulação de vértices por gap de grafos bipartidos, demonstrando que o problema de decisão permanece NP-completo para grafos subcúbicos bipartidos.

Given a simple graph $G=(V(G),E(G))$ and a subset of real numbers $L$, an $L$-edge-labelling of $G$ is a function $f:E(G) \rightarrow L$. Given an $L$-edge-labelling of $G$, we define the colour $C(v)$ of a vertex $v$ of $G$ as the sum of the labels of its incident edges. We say that the pair $(f,C)$ is a neighbour-distinguishing $L$-edge-labelling of $G$ if $f$ is an $L$-edge-labelling of $G$ and $C(u)$ is different from $C(v)$, for any two adjacent vertices $u$ and $v$ of $G$. In 2004, Karonski, Luczak and Thomason [1] posed an interesting conjecture which states that every connected simple graph with at least three vertices has a neighbour-distinguishing ${1,2,3}$-edge-labelling. This conjecture became known as the $1,2,3$ Conjecture and, although it has been investigated by some authors, it remains widely open. Motivated by the $1,2,3$ Conjecture, some authors have investigated neighbour-distinguishing $L$-edge-labellings in the broader context in which the set of labels $L$ comprises not only positive integers but any real numbers. Let $a,b,c$ be three distinct positive real numbers. In this seminar, we present some known results on the $1,2,3$ Conjecture as well as new results on neighbour-distinguishing ${a,b,c}$-edge-labellings of three families of graphs: the split graphs, regular cobipartite graphs and flower snarks.

Reference(s):
[1] M. Karonski, T. Luczak, A. Thomason. Edge weights and vertex colours. Journal of Combinatorial Theory, Series B 91(1), 151-157 (2004).

An edge-coloring is an assignment of colors to the edges of the graph such that any two adjacent edges receive different colors. The chromatic index of a graph $G$ is the smallest number of colors such that $G$ has an edge-coloring. Clearly, the lower bound for the chromatic index is the degree of the vertex of higher degree, denoted by $\Delta(G)$. In 1964, Vizing proved that chromatic index is $\Delta(G)$ or $\Delta(G) + 1$. The Classification Problem is to determine if the chromatic index is $\Delta(G)$ (Class 1) or the chromatic index is $\Delta(G) + 1$ (Class 2). It is well-known that the Classification Problem is an NP-Complete problem. A graph $G$ is a split graph if its vertices can be partitioned into two sets, a clique and a stable set. A graph $G$ is a comparability graph if it admits a transitive orientation of its edges. A split-comparability graph is a split graph that is also a comparability graph. In this presentation we will see the result of the Classification Problem in this graph class. This result was obtained in my master’s research [1].

Reference(s):
[1] Jadder Bismarck de Sousa Cruz. Coloração de Arestas em Grafos Split-Comparabilidade. Master’s thesis, Federal University of São Carlos, 2017.

No Problema de Localização e Alocação de Terminais, a entrada é um espaço métrico composto por clientes, localidades e um conjunto de pares de clientes; uma solução é um subconjunto das localidades, onde serão abertos terminais, e uma atribuição de cada par de clientes à uma rota, que começa no primeiro cliente, passando em um ou dois terminais, e terminando no segundo cliente. O objetivo é encontrar uma solução que minimize o tamanho de todas as rotas somado com o custo de abertura de terminais. Os algoritmos de aproximação da literatura consideram apenas o caso em que o conjunto de terminais abertos é dado como parte da entrada, e o problema se torna atribuir clientes aos terminais; ou então quando o espaço é definido em classes especiais de grafos. Neste trabalho, apresentamos o primeiro algoritmo de aproximação com fator constante para o problema de, simultaneamente, escolher localidades para abrir terminais e atribuir clientes à estes.
A primeira parte do trabalho cria algoritmos de aproximação para diversas variantes do problema. A estratégia principal é reduzir os problemas de localização e alocação de terminais aos problemas clássicos de localidades, como o problema de localização de instalações e o problema das k-medianas. A redução transforma uma instância de localização e alocação de terminais em uma instância de um destes problemas, que então é resolvida usando conhecidos algoritmos de aproximação. A saída do algoritmo induz uma solução para o problema original, com uma perda constante no fator de aproximação.
Na segunda parte, o foco é o Problema de Localização e Alocação Única de Terminais (SAHLP), que é uma variação em que cada cliente deve estar conectado a apenas um terminal, além de não haver limite na quantidade de terminais abertos. A principal contribuição é um algoritmo 2.48-aproximado para o SAHLP, baseado em arredondamento de uma nova formulação de programa linear para o problema. O algoritmo é composto por duas fases: na primeira, a solução fracionária é escalada e um subconjunto de terminais é aberto, e na segunda, atribuímos clientes aos terminais abertos. A primeira fase segue o formato padrão de filtering para problemas de localidades. A segunda, no entanto, exigiu o desenvolvimento de novas ideias e é baseada em múltiplos critérios para realizar a atribuição. A principal técnica atribui cada cliente ao terminal aberto mais próximo, se este estiver em sua vizinhança; caso contrário, o cliente se conecta ao terminal que melhor balanceia múltiplos custos, relacionados à distância entre eles.

Inicialmente será feita uma breve introdução à Combinatória Extremal, explicando que tipos de problemas são estudados nessa área. Em um segundo momento, analisamos uma conjectura proposta por Bal e DeBiasio [1] a respeito de funções limiares para a seguinte propriedade tipo Ramsey: em toda $k$-coloração do conjunto das arestas de um grafo $G$, existem $k$ árvores monocromáticas que particionam todo o conjunto de vértices de $G$. Mais precisamente, determinamos a função limiar para essa propriedade para duas cores. Este trabalho foi feito em conjunto com Yoshiharu Kohayakawa e Mathias Schacht.

Referência(s):
[1] Deepak Bal and Louis DeBiasio. Partitioning Random Graphs into Monochromatic Components. Electron J Combin 24(1) (2017), #P1.18.

Calcular a distância evolucionária entre espécies é um problema importante da área de Biologia Computacional. Em várias abordagens, o cálculo dessa distância considera apenas rearranjos de genomas, os quais são conjuntos de mutações que alteram grandes trechos do genoma de um organismo. Assumindo que o genoma não possui genes duplicados, podemos representá-los como permutações de inteiros, em que cada elemento corresponde a um bloco conservado (região de alta similaridade entre os genomas comparados) e o sinal de cada elemento corresponde a orientação desse bloco. Ao usar permutações, o problema de transformar um genoma em outro é equivalente ao da ordenação de permutações por operações de rearranjo. A abordagem mais comum desse problema considera que todas as operações tem o mesmo custo e, assim, o objetivo é encontrar uma sequência mínima de operações que ordene a permutação. Entretanto, estudos indicam que algumas operações de rearranjo tem maior probabilidade de acontecer do que outras, fazendo com que abordagens em que operações possuem custos diferentes sejam mais realistas. Nas abordagens ponderadas, o objetivo é encontrar a sequência que ordena a permutação, tal que a soma dos custos dos rearranjos dessa sequência seja mínimo. Neste trabalho, apresentamos algoritmos de aproximação para uma nova versão do problema da ordenação de permutações por operações ponderadas, em que a função de custo de uma operação corresponde à quantidade de fragmentações que a operação causa no genoma [1].

Referência(s):
[1] Alexsandro Oliveira Alexandrino, Carla Negri Lintzmayer, and Zanoni Dias. Approximation Algorithms for Sorting Permutations by Fragmentation-Weighted Operations. In: 5th International Conference on Algorithms for Computational Biology (AlCoB’2018). LNCS volume 10849, pages 53-64, 2018.

Problemas de otimização combinatória muitas vezes podem ser resolvidos de forma eficiente a partir de modelos de programação linear inteira (PLI). O número de variáveis em um modelo de PLI está diretamente relacionado à complexidade de sua resolução. Alguns modelos apresentam um número exponencial de variáveis, com relação a entrada do problema, o que pode tornar sua resolução inviável. Em 1961, Gilmore e Gomory [1] propuseram um algoritmo para a resolução de um modelo com um número exponencial de variáveis. Desde então, esse algoritmo, chamado de algoritmo de geração de colunas, vem sido utilizado com frequência na literatura para a resolução de diferentes problemas de otimização combinatória. Esse seminário apresenta uma introdução ao algoritmo de geração de colunas.

Referência(s):
[1] Paul Carl Gilmore and Ralph Edward Gomory. A Linear Programming Approach to the Cutting-Stock Problem. Operations Research, volume 9(6), pages 849-859, 1961.

In Steiner Tree Problem (STP), we are are given a graph $G = (V,E)$ and an edge cost function $c$ and we are asked to find a cheapest tree $S$ that spans a distinguished set of vertices known as terminals. In this seminar we present a very simple proof for a randomized ($1.55+\epsilon$)-approximation algorithm, which matches the prior best approximation known for the problem.

Reference(s):
[1] Deeparnab Chakrabarty, Jochen Könemann, and David Pritchard. Integrality gap of the hypergraphic relaxation of Steiner trees: A short proof of a 1.55 upper bound. Operations Research Letters, volume 38(6), pages 567-570, 2010.

In this seminar, some of the main results of [1] will be presented. The problem that was studied in the paper is the Minimum Perimeter Polygon Problem (MP3): for a given set $V$ of points in the plane, find a polygon $P$ with holes that has vertex set $V$, such that the total boundary length is smallest possible. The MP3 can be considered a natural geometric generalization of the Traveling Salesman Problem (TSP), which asks for a simple polygon with minimum perimeter. Just like the TSP, the MP3 occurs naturally in the context of curve reconstruction.

There are three main results in this paper: (1) A proof of NP-hardness of the MP3; (2) a constant-factor approximation algorithm; and (3) a branch-and-cut algorithm. In this presentation, the focus will be on (3), showing how the geometric properties of the problem can aid in finding provably optimal solutions to the MP3.

Reference(s):
[1] Sándor P. Fekete, Andreas Haas, Michael Hemmer, Michael Hoffmann, Irina Kostitsyna, Dominik Krupke, Florian Maurer, Joseph S. B. Mitchell, Arne Schmidt, Christiane Schmidt, Julian Troegel. Computing nonsimple polygons of minimum perimeter. Journal of Computational Geometry, volume 8(1), pages 340-365, 2017.

A well-studied object in combinatorial optimization is the perfect matching polytope of a graph $G$ — the convex hull of the incidence vectors of all perfect matchings of $G$. In any such investigation, one may assume that $G$ is matching covered — that is, G is a connected graph (on at least two vertices) and each edge of $G$ lies in some perfect matching.
A graph $G$ is Birkhoff–von Neumann if its perfect matching polytope is characterized solely by non-negativity and degree constraints. A result of Balas [1] implies that $G$ is Birkhoff–von Neumann if and only if $G$ does not contain a pair of vertex-disjoint odd cycles $(C_1, C_2)$ such that $G − V (C_1) − V (C_2)$ has a perfect matching. It follows immediately that the corresponding decision problem is in co-$\mathcal{NP}$. However, it is not known to be in $\mathcal{NP}$. The problem is in $\mathcal{P}$ if the input graph is planar — due to a result of Carvalho, Lucchesi and Murty [3]. More recently, in a joint work with these three authors, we have shown that this problem is equivalent to the seemingly unrelated problem of deciding whether a given graph is ‘prism-free’.
The combinatorial diameter of a polytope is the diameter of its 1-skeleton graph. A graph $G$ is PM-compact if the combinatorial diameter of its perfect matching polytope equals one. A result of Chvátal [4] implies that $G$ is PM-compact if and only if $G$ does not contain a pair of vertex-disjoint even cycles $(C_1, C_2)$ such that $G − V(C_1) − V(C_2)$ has a perfect matching. Once again the corresponding decision problem is in co-$\mathcal{NP}$, but it is not known to be in $\mathcal{NP}$. The problem is in $\mathcal{P}$ if the input graph is bipartite or is ‘near-bipartite’ — due to results of Wang, Lin, Carvalho, Lucchesi, Sanjith and Little [5].
Recently, in a joint work with Carvalho, Wang and Lin [2], we considered the “intersection” of the aforementioned problems. We give a complete characterization of matching covered graphs that are Birkhoff–von Neumann as well as PM-compact. Thus the corresponding decision problem is in $\mathcal{P}$.
I will discuss the two problems, and our recent result mentioned above. The talk will be mostly self-contained. I will assume only basic knowledge of graph theory. I will perhaps not present any lengthy proofs.

Reference(s):
[1] E. Balas. Integer and fractional matchings. North-Holland Math. Stud., volume 59, pages 1–13, 1981.
[2] Marcelo H. de Carvalho, Nishad Kothari, Xiumei Wang, Yixun Lin. Birkhoff-von Neumann Graphs that are PM-compact. arXiv preprint arXiv:1807.07339, 2018.
[3] Marcelo H. de Carvalho, Cláudio Leonardo Lucchesi, Uppaluri S. R. Murty. The perfect matching polytope and solid bricks. J. Comb. Theory, Ser. B, volume 92, issue 2, pages 319-324, 2004.
[4] V. Chvátal. On certain polytopes associated with graphs. J. Combin. Theory Ser. B, volume 18, pages 138–154, 1975.
[5] Xiumei Wang, Yixun Lin, Marcelo H. de Carvalho, Cláudio Leonardo Lucchesi, G. Sanjith, Charles H. C. Little. A characterization of PM-compact bipartite and near-bipartite graphs. Discrete Math., volume 313, issue 6, pages 772-783, 2013.

In this seminar, we present some of the main results of the paper “Bitcoin Mining Pools: A Cooperative Game Theoretic Analysis” [1].
Bitcoin is an innovative decentralized cryptocurrency whose core security relies on a “proof of work” procedure, which requires network participants to repeatedly compute hashes on inputs from a large search space. Finding one of the rare inputs that generates an extremely low hash value is considered a successful attempt, allowing miners to approve new transactions and, in return, to collect rewards in bitcoins.
This reward allocation, which provides the incentive for miners to participate, is a random process with a large variance. Miners who desire a steady income thus often participate in mining pools that divide among their members the earned rewards, and reduce this variance. Mining pools are slightly better at coordinating participants due to lower latency communication, a fact which implies that they manage to collect slightly higher rewards.
The paper examine dynamics of pooled mining and the rewards that pools manage to collect, and use cooperative game theoretic tools to analyze how pool members may share these rewards. The authors show that for some network parameters, especially under high transaction loads, it is difficult or even impossible to distribute rewards in a stable way: some participants are always incentivized to switch between pools.

Reference(s):
[1] Yoad Lewenberg, Yoram Bachrach, Yonatan Sompolinsky, Aviv Zohar, and Jeffrey S. Rosenschein. Bitcoin Mining Pools: A Cooperative Game Theoretic Analysis. In: Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems (AAMAS’2015), pages 919-927, 2015.

The understanding of how different two organisms are is one of the challenging tasks of modern science. A well accepted way to estimate the evolutionary distance between genomes of two organisms is estimating the rearrangement distance, which is the smallest number of rearrangements needed to transform one genome into another. By representing genomes as permutations, one of them can be represented as the identity permutation and so we reduce the problem of transforming one permutation into another to the problem of sorting a permutation using the minimum number of operations. In this work, we study the problems of sorting permutations using reversals and/or transpositions, with some additional restrictions of biological relevance. Given a value $\lambda$, the problem now is how to sort a $\lambda$-permutation, which is a permutation where all elements are less than $\lambda$ positions away from their correct places (regarding the identity), by applying the minimum number of operations. Each $\lambda$-operation must have size at most $\lambda$ and, when applied over a $\lambda$-permutation, the result should also be a $\lambda$-permutation. We present algorithms with approximation factors of O($\lambda^2$), O($\lambda$), and O(1) for the problems of Sorting $\lambda$-Permutations by $\lambda$-Reversals, by $\lambda$-Transpositions and by both $\lambda$-Operations.

Reference(s):
Guilherme Henrique Santos Miranda, Alexsandro Oliveira Alexandrino, Carla Negri Lintzmayer, Zanoni Dias. Sorting $\lambda$-Permutations by $\lambda$-Operations. In: Proceedings of the 11th Brazilian Symposium on Bioinformatics (BSB’2018), pages 1-13, 2018.