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 (CRIStAL) - 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 metadatas

Cited literature [19 references]  Display  Hide  Download

https://hal.inria.fr/hal-02393316
Contributor : Martine Labbé <>
Submitted on : Wednesday, December 4, 2019 - 12:50:00 PM
Last modification on : Wednesday, June 24, 2020 - 10:48:04 AM
Long-term archiving on: : Thursday, March 5, 2020 - 3:31:40 PM

File

MacedodeAraujoetal2019.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

215

Files downloads

836