ACRO : Algorithmique, Combinatoire et Recherche Opérationnelle

Mots clés

Graphes, combinatoire des familles structurées d’ensembles, distances, théorie métrique des graphes, algorithmes, algorithmes d’approximation, algorithmes géométriques, optimisation combinatoire, multiflots, couverture et packing, classification

 

Responsable

Victor CHEPOI

 

Membres permanents

BARBANCHON RégisMaitre de Conférences
Courriel : regis.barbanchon@lis-lab.fr
Telephone : 0486090453
BERNARD FichetMaitre de Conférences
Courriel : bernard.fichet@lis-lab.fr
BRUCKER FrancoisProfesseur des Universités
Courriel : francois.brucker@lis-lab.fr
Telephone : 0486090486
CHEPOI VictorProfesseur des Universités
Courriel : victor.chepoi@lis-lab.fr
Telephone : 0486090459
Page personnelle : https://pageperso.lis-lab.fr/victor.chepoi/
COUETOUX BasileMaitre de Conférences
Courriel : basile.couetoux@lis-lab.fr
Telephone : 0486090461
Page personnelle : https://pageperso.lis-lab.fr/basile.couetoux/
ESTELLON BertrandMaitre de Conférences
Courriel : bertrand.estellon@lis-lab.fr
Telephone : 0486090465
Page personnelle : https://pageperso.lis-lab.fr/bertrand.estellon/
DIAS DA FONSECA GuilhermeProfesseur des Universités
Courriel : guilherme.fonseca@lis-lab.fr
GAMBINI IanMaitre de Conférences
Courriel : ian.gambini@lis-lab.fr
Telephone : 0442913422
KNAUER KoljaMaitre de Conférences
Courriel : kolja.knauer@lis-lab.fr
Telephone : 0486090476
Page personnelle : https://pageperso.lis-lab.fr/kolja.knauer/
MASSAT Jean-LucMaitre de Conférences
Courriel : jean-luc.massat@lis-lab.fr
Telephone : 0486090488
Page personnelle : https://pageperso.lis-lab.fr/jean-luc.massat/
NAVES GuyslainMaitre de Conférences
Courriel : guyslain.naves@lis-lab.fr
Telephone : 0486090492
Page personnelle : https://pageperso.lis-lab.fr/guyslain.naves/
NOUIOUA KarimMaitre de Conférences
Courriel : karim.nouioua@lis-lab.fr
Telephone : 0486090494
Page personnelle : https://pageperso.lis-lab.fr/karim.nouioua/
PRÉA PascalMaitre de Conférences
Courriel : pascal.prea@lis-lab.fr
Telephone : 0486090486
THIEL ÉdouardProfesseur des Universités
Courriel : edouard.thiel@lis-lab.fr
Telephone : 0486090682
Page personnelle : https://pageperso.lis-lab.fr/edouard.thiel/
VALICOV PetruMaitre de Conférences
Courriel : petru.valicov@lis-lab.fr
Telephone : 0486090683
Page personnelle : https://pageperso.lis-lab.fr/petru.valicov/
VAXES YannProfesseur des Universités
Courriel : yann.vaxes@lis-lab.fr
Telephone : 0486090684
Page personnelle : https://pageperso.lis-lab.fr/yann.vaxes/

 

Doctorants

ATIGHEHCHI KevinATER
Courriel : kevin.atighehchi@lis-lab.fr
Telephone : 0486090483
CHATEL CéliaDoctorant
Courriel : celia.chatel@lis-lab.fr
Telephone : 0491829070
Page personnelle : https://pageperso.lis-lab.fr/celia.chatel/
PHILIBERT ManonDoctorant
Courriel : manon.philibert@lis-lab.fr
RATEL SébastienDoctorant
Courriel : sebastien.ratel@lis-lab.fr
Telephone : 0486090481
Page personnelle : https://pageperso.lis-lab.fr/sebastien.ratel/

 

Autres membres

 

Objectif scientifique

Les activités de l’équipe Algorithmique, Combinatoire et Recherche Opérationnelle concernent l’étude des propriétés structurelles, de la combinatoire, de la géométrie, de l’algorithmique des structures discrètes (graphes et réseaux, distances, complexes cubiques et simpliciaux, familles d’ensembles, structures d’événements), ainsi que l’étude de problèmes d’optimisation combinatoire et en nombres entiers.

Ses travaux recherches s’articulent autour des cinq thèmes suivants :

  • Combinatoire, graphes et distances ;
  • Algorithmique des graphes et réseaux, algorithmes d’approximation ;
  • Recherche Opérationnelle ;
  • Géométrie discrète et algorithmique ;
  • Sériation et classification.

L’équipe ACRO fait partie du pôle « Calcul ». Ses thèmes de recherche contribuent à l’axe ASD–« Algorithmique et Structures Discrètes » de ce pôle. Une partie des travaux issus du thème “Combinatoire, graphes et distances” et une majorité des travaux issus du thème « Géométrie discrète et algorithmique » contribuent aussi à l’axe GTC–“Géométrie et Topologie pour le Calcul”. De façon plus occasionnelle, nous allons travailler sur des problématiques issues d’autres axes du pôle « Calcul », ainsi que d’autres pôles du laboratoire. Cela permettra d’enrichir nos thèmes de recherche et de trouver de nouvelles applications de nos compétences en combinatoire, théorie des graphes, algorithmique, optimisation combinatoire, et classification. Cela nous permettra également de maintenir nos collaborations avec les équipes DALGO et MOVE, et de débuter de nouvelles collaborations avec d’autres équipes du pôle.

Des membres de l’équipe participent ou ont participé aux projets ANR suivants :

  • DISTANCIA « Metric Graph Theory » (2018-2021)
  • CAPPS « Combinatorial Analysis of Polytopes and Polyhedral Subdivisions » (2018-2021)
  • GATO « Graphes Algorithmes et TOpologie » (2016-2020)
  • GGAA « Aspects Géométriques, Analytiques et Algorithmiques des Groupes » (2010-2014)
  • TEOMATRO « Nouvelles Tendances dans les Matroides : Polytopes des bases, Structures, Algorithmes et Interactions » (2010-2013)
  • BOOLE « Quantifying Boolean Frameworks » (2009-2013)
  • ENUM « Algorithmes et complexité pour l’énumération » (2007-2011)
  • OPTICOMB « Optimisation Combinatoire » (2006-2010)

 

Publications récentes de l’équipe



25 documents

Article dans une revue

  • Jérémie Chalopin, Victor Chepoi, Feodor Dragan, Guillaume Ducoffe, Abdulhakeem Mohammed, et al.. Fast Approximation and Exact Computation of Negative Curvature Parameters of Graphs. Discrete and Computational Geometry, Springer Verlag, In press, ⟨10.1007/s00454-019-00107-9⟩. ⟨hal-02149991⟩
  • Jérémie Chalopin, Victor Chepoi. 1-Safe Petri nets and special cube complexes: equivalence and applications. ACM Transactions on Computational Logic, Association for Computing Machinery, 2019, 20 (3), pp.17:1-17:49. ⟨10.1145/3322095⟩. ⟨hal-01863455v2⟩
  • Victor Chepoi, Feodor Dragan, Michel Habib, Yann Vaxès, Hend Alrasheed. Fast approximation of eccentricities and distances in hyperbolic graphs. Journal of Graph Algorithms and Applications (JGAA), Brown University, 2019, 23 (2), pp.393-433. ⟨10.7155/jgaa.00496⟩. ⟨hal-02268471⟩
  • François Brucker, Pascal Prea, Célia Châtel. Totally Balanced Dissimilarities. Journal of Classification, Springer Verlag, 2019, ⟨10.1007/s00357-019-09320-w⟩. ⟨hal-02269391⟩
  • Hans-Jürgen Bandelt, Victor Chepoi, Kolja Knauer. COMs: Complexes of oriented matroids. Journal of Combinatorial Theory, Series A, Elsevier, 2018, 156, pp.195-237. ⟨10.1016/j.jcta.2018.01.002⟩. ⟨hal-02268709⟩
  • Victor Chepoi, Arnaud Labourel, Sébastien Ratel. On density of subgraphs of halved cubes. European Journal of Combinatorics, Elsevier, 2018. ⟨hal-01959093⟩
  • Jérémie Chalopin, Victor Chepoi, Hirai Hiroshi, Damian Osajda. Weakly modular graphs and nonpositive curvature. Memoirs of the American Mathematical Society, American Mathematical Society, In press. ⟨hal-01787197⟩
  • Victor Chepoi. Distance-Preserving Subgraphs of Johnson Graphs. Combinatorica, Springer Verlag, 2017, 37 (6), pp.1039-1055. ⟨10.1007/s00493-016-3421-y⟩. ⟨hal-02268710⟩
  • Victor Chepoi, Bertrand Estellon, Guyslain Naves. Packing and Covering with Balls on Busemann Surfaces. Discrete and Computational Geometry, Springer Verlag, 2017, 57 (4), pp.985-1011. ⟨10.1007/s00454-017-9872-0⟩. ⟨hal-02268712⟩
  • Nicolas Catusse, Victor Chepoi, Karim Nouioua, Yann Vaxès. Bidirected minimum Manhattan network problem. Networks, Wiley, 2017, 69 (2), pp.167-178. ⟨10.1002/net.21719⟩. ⟨hal-02268714⟩
  • Ian Gambini, Laurent Vuillon. Tiling the Space by Polycube Analogues of Fedorov’s Polyhedra. Fundamenta Informaticae, Polskie Towarzystwo Matematyczne, 2016, 146 (2), pp.197-209. ⟨10.3233/FI-2016-1381⟩. ⟨hal-02269399⟩
  • Hans-Jürgen Bandelt, Victor Chepoi, David Eppstein. Ramified Rectilinear Polygons: Coordinatization by Dendrons. Discrete and Computational Geometry, Springer Verlag, 2015, 54 (4), pp.771-797. ⟨10.1007/s00454-015-9743-5⟩. ⟨hal-02268742⟩
  • Jérémie Chalopin, Victor Chepoi, Damian Osajda. On two conjectures of Maurer concerning basis graphs of matroids. Journal of Combinatorial Theory, Series B, Elsevier, 2015, 114, pp.1-32. ⟨10.1016/j.jctb.2015.03.004⟩. ⟨hal-02065778⟩
  • Jérémie Chalopin, Victor Chepoi, Guyslain Naves. Isometric Embedding of Busemann Surfaces into $$L_1$$ L 1. Discrete and Computational Geometry, Springer Verlag, 2015, 53 (1), pp.16-37. ⟨10.1007/s00454-014-9643-0⟩. ⟨hal-02268738⟩
  • Victor Chepoi, Damian Osajda. Dismantlability of weakly systolic complexes and applications. Transactions of the American Mathematical Society, American Mathematical Society, 2015, 367, pp.1247-1272. ⟨hal-01199906⟩

Communication dans un congrès

  • Victor Chepoi, Arnaud Labourel, Sébastien Ratel. Distance and routing labeling schemes for cube-free median graphs. 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019), 2019, Aachen, Germany. pp.15:1--15:14, ⟨10.4230/LIPIcs.MFCS.2019.15⟩. ⟨hal-02268771⟩
  • Jérémie Chalopin, Victor Chepoi, Shay Moran, Manfred Warmuth. Unlabeled Sample Compression Schemes and Corner Peelings for Ample and Maximum Classes. 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), 2019, Patras, Greece. pp.34:1--34:15, ⟨10.4230/LIPIcs.ICALP.2019.34⟩. ⟨hal-02269141⟩
  • Victor Chepoi, Feodor Dragan, Michel Habib, Yann Vaxès, Hend Alrasheed. Fast Approximation of Centrality and Distances in Hyperbolic Graphs. COCOA 2018 - 12th Annual International Conference on Combinatorial Optimization and Applications, Dec 2018, Atlanta, United States. pp.1-23. ⟨hal-01955263⟩
  • Jérémie Chalopin, Victor Chepoi, Feodor Dragan, Guillaume Ducoffe, Abdulhakeem Mohammed, et al.. Fast Approximation and Exact Computation of Negative Curvature Parameters of Graphs. 34th International Symposium on Computational Geometry (SoCG 2018), Jun 2018, Budapest, Hungary. pp.22, ⟨10.4230/LIPIcs.SoCG.2018.22⟩. ⟨hal-01836063⟩
  • Jérémie Chalopin, Victor Chepoi. A Counterexample to Thiagarajan's Conjecture on Regular Event Structures. ICALP 2017, 2017, Warsaw, Poland. ⟨10.4230/LIPIcs.ICALP.2017.101⟩. ⟨hal-01787205⟩
  • Victor Chepoi, Feodor Dragan, Yann Vaxès. Core congestion is inherent in hyperbolic networks. Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017, Barcelona, Spain. pp.2264-2279. ⟨hal-02268729⟩

Pré-publication, Document de travail

  • Victor Chepoi, Kolja Knauer, Manon Philibert. Two-dimensional partial cubes. 2019. ⟨hal-02268768⟩
  • Jérémie Chalopin, Victor Chepoi, Shay Moran, Manfred K. Warmuth. Unlabeled sample compression schemes and corner peelings for ample and maximum classes. 2019. ⟨hal-02065772⟩
  • Victor Chepoi, Kolja Knauer, Tilen Marc. Partial cubes without $Q_3^-$ minors. 2019. ⟨hal-02065775⟩
  • Jérémie Chalopin, Victor Chepoi, Feodor F. Dragan, Guillaume Ducoffe, Abdulhakeem Mohammed, et al.. Fast approximation and exact computation of negative curvature parameters of graphs. 2018. ⟨hal-01737445⟩