Skip to Main content Skip to Navigation
Journal articles

The Geodesic Classification Problem on Graphs

Paulo 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é <>
Submitted on : Wednesday, December 4, 2019 - 12:50:00 PM
Last modification on : Friday, December 11, 2020 - 6:44:07 PM
Long-term archiving on: : Thursday, March 5, 2020 - 3:31:40 PM


Files produced by the author(s)




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



Record views


Files downloads