Palestrantes Convidados

Programação científica


Segunda-feira 28 de março

09h00 : Plenária - Dijkstra Graphs - Jayme L. Szwarcfiter
10h00 : Resumos
11h10 : Problemas em aberto
12h00 : Almoço
14h00 : Grupos de trabalho
16h00 : Coffee-break
16h15 : Evento social

Terça-feira 29 de março

09h00 : Plenária - Recent progress on coloring perfect graphs - Nicolas Trotignon
10h00 : Resumos
11h30 : Sessão de problemas em aberto
12h00 : Almoço
14h00 : Plenária - On Some Packing Games - Flávio Miyazawa
15h00 : Grupos de trabalho
16h00 : Coffee-break
16h30 : Discussão do progresso obtido nos problemas apresentados

Quarta-feira 30 de março

09h00 : Plenária - Solving the classification problem with combinatorial optimization tools - Ricardo Corrêa
10h00 : Resumos
11h30 : Sessão de problemas em aberto
12h00 : Almoço
14h00 : Plenária - Antistrong digraphs - Stéphane Bessy
15h00 : Grupos de trabalho
16h00 : Coffee-break
16h15 : Evento social

Quinta-feira 31 de março

09h00 : Plenária - Revisiting Resolution Search - Phillippe Michelon
10h00 : Resumos
11h10 : Sessão de problemas em aberto
12h00 : Almoço
14h00 : Plenária - Tree-decompositions with metric properties on the bags - Nicolas Nisse
15h00 : Grupos de trabalho
16h00 : Coffee-break
16h30 : Discussão do progresso obtido nos problemas apresentados

Sexta-feira 01 de abril

09h00 : Plenária - Subdivisions of oriented cycles in digraphs with large chromatic number - F. Havet
10h00 : Discussão final de resultados
12h00 : Almoço
13h00 : Transfer para Fortaleza (Aeroporto Pinto Martins)

Resumos das Plenárias


Jayme L. Szwacfiter
Título: Dijkstra Graphs
Resumo: We re-visit a concept that has been, in a way, central in some early stages of computer science, that of structured programming. Basically it consists of a set of rules that an algorithm has to follow, in order to acquire a structure that is desired in many aspects. In spite of the fact that much has been written about structured programming, an im- portant issue has been left unanswered: given an arbitrary algorithm, described by its flowchart, decide whether or not it is structured, that is, whether or not it follows the stated principles for structuring. By employing graph theoretic tools and algorithmic techniques, we for- mulate an efficient algorithm for answering this question. In order to do so, first we introduce the class of graphs which correspond to the structured algorithms, which were then been named as Dijkstra Graphs. Our recognition problem then became to recognize graphs of this class. Further, we describe an efficient isomorphism algorithm for Dijkstra graphs. Both the recognition and isomorphism algorithms have complexity O(n^2), for graphs with n vertices.
Joint work with Lucila M. Bento, Davidson Boccardo, Raphael C. Machado and Vinicius G. Sá.

Nicolas Trotignon
Título: Recent progress on coloring perfect graphs
Resumo: Finding a combinatorial algorithm that would color in polytime any input perfect graph is perhaps the most well known open question about perfect graphs. In the last years, several progress have been made in this direction, by different authors. In particular : how to use decompositions (2-joins, and in some cases balanced skew partitions), how to improve the known decomposition theorems (in the square-free case). Results of the following authors (in some case jointly with the speaker) will be presented : Maria Chudnovsky, Aurélie Lagoutte, Irene Lo, Frédéric Maffray, Paul Seymour, Sophie Spirkl, Krisitina Vuskovic.

Flávio Miyazawa
Título: On Some Packing Games
Resumo: In the classical bin packing problem, we have a list of items, each of them with a specific size, and bins of bounded capacity, and the objective is to obtain a packing of the items into the minimum number of bins. We consider game-theoretic versions of this problem, where each player controls exactly one item and is charged with a cost defined as the ratio between the area of the item and the occupied area of the respective bin. Initially, a set of items is packed in bins and, one at a time, players selfishly move their items from one bin to another, in order to minimize the costs they are charged. In this game, the social cost is the number of used bins, and the optimal social cost is the minimum number of bins needed to pack the given items. We present some known results and ours for variants of one or more dimensions, considering the price of anarchy, coalitions and convergence time to attain Nash equilibrium. Some of the presented results are joint work with C.G. Fernandes, C. E. Ferreira, and Y. Wakabayashi.

Ricardo Corrêa
Título: Solving the classification problem with combinatorial optimization tools
Resumo: In the last 30 years, the availability of massive amounts of data in electronic form have led to the development of the field of data mining. A central problem in this field is data classification which consists in detecting a pattern in a set of classified data (referred to as samples) in order to predict the classification of unclassified ones. While continuous optimization methods have been widely used to solve the classification problem, the common sense was created that combinatorial optimization methods for this problem are not tractable in practical computational settings. More recently, the significant advances in integer programming tools and the vertiginous increases in computational power have motivated some authors to question this common sense. Investigation conducted by different authors in distinct contexts show that combinatorial approaches to the classification problem has been becoming a promising alternative. In this talk, we give an outline of mixed linear programming and 0-1 integer programming formulations for the classification problem in cases meeting the following assumptions: (a) there is an underlying pattern to the set of samples that can be expressed by some notion of convex sets; and (b) the data set contains outliers, which are not previously identified in the data set. We focus our attention in two particular cases of convexity. The first one is the natural geometric (or Euclidean) convexity notion, which is used in all studies in the literature (to the best of our knowledge). In this case, it is assumed that the samples are represented by vectors of real numbers in a multidimensional space and it is expected that the underlying pattern is associated with the spatial location of these samples. We give some preliminary computational results to show that this is a promising approach with respect to the quality of the solution. The second case is exploratory, since it has not been studied in the literature. It consists of stating the classification problem in terms of geodesic convexity in graphs, whose motivation is twofold. Firstly, it is of theoretical interest since it concerns the possibility of establishing new problems on graphs. Secondly, it models the underlying pattern by means of a binary relation on the set of samples. Consequently, the samples need not to be formed by numerical values and the classification problem becomes purely combinatorial.

Stéphane Bessy
Título: Antistrong digraphs
Resumo: An antidirected trail in a digraph is a trail (a walk with no arc repeated) in which the arcs alter- nate between forward and backward arcs. An antidirected path is an antidirected trail where no vertex is repeated. We show that it is NP-complete to decide whether two vertices x, y in a digraph are connected by an antidirected path, while one can decide in linear time whether they are connected by an antidirected trail. Indeed this can be done easily by looking for an (x,y)-path in the adjacency bipartite of the input digraph. Motivated by this observation, we say that a digraph is antistrong if its adjacency bipartite is con- nected. We study natural algorithmic questions on antistrong digraphs. Some results derive easily from the definition (eg. checking k-arc-antistrongness, or computing the minimum number of arcs to add to be antistrong....), other are more difficult to establish. In particular, we use results from matroid theory to characterize graphs which admit an antistrong orientation and give a polynomial time algorithm for constructing such an orientation when it exists. In this talk, I will present these notions and results and also give some problems and conjectures related to this area.
This is joint work with J.Bang-Jensen, M.Kriesell and B.Jackson

Phillippe Michelon
Título: Revisiting Resolution Search
Resumo: In 1997, V. Chvatal proposed an alternative method to the classical branch-and-bound approach for solving Combinatorial Optimization problems, that he named "Resolution Search". So far, Resolution Search has been under used and almost ignored. Among others reasons that can explain this phenomena, there is the efficiency of the Integer and Linear Programming codes that makes difficult the emergence of new methods in a short period of time. Nevertheless, it is somehow unreasonable to only have one method, whose limitations in space and time are known, for solving the numerous and tremendously important combinatorial optimization industrial problems. In this talk, we will revisit the Resolution Search approach and try to point out some research directions that could be of interest. In particular, we will point out that Resolution Search is actually a rich (and exact) method that allows to build bridges between exact and heuristic methods, since it can be seen as a multi-start descent method while maintaining a set of (partial) solutions.

Nicolas Nisse
Título: Tree-decompositions with metric properties on the bags
Resumo: Tree-decompositions of graphs are a way to study and model topological structure of graphs. Such decompositions have many applications for designing algorithms that allow to efficiently solve difficult (NP-hard in general) problems in graphs (e.g., coloring, dominating set, cover...). The classical approach consists in decomposing graphs in small “pieces” (subsets of vertices) that may be organized along the minimal separators of the graph. Another approach is to minimize metric properties of these pieces instead of their size. For instance, minimizing the bags' diameter (resp., radius) correspond to the tree-length (resp. tree-breadth) We survey some recent results on the computational complexity of these parameters and their relationship with the treewidth of graphs.
This is joint work with D. Coudert, G. Ducoffe and S. Legay

Frédéric Havet
Título: Subdivisions of oriented cycles in digraphs with large chromatic number
Resumo: An oriented cycle is an orientation of a undirected cycle. We first show that for any oriented cycle C, there are digraphs containing no subdivision of C (as a subdigraph) and arbitrarily large chromatic number. In contrast, we show that for any C is a cycle with two blocks, every strongly connected digraph with sufficiently large chromatic number contains a subdivision of C. We prove a similar result for the antidirected cycle on four vertices (in which two vertices have out-degree 2 and two vertices have in-degree 2).
This is joint work with N. Cohen, W. Lochet and N. Nisse.