mercredi 22 juin 2016, 11h, A403 (attention, jour et heure inhabituels) : Two Applications of Mixed Integer Nonlinear Programming (MINLP) in R^n : the Euclidean Steiner Tree Problem and Covering a Solid with Different Spheres.
Nelson Maculan (Federal University of Rio de Janeiro, Brazil) :
The Euclidean Steiner tree problem (ESTP) in Rn consists of
finding a tree of minimal Euclidean length that spans a given set of
points in Rn, using or not additional points. Only a few papers
consider the exact solution for the ESTP in Rn (n>2) and there are
just two works that considered a mathematical programming
formulation for the ESTP. One of them presented a "convex"
mixedinteger formulation that could be implemented in a Branch and
Bound (B&B) algorithm.
We also present a mathematical programming model for the problem of
covering solids by spheres of different radii. Given a set of
spheres, possibly with different diameters, and a solid, the goal is
to locate the spheres in such a way their union forms a coverage for
this solid, using the smallest possible number of spheres of this
set. This problem has an application in the radio-surgical treatment
planning known as Gamma Knife and can be formulated as a "non-convex"
optimization problem with quadratic constraints and a linear
objective function.
The distance geometry problem.
Leo Liberti (LIX Ecole Polytechnique) :
Distance geometry mainly aims at realizing metrics in Euclidean or other normed spaces. We discuss the case where the metric is finite and partial, i.e. the realization of weighted graphs. As the time allows, we shall discuss a combination of history, applications, combinatorial methods and formulation-based methods.
Joint work with C. Lavor, N. Maculan, A. Mucherino and many other people.
lundi 4 avril 2016, 14h, A 403 : Chien-Chung Huang (Chalmers University). Minimizing the number of unhappy singles : improved approximation algorithms for the stable marriage problem with one-sided ties.
Abstract : We consider the problem of computing a large stable matching in
a bipartite graph $G = (A\cup B, E)$ where each vertex $u \in A\cup B$ ranks its
neighbors in an order of preference, perhaps involving ties.
A matching $M$ is said to be stable if
there is no edge $(a,b)$ such that $a$ is unmatched or prefers $b$ to $M(a)$ and similarly,
$b$ is unmatched or prefers $a$ to $M(b)$. While a stable matching in $G$ can be easily
computed in linear time by the Gale-Shapley algorithm,
it is known that computing a maximum size stable matching is APX-hard.
In this talk, we consider the special case of one-sided ties and give new approximation algorithms.
lundi 21 mars 2016, 14h, P 301 : Ljiljana Brankovic (University of NewCastle). Linear-Time Superbubble Identification Algorithm for Genome Assembly.
DNA sequencing is the process of determining the exact order of the nucleotide bases of an individual’s genome in order to catalogue sequence variation and understand its biological implications. Whole-genome sequencing techniques produce masses of data in the form of short sequences known as reads. Assembling these reads into a whole genome constitutes a major algorithmic challenge. Most assembly algorithms utilize de Bruijn graphs constructed from reads for this purpose. A critical step of these algorithms is to detect typical motif structures in the graph caused by sequencing errors and genome repeats, and filter them out ; one such complex subgraph class is a so-called superbubble. In this talk, we present an O(n+m)-time algorithm to detect all superbubbles in a directed acyclic graph with n nodes and m (directed) edges, improving the best-known O(m log m)-time algorithm by Sung et al.
This is a joint work with Costas S. Iliopoulos, Ritu Kundu, Manal Mohamed, Solon P. Pissis and Fatima Vayani.
lundi 14 mars 2016, 14h, A 711 : Yann Ponty (LIX, Polytechnique). Selected combinatorial problems in RNA Bioinformatics
Slides
In this seminar, I will review some (hard) combinatorial problems arising in RiboNucleic Acids (RNA) computational biology. RNA is indeed a fascinating biopolymer, whose instances can be represented as sequences over a four-letter alphabet A,C,G,U. Through the spontaneous formation of hydrogen bonds, creating base-pairs, it adopts one (or several) 3D structure(s), that are traditionally abstracted as a secondary structure, ie a (non-crossing) matching of the sequence positions. This structure is, for many functional RNA families, more conserved throughout evolution than the sequence, and are essential to its function(s).
The talk will focus on four historic problems in RNA research : the prediction of the most stable structure for a given RNA (RNA structure prediction) ; the computation of thermodynamic quantities at the Boltzmann equilibrium (partition function) ; the estimation of the activation energy between two structures (energy barrier) ; the search for an occurrence of a given RNA within a genome (sequence/structure comparison), and the design of an RNA sequence that preferentially adopts a given structure (RNA design). While most of these problems become NP-hard (sometimes APX-hard) as soon as crossing base-pairs are allowed, some problems are already hard in their non-crossing version. This motivates meta-heuristic approaches, exact exponential-time of Fixed-Parameter Tractable solutions. Interestingly, the complexity of the RNA design problem remains unknown more than two decades after its introduction, and I will mention recent developments towards its resolution.
Some of the work presented here is joint work with multiple co-authors from various institutions.
lundi 11 janvier 2016, 14h, A 707 : Pierre Le Bodic (Georgia Institute of Technolog). An Abstract Model for Branching and its Application to Mixed Integer Programming
The selection of branching variables is a key component of branch-and-bound algorithms for solving Mixed-Integer Programming (MIP) problems since the quality of the selection procedure is likely to have a significant effect on the size of the enumeration tree. State-of-the-art procedures base the selection of variables on their "LP gains", which is the dual bound improvement obtained after branching on a variable. There are various ways of selecting variables depending on their LP gains. However, all methods are evaluated empirically. In this paper we present a theoretical model for the selection of branching variables. It is based upon an abstraction of MIPs to a simpler setting in which it is possible to analytically evaluate the dual bound improvement of choosing a given variable. We then discuss how the analytical results can be used to choose branching variables for MIPs, and we give experimental results that demonstrate the effectiveness of the method on MIPLIB 2010 "tree" instances where we achieve a 5% geometric average time and node improvement, over the default rule of SCIP, a state-of-the-art MIP solver.
Joint work with George L. Nemhauser
lundi 23 novembre 2015, 13h, A711 : Ahmad Abdi (University of Waterloo). Studying Edmonds’ trick of bi-directing edges
A classical well-studied problem in combinatorial optimization is that of finding a minimum weight spanning tree of a graph. A linear programming (LP) approach is to use the cut LP relaxation, except that this LP is quite weak, outputting fractional optimal solutions even on a triangle. In 1967, Edmonds came up with a nifty trick to avoid this issue : bi-direct the edges and instead, in an equivalent manner, look for a minimum weight arborescence. He showed that the corresponding bi-directed cut LP relaxation is strong, in the sense that it can always output an integral optimal solution.
In this talk, I will generalize Edmonds’ operation to any set covering LP, and show how this operation always makes the LP stronger. We will survey the different attributes of this operation, and along the way, we make some beautiful connections to Menger’s theorem, Ford and Fulkerson’s theorem, comparability graphs, Steiner trees, degenerate projective planes, binary clutters and matroids.
Joint work with Ricardo Fukasawa and Laura Sanità.
lundi 2 novembre 2015, 14h, A 707 : Pinar Heggernes (Institutt for Informatikk Universitetet i Bergen ). Graph classes in enumeration Slides
Enumerating, counting, and determining the maximum number of various
objects in graphs have long been established as important areas within
graph theory and graph algorithms. As the number of enumerated objects
is very often exponential in the size of the input graph, enumeration
algorithms fall into two categories depending on their running time :
those whose running time is measured in the size of the input, and those
whose running time is measured in the size of the output. Based on this,
we concentrate on the following two types of algorithms.
1. Exact exponential time algorithms. The design of these algorithms
is mainly based on recursive branching. The running time is a function
of the size of the input graph, and very often it also gives an upper
bound on the number of enumerated objects any graph can have.
2. Output polynomial algorithms. The running time of these algorithms
is polynomial in the number of the enumerated objects that the input
graph actually contains. Some of these algorithms have even better
running times in form of incremental polynomial or polynomial delay,
depending on the time the algorithm spends between each consecutive
object that is output.
The methods for designing the two types of algorithms are usually
quite different. Common to both approaches is that efforts have
traditionally mainly been concentrated on arbitrary graphs, whereas
graphs with particular structure have largely been left unattended. In
this talk we look at enumeration of objects in graphs with special
structure. In particular, we focus on enumerating minimal dominating
sets in various graph classes.
The presentation is based on joint works with following co-authors :
Jean-Francois Couturier, Petr Golovach, Pim van ’t Hof, Mamadou Kanté, Dieter Kratsch, and Yngve Villanger.
jeudi 22 octobre 2015, 11h (attention, jour et heure inhabituels), B203 : Thomas McCormick (Sauder School of Business, University of British Columbia). Parametric Network Flows
Co-authors : S. Tom McCormick, Britta Peis, Jannik Matuschke, Fabio Tardella
We review the parametric optimization framework of Topkis, and how the
parametric min cut results of GGT fit into the framework. This framework
gives two main results : a Structural Property that min cuts are monotone
in the parameter, and an Algorithmic Property, that one can compute all
min cuts in the same time as solving the non-parametric problem. We
extend these results to parametric capacity and parametric rewards
versions of “Max Reward Flow”, a “max” version of Min Cost Flow. We
prove that the Structural Property again holds, and we adapt the Relax
algorithm of Bertsekas to also get the Algorithmic Property. We further
indicate how to extend the results to parametric Weighted Abstract Min
Cut, and to other problems.
lundi 19 octobre 2015, 14h, A 707 : Arman Boyacı (LAMSADE et Boğaziçi University). The Maximum Cardinality Cut Problem In Some Sub-class of Co-bipartite Graphs.
Joint work with : Tinaz Ekim, Mordechai Shalom
It is known that the maximum cardinality cut problem (MAXCUT) is NP-complete even in co-bipartite graphs.
We start by considering MAXCUT in co-bipartite chain graphs (the neighborhoods of the vertices in each clique can be linearly ordered with respect to inclusion).
We show that there is an explicit solution for the twin-free case.
Then using a dynamic programming algorithm we show that MAXCUT is polynomial-time solvable in this graph class.
Finally based on bi-modular decomposition technique, we will extend this result to some special sub-class of co-bipartite graphs.
lundi 12 octobre 2015, 14h, B102 Bis (attention, changement de salle) : Zsolt Tuza (MTA Renyi Institute, Budapest, and University of Pannonia, Veszprem Hungary). Decompositions of graphs into induced subgraphs.
Let F be a fixed graph. An induced F-decomposition of a graph G is a
collection of graphs F1 , ... , Fm such that each edge of G belongs to precisely
one Fi , moreover each Fi is isomorphic to F and is an induced subgraph of
G. Some years ago Bondy and Szwarcfiter raised the following Turan-type
question : Given F , what is the maximum number of edges in a graph of
order n that admits an induced F-decomposition ? We present an overview
of results, conjectures and related open problems.
lundi 5 octobre 2015, 14h, A 707 : Valia Mitsou (Institute of Computer Science and Control,
Hungarian Academy of Sciences.). Complexity and Approximability of Parameterized CSP
The complexity of various Constraint Satisfaction Problems (CSP) when parameterized by structural measures (such as treewidth or clique-width) is a very well-investigated area. In this talk, we take a fresh look at such questions from the point of view of approximation, considering four standard CSP predicates : AND, OR, PARITY, and MAJORITY. By providing new or tighter hardness results for the satisfiability versions, as well as approximation algorithms for the corresponding maximization problems, we show that already these basic predicates display a diverse set of behaviors, ranging from being FPT to optimize exactly for quite general parameters (PARITY), to being W-hard but well-approximable (OR, MAJORITY) to being W-hard and inapproximable (AND). Our results indicate the interest in posing the question of approximability during the usual investigation of CSP complexity with regards to the landscape of structural parameters.
lundi 28 septembre 2015, 14h, A 707 : Rémy Belmonte (Kyoto University.). Induced Minor Free Graphs : Isomorphism and Clique-width
Given two graphs G and H, we say that G contains H as an induced minor if a graph isomorphic to H can be obtained from G by a sequence of vertex deletions and edge contractions. We study the complexity of Graph Isomorphism on graphs that exclude a fixed graph as an induced minor. More precisely, we determine for every graph H that Graph Isomorphism is polynomial-time solvable on H-induced minor-free graphs or that it is isomorphism complete. Additionally, we classify those graphs H for which H-induced-minor-free graphs have bounded clique-width. Those two results complement similar dichotomies for graphs that exclude a fixed graph as an induced subgraph, minor or subgraph.
Collaboration avec Yota Otachi et Pascal Schweitzer.