Geometry, Combinatorics, and Algorithms (GeCoaL)

GeCoaL is a research team of the Laboratoire d'Informatique of École normale supérieure, supported by ENS and CNRS. Its research field is the development of algorithms for combinatorial optimization and for geometric and topological problems.
[double torus]

Members

Former members: Michel Pocchiola (MdC ENS, -2009) - Vincent Pilaud (Ph.D. student, 2007-2009) - Luc Habert (Ph.D. student, 2003-2009) - Laurent Rineau (Ph.D. student, 2002-2007) - Pierre Angelier (Ph.D. student, 1998-2002).

Former visitors: Benjamin A. Burton (June 16-23, 2011) - Claire Mathieu (Mar. 2011) - Jaroslav Nesetril (May 2009) - Ioannis Emiris (Feb.-Mar. 2009) - Micha Sharir (Oct. 2008) - Francisco Santos (June 1-30, 2008) - Jürgen Bokowski (Nov. 19-24, 2007) - Ricky Pollack (Nov. 26-Dec. 2, 2007) - Herbert Edelsbrunner (May 2007) - Günter Rote (Sep. 2005) - Jack Snoeyink (Apr. 2003) - Ileana Streinu (Mar. 2003) - Gert Vegter (Mar. 1999)...

Former internship students: Arnaud de Mesmay (M2, Mar.-Aug. 2011) - Alexandre Boulc'h (M1, Apr.-Aug. 2010) - Kshitij Bansal (L3, May-June 2009) - Julien Ferté (M1, Mar.-July 2008) - Hrushikesh Tilak (L3, May-June 2008) - Preyas Popat (L3, May-June 2008) - Shreevasta Rajagopalan (L3, May-June 2007) - Laurent Jouhet (M2, Mar.-Aug. 2007) - Vincent Pilaud (M2, Mar.-Aug. 2005) - Constin Vilcu (M2, Mar.-Aug 2004)...

Next seminar

Thursday, January 5, 2012: Thomas Sauerwald, Ultra-Fast Rumor Spreading on Social Networks. Details.

Current Research Directions

The current research themes of the team include the design of algorithms and study of combinatorial structures for geometrical and topological problems, and for combinatorial optimization. We use tools from algebraic topology, combinatorics, probability theory, and mathematical programming. In terms of communities, the main relevant fields are discrete algorithms (SODA) and computational geometry (SoCG), with links to combinatorics and graph theory. The following four research directions are currently investigated (anticipating the upcoming venue of Claire Mathieu):
  • algorithms for embedded graphs: approximation algorithms for network design problems on planar graphs; algorithms for topological problems in graphs on surfaces;
  • approximation algorithms and techniques for combinatorial optimization;
  • streaming and online algorithms for graph problems;
  • combinatorial geometry problems with a topological flavor.

Main Collaborations

Contact

LIENS
DI - École normale supérieure
45, rue d'Ulm
75230 Paris Cedex 05 - France
Phone: +33 1 44 32 20 53
Offices: "Hauts du DI" (Staircase A, 3rd floor)

 
Webmaster: webdi[@]di[.]ens[.]fr.