The Geodesic Classification Problem on Graphs

Macêdo de Araújo, Paulo; Campêlo, Manoel; Correa, Ricardo; Labbé, Martine

Type de document :

Article dans une revue scientifique: Article original

DOI :

10.1016/j.entcs.2019.08.007

Titre :

The Geodesic Classification Problem on Graphs

Auteur(s) :

Macêdo de Araújo, Paulo [Auteur]
Universidade Federal do Ceará = Federal University of Ceará [UFC]
Campêlo, Manoel [Auteur]
Universidade Federal do Ceará = Federal University of Ceará [UFC]
Correa, Ricardo [Auteur]
Departamento do Computacao [Fortaleza BR]
Labbé, Martine [Auteur]
Integrated Optimization with Complex Structure [INOCS]

Titre de la revue :

Electronic Notes in Theoretical Computer Science

Pagination :

65 - 76

Éditeur :

Elsevier

Date de publication :

2019

ISSN :

1571-0661

Mot(s)-clé(s) en anglais :

Classification
Geodesic Convexity
Integer Linear Programming

Discipline(s) HAL :

Computer Science [cs]/Operations Research [math.OC]

Résumé en anglais : [en]

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 ...
Lire la suite >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.Lire moins >

Langue :

Anglais

Comité de lecture :

Oui

Audience :

Internationale

Vulgarisation :

Non

Collections :

Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL

Fichiers

https://hal.inria.fr/hal-02393316/document
Accès libre
Accéder au document

https://doi.org/10.1016/j.entcs.2019.08.007
Accès libre
Accéder au document

https://doi.org/10.1016/j.entcs.2019.08.007
Accès libre
Accéder au document

https://hal.inria.fr/hal-02393316/document
Accès libre
Accéder au document

https://doi.org/10.1016/j.entcs.2019.08.007
Accès libre
Accéder au document

https://doi.org/10.1016/j.entcs.2019.08.007
Accès libre
Accéder au document

https://hal.inria.fr/hal-02393316/document
Accès libre
Accéder au document

https://doi.org/10.1016/j.entcs.2019.08.007
Accès libre
Accéder au document

https://doi.org/10.1016/j.entcs.2019.08.007
Accès libre
Accéder au document

document
Accès libre
Accéder au document

MacedodeAraujoetal2019.pdf
Accès libre
Accéder au document

j.entcs.2019.08.007
Accès libre
Accéder au document

document
Accès libre
Accéder au document

MacedodeAraujoetal2019.pdf
Accès libre
Accéder au document

The Geodesic Classification Problem on Graphs BibTeX CSV Excel RIS

Fichiers

The Geodesic Classification Problem on Graphs

BibTeX

CSV

Excel

RIS