Skip to Main content Skip to Navigation
New interface
Journal articles

The Geodesic Classification Problem on Graphs

Paulo Henrique Macêdo de Araújo 1 Manoel Campêlo 1 Ricardo Correa 2 Martine Labbé 3 
3 INOCS - Integrated Optimization with Complex Structure
Inria Lille - Nord Europe, ULB - Université libre de Bruxelles, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189
Abstract : Motivated by the significant advances in integer optimization in the past decade, Bertsimas and Shioda developed an integer optimization method to the classical statistical problem of classification in a multi-dimensional space, delivering a software package called CRIO (Classification and Regression via Integer Optimization). Following those ideas, we define a new classification problem, exploring its combinatorial aspects. That problem is defined on graphs using the geodesic convexity as an analogy of the Euclidean convexity in the multidimensional space. We denote such a problem by Geodesic Classification (GC) problem. We propose an integer programming formulation for the GC problem along with a branch-and-cut algorithm to solve it. Finally, we show computational experiments in order to evaluate the combinatorial optimization efficiency and classification accuracy of the proposed approach.
Document type :
Journal articles
Complete list of metadata

Cited literature [19 references]  Display  Hide  Download
Contributor : Martine Labbé Connect in order to contact the contributor
Submitted on : Wednesday, December 4, 2019 - 12:50:00 PM
Last modification on : Tuesday, December 6, 2022 - 12:42:13 PM
Long-term archiving on: : Thursday, March 5, 2020 - 3:31:40 PM


Files produced by the author(s)




Paulo Henrique Macêdo de Araújo, Manoel Campêlo, Ricardo Correa, Martine Labbé. The Geodesic Classification Problem on Graphs. Electronic Notes in Theoretical Computer Science, 2019, 346, pp.65 - 76. ⟨10.1016/j.entcs.2019.08.007⟩. ⟨hal-02393316⟩



Record views


Files downloads