Talgo (Theory, ALgorithms, Graphs, and Optimization)

Talgo is a research team of the Département d'Informatique of École normale supérieure, supported by ENS and CNRS. The current research themes of the team include the design of algorithms and study of combinatorial structures, in particular for combinatorial optimization and for geometric problems. We use tools from graph theory, combinatorics, probability theory, and mathematical programming.

News

• Positions: FSMP postdoc: please contact Chien-Chung Huang during the first half of November if you are interested in applying for an FSMP postdoc in the Talgo research group. Firm application deadline Dec 1, 2017. Postdoc starting date on or after October 2018.
• Claire Mathieu has the yearly Chair "Informatique et sciences numériques" of Collège de France in 2017-2018, with a course on Algorithms, and the first lesson will be on Nov 16 at 6pm.
• Vincent Cohen-Addad received the PhD thesis award Graphes Charles Delorme 2017, the 2017 PGMO prize, and the EATCS 2017 Distinguished Dissertation Award.
• Former PhD students : Frederik Mallmann-Trenn is a post-doctoral researcher at MIT; Hang Zhou is assistant professor at Ecole Polytechnique; Vincent Cohen-Addad is a CNRS researcher at LIP6 (UPMC University); Arnaud de Mesmay is a CNRS researcher at GIPSA-lab (Grenoble).

Seminar

Members

Permanent members

• Chien-Chung Huang (CR CNRS, head of team)
• Zhentao Li (assistant professor, on leave in 2017-18)
• Claire Mathieu (DR CNRS, visiting IRIF in 2017-18)
• Tatiana Starikovskaya (assistant professor)

Post-docs, visitors, interns, etc.

• Thang Nguyen (on sabbatical at ENS in 2017-2018, funded by CNRS)
• Abhinav Srivastav postdoc ENS-Dauphine, 2017-2018
• Nabil Mustafa (occasional visitor, since Fall 2016)
• Kevin Schewior, DAAD postdoc, starting June 2018

PhD students

• Victor Verdugo (defense planned 2018)
• Mathieu Mari (defense planned 2020)

Teaching

We co-teach Algorithms and programming at level L3 at ENS and Algorithms and combinatorics for geometric graphs at MPRI.

Main Collaborations

• with Dauphine (Vangelis Paschos et al.). Project MultiFAC (Multiple Facility Location). PSL funded project. Jan 2017-Dec 2018
• with Frédéric Magniez and other members of LIAFA (ANR "white" program RDAM), until Dec 2017.
• with Philip N. Klein and David Eisenstat, (Medium NSF collaborative grant, 0964037), completed
• with Xavier Goaoc and Martin Tancer (bilateral project Embeds), completed.

Highlights 2017

Distributed Weighted All-Pairs Shortest Paths in few Rounds

Chien-Chung Huang, Danupon Nanongkai, and Thatchaphol Saranurak give a fast randomized distributed algorithm for the problem of computing shortest paths between all pairs of vertices of a weighted graph.

Highlights 2016

Local search for k-median in planar graphs and the Euclidean plane

In a collaboration with Philip Klein, Vincent Cohen-Addad and Claire Mathieu prove that local search is a polynomial-time approximation scheme for the k-median problem in planar graphs and the Euclidean plane. Given a collection of clients with distances defined by shortest paths in a planar graph or in the Euclidean plane, the k-median problem consists in selecting positions where to build k facilities so as to minimize the total distance from clients to the nearest facility. Local search iteratively tries to improve the current tentative solution by moving a few facilities around. This is a near-optimal strategy.

Highlights 2015

Homophily and the Glass Ceiling Effect in Social Networks

The glass ceiling effect has been defined in a recent US Federal Commission report as “the unseen, yet unbreakable barrier that keeps minorities and women from rising to the upper rungs of the corporate ladder, regardless of their qualifications or achievements”. It is well documented that many societies and organizations exhibit a glass ceiling.

Claire Mathieu and her collaborators Chen Avin, Barbara Keller, Zvi Lotker, David Peleg, and Yvonne Pignolet have studied this problem in a paper published in ITCS 2015. They formally define and study the glass ceiling effect in social networks and propose a natural mathematical model, called the biased preferential attachment model, that partially explains the causes of the glass ceiling effect. This model consists of a network composed of two types of vertices, representing two sub-populations, and accommodates three well known social phenomena: (i) the “rich get richer” mechanism, (ii) a minority-majority partition, and (iii) homophily. They prove that their model exhibits a strong moment glass ceiling effect and that all three conditions are necessary, i.e., removing any one of them will prevent the appearance of a glass ceiling effect. Additionally, they present empirical evidence taken from a mentor-student network of researchers (derived from the DBLP database) that exhibits both a glass ceiling effect and the above three phenomena.

Coalition games

How much do we have to pay selfish agents to make them work together on a project that needs everyone’s participation? In coalition games, the answer is: enough so that no small group wants to break off on their own to work together on something else that earns more than what they were paid for the project. Which small groups are allowed to break off is determined by a graph of possible communications in the classic model of Myerson.

Zhentao Li and his colleagues Nicolas Bousquet and Adrian Vetta, at the ACM Conference on Economics and Computation, improve the gap between the total payment and the the wealth created by the project in the worst possible game. This is done by introducing a new graph parameter. For all communication graphs, they give examples of games that reach this ratio, showing their result is tight.

Facility location

Where to build fire stations? Given a set of points P in R^d and a building cost, the well-known facility location problem asks for a set S of facilities such that the total building cost plus the sum of the distances of each client to the closest facility in S is minimum.

Vincent Cohen-Addad and Claire Mathieu, in the proceedings of the Symposium on Computational Geometry 2015, analyze the performances of the local search technique -- a popular heuristic for hard optimization problem -- for the facility location problem. Given a feasible solution, the local search algorithm repeatedly performs operations from the given class, so long as each improves the cost of the current solution, until a solution is reached for which no operation yields an improvement. They show that this very simple approach achieves a solution close to the optimum.

Minimum multicut

Given a network, how can we remove a minimum number of connections to separate given pairs of terminals? The minimum multicut problem is known to be NP-hard and inapproximable, even in very simple instances (e.g., when the network is a tree).

Éric Colin de Verdière, at the European Symposium on Algorithms, has shown that the problem was solvable in polynomial time if the number of terminal pairs is bounded and if the graph is planar (or, more generally, drawn without crossings on a fixed surface). In the planar case, the result has been known for more than twenty years in the more restricted multiway cut problem; for the present generalization, techniques from computational topology turn out to be necessary.