Return to Events


General presentation

Title: ADdressing DIfficult problems in a Computationally Tractable fashION

Dates: November 16-21, 2014

Location: Olissipo Marquês de Sá Hotel, Lisbon, Portugal

ADDICTION is the second event organised by the Inria AMICI International Partnership. The goal of ADDICTION is to focus on smart data structures, algorithm engineering and experimental algorithms, probabilistic algorithms, and (M)ILP approaches simple and enumerative for dealing with exponential problems with a particular focus on computational biology. The School is addressed to young researchers at the PhD student or postdoc level, but also to any other interested listeners. The scope of ADDICTION is international.

A poster is available here for printing and display in your institution.

Back to top

Keynote lecturers

Friedrich Eisenbrand (EPFL, Switzerland)

Title lecture: Randomized algorithms for linear programming.

Short bio: Friedrich Eisenbrand is a professor of Mathematics and Computer Science at EPFL in Lausanne. His main research interests lie in the field of discrete optimization, in particular in algorithms and complexity, integer programming, geometry of numbers, and applied optimization. He is best known for his work on efficient algorithms for integer programming in fixed dimension and the theory of cutting planes, which are an important tool to solve large scale industrial optimization problems. Friedrich received the Heinz Maier-Leibnitz award of the German Research Foundation (DFG) in 2004, the Otto Hahn medal of the Max Planck Society in 2001 and he was a recipient of an Alexander von Humboldt professorship in 2011.

Giuseppe F. Italiano (University of Rome “Tor Vergata”, Italy)

Title lecture: Dynamic Graph Algorithms.

Short bio: Giuseppe F. Italiano is a Professor of Computer Science at University of Rome “Tor Vergata” in Italy, where he was also the Department Chair from 2004 to 2012, Chair of the Evaluation Committee from 2002 to 2008, and is currently Vice-Rector for Quality, Evaluation and Performance. Prior to joining “Tor Vergata” in 1998, he was a researcher at the IBM T.J. Watson Research Center in the US, and a professor of computer science at University of Salerno and University of Venice, Italy.

Giuseppe F. Italiano’s research focuses on the design, analysis, implementation and experimental evaluation of algorithms and data structures. In particular, he is interested in several research areas, including algorithm engineering, combinatorial algorithms, computer security, graph algorithms and string algorithms. In those areas, he has published over 200 papers in journals and conference proceedings, is the inventor of few US patents, and has co-founded two technology startups, one focusing on security for mobile devices and the other on wireless technologies for pervasive and mobile computing.

Giuseppe F. Italiano has been serving as Editor-in-Chief and Associate Editor in several journals in theoretical computer science. His research has been funded in part by several EU projects, industrial contracts and by the Italian Ministry of Education, University and Research.

Kurt Mehlhorn (Max-Planck-Institute für Informatik at Saarbrücken, Germany)

Title lectures: (1) Certifying Algorithms; (2) Physarum Computations; and (3) The Virtual-Address-Model of Computation.

Short bio: Kurt Mehlhorn is Director at the Max-Planck-Institute for Computer Science and Professor of Computer Science at Saarland University.

His research interest are data structures, graph algorithms, computational geometry and geometric computing, natural computation, computer algebra, algorithm, and software libraries. He is recipient of the Leibniz-Award, the Karl-Heinz-Beckurts-Award, the EATCS-Award (2010), the ACM Theory and Practice Award, and the Erasmus Medal. He is member of the German National Academy of Science and the US Academy of Engineering.

He is one of the people behind LEDA and CGAL and a co-founder of Algorithmic Solutions GmbH.

He supervised more than 60 PhD-students and hosted about the same number of postdocs. Kurt Mehlhorn has published 6 books and more than 300 articles in scientific journals and conferences.

Eli Upfal (Brown University, USA)

Title lecture: Probabilistic methods in algorithms with applications to computational biology.

Short bio: Eli Upfal is a professor of computer science at Brown University; where he was also the department chair from 2002 to 2007. Prior to joining Brown in 1998, he was a researcher and project manager at the IBM Almaden Research Center in California, and a professor of Applied Mathematics and Computer Science at the Weizmann Institute of Science in Israel.

Professor Upfal’s research focuses on the design and analysis of algorithms. In particular he is interested in randomized algorithms, probabilistic analysis of algorithms, and computational statistics, with applications ranging from combinatorial and stochastic optimization to routing and communication networks, computational biology, and computational finance.

Professor Upfal is a co-author of a popular textbook “Probability and Computing: Randomized Algorithms and Probabilistic Analysis” (with M. Mitzenmacher, Cambridge University Press 2005 – translated to Chinese, Japanese and Polish). He is the inventor of 13 US patents. His patents related to sequencing by hybridizations (with F. Preparata) were licensed to GeneSpectrum Inc., a bio-tech startup (acquired by NABsys inc. in 2006).

Professor Upfal is a fellow of the IEEE and the Association for Computing Machinery (ACM). He received the IBM Outstanding Innovation Award, and the IBM Research Division Award, His work at Brown has been funded in part by the National Science Foundation (NSF), The Defense Advanced Research Projects Agency (DARPA), The office of Naval Research (ONR), and the National Institute of Health (NIH).

Alain Viari (Inria Grenoble Rhône-Alpes, France)

Title lecture: Open Challenges in computational biology, an introduction to the School.

Short bio: Alain Viari graduated from the University Pierre et Marie Curie (Paris VI) and holds a PhD in Biophysics. From 1988 to 1999, he worked as a CNRS researcher at the Institut Curie (Physics department) and the University Paris VI (Atelier de Bioinformatique). He moved to Inria in 2000 as Director of research and was successively at the head of a bioinformatics research team (Helix) and Scientific Delegate of the Grenoble-Rhône-Alpes research center. He is now a member of the Bamboo team at Inria.

Since 2012, Alain Viari has been appointed Deputy Scientific Director at Inria responsible for ICST (Information and Communication Science and Technology) for Life and Environmental Sciences. His research activities focus on the development of string and graph algorithms for genomics and proteomics. More recently, he grew a new interest for the ecology and evolutionary study of infectious diseases.

Back to top

Important dates

Arrivals: Sunday, November 16
Welcome cocktail: Sunday evening, November 16
Workshop starts: Monday morning, November 17
Workshop ends: Friday, November 21 (lunchtime)
Departures: Friday afternoon, November 21

Back to top


The program may be found below, where CLOP stands for Contributed Lectures and Open Problems.

The School was welcomed on Monday morning by Arlindo Oliveira, Professor at the Department of Computer Science and Engineering of Instituto Superior Técnico (IST), the school of Engineering of Lisbon University, and currently the President of IST and member of its executive board.

Slides of the presentations may be obtained by clicking on the name of the speaker for each lecture. Notice that for Friedrich Eisenbrand, the first two lectures are gathered in a same set of slides that may be obtained by clicking on the first or the second lecture.

  Sunday 16 Monday 17 Tuesday 18 Wednesday 19 Thursday 20 Friday 21
09h30-11h00 Arrivals Intro: A. Viari E. Upfal F. Eisenbrand G. Italiano K. Mehlhorn
11h00-11h30 Coffee break Coffee break Coffee break Coffee break Coffee break
11h30-12h30 E. Upfal K. Mehlhorn E. Upfal F. Eisenbrand F. Eisenbrand
12h30-15h00 Lunch Lunch Lunch + Excursion + Dinner Lunch Lunch
15h00-16h00 G. Italiano G. Italiano K. Mehlhorn Departures
16h00-16h30 Coffee break Coffee break Coffee break
16h30-18h00 CLOP CLOP CLOP
18h00-20h00 Welcome cocktail Free Free Free
20h00 Dinner Dinner Dinner Dinner

Back to top


Scientific organising committee:
Pierluigi Crescenzi, University of Florence, Italy
Alberto Marchetti-Spaccamela, University of Rome, La Sapienza, Italy
Marie-France Sagot, INRIA and University of Lyon 1, France
Leen Stougie, Free University Amsterdam and CWI, Netherlands

Florence Bouheddi and Marie-France Sagot, INRIA, France, with the help of Susana Vinga.

Back to top


Registration is now closed!

As a reminder, the registration fee was:

  • Before September 30, 2014 (early registration fee): 250 euros for PhD students and 300 euros for postdocs or other researchers.
  • After September 30, 2014 (late registration fee): 300 euros for PhD students and 350 euros for postdocs or other researchers.

The fees cover for access to the school, mid-day meals, coffee breaks and gala dinner. It does not cover for dinner, neither for accommodation which must be done directly at the hotel where the school will take place at a preferential rate until 17/10/2014 (normal rate afterwards), or at any other hotel of a participant’s choice. There are many within walking distance. For booking the hotel where the school wll take place, see the registration page.

Please go to this page in order to do the registration.

Back to top


Accommodation can be provided by the hotel where the school will be organised (Olissippo Marquês de Sá hotel) at a preferential rate until 17/10/2014: Single room: 64 € / Double room: 74 €.

To benefit from this rate, you have to send back a form that may be recovered here (Section “Hotel Accommodation” at the foot of the webpage).

Back to top


ERC logoADDICTION is funded by the ERC AdG SISYPHE.

ERC logoParticipation to ADDICTION is partially supported by the FP7 KBBE project BacHBerry.

Back to top

List of participants


Vicente Acuña, Centro de Modelamiento Matemático, University of Chile, Santiago, Chile
Ricardo Andrade, Ciência sem Fronteiras, Lyon, France
Christian Baudet, Inria, Lyon, France
Laurent Bulteau, Inria, France
Anna Paola Carrieri, University Milano-Bicocca
Cecilia Coimbra Klein, Inria, Lyon, France
Pierluigi Crescenzi, University of Florence, Italy
Gianlorenzo d’Angelo, Gran Sasso Science Institute, L’Aquila, Italy
Friedrich Eisenbrand, EPFL, Lausanne, Italy
Mariana Galvão Ferrarini, Inria, Lyon, France
Mattia Gastaldello, University La Sapienza Rome, Italy
Sebastian Hanisch, University of Rostock, Germany
Andras Hartman, IDMEC, IST, Lisbon, Portugal
Susan Higashi, Inria, Lyon, France
Leandro Ishi Soares de Lima, Campo Grande, Brazil
Giuseppe F. Italiano, University Tor Vergata Rome, Italy
Alice Julien-Laferrière, Inria, Lyon, France
Camille Marchet, Inria, Lyon, France
Alberto Marchetti-Spaccamela, University La Sapienza Rome, Italy
Andrea Marino, University of Milan, Italy
Arnaud Mary, University of Lyon, France
Kurt Melhorn, Max-Planck Institute, Saarbrücken, Germany
Filipe Nevola, TecSinapse, Brazil
Alexandros Panagiotidis, Greece
Delphine Parrot, Inria, Lyon, France
Thomas Piccheti, MAP5, University of Paris 5, France
Nadia Pisanti, University of Pisa, Italy
Jerôme Renaux, KULeuven, Belgium
Gustavo Sacomoto, Inria, Lyon, France
Marie-France Sagot, Inria, Lyon
Matteo Seminaroti, CWI, Amsterdam, The Netherlands
Lorenzo Severini, Gran Sasso Science Institute, L’Aquila, Italy
Blerina Sinaimeri, Inria, Lyon, France
Leen Stougie, Free University Amsterdam & CWI, Amsterdam, The Netherlands
Paulo Trenhago, Capes, Lyon & LNCC, France & Brazil
Eli Upfal, Brown University, Providence, USA
Laura Urbini, Inria, Lyon, France
Yllka Velaj, Gran Sasso Science Institute, L’Aquila, Italy
André Veríssimo, IDMEC, IST, Lisbon, Portugal
Alain Viari, Inria, Grenoble, France
Paulo Vieira Milreu, TecSinapse, Campinas, Brazil
Susana Vinga, IDMEC, IST, Lisbon, Portugal
Martin Wannagat, Inria, Lyon, France

Back to top


The School will take place in central Lisbon, Portugal, at the Olissippo Marquês de Sá hotel in Lisbon, Portugal. The hotel is a 2-minutes walk away from the Calouste Gulbenkian Museum. It is located between three of the main Metro lines of Lisbon (red, yellow and blue).

For more information on Lisbon, you may want to visit this page.

Back to top

How to reach Lisbon

Lisbon is very easy to get to. It is just a short flight away from most European locations and also accessible by road and rail. There are moreover direct flights to it from major cities outside Europe.

Flights to Lisbon
The airport has daily flights to and from the major cities in the world and the main national airline is TAP. Lisbon is also reachable using low-cost companies. The airport is located seven kilometres (four miles) north of the city. There is now a direct Metro connection to the city center, including to where the School will take place (red line, then get off at São Sebastião station).

If you’re driving to Lisbon, enjoy the countryside along the way. The A1 Auto-estrada do Norte extends from Porto to Lisbon and the A8 arrives from destinations to the north and west of the city. The A2 Auto-estrada do Sul arrives from the Algarve via Almada and the Ponte 25 de Abril. The A12 crosses the Ponte Vasco da Gama, offering a less congested route into the city.

Trains to Lisbon
International trains arrive in Lisbon every day, mainly to Santa Apolónia Station and to the Gare do Oriente located in the former Expo Park, today known as Nations Park. Intercity trains connect all of Portugal’s major cities to either Lisbon or Porto. Both the comfortable Alfa Service from Porto and the InterCity train from Faro take 3 hours 30 minutes to reach Lisbon. There are overnight trains from, for instance, Madrid (10 hours) and Paris (18 hours 30 minutes).

Back to top

Permanent link to this article: