Serveur d'exploration sur la visibilité du Havre

Attention, ce site est en cours de développement !
Attention, site généré par des moyens informatiques à partir de corpus bruts.
Les informations ne sont donc pas validées.

Une approche polyédrale pour le K-partitionnement de graphe appliqué à l'analyse de dialogue

Identifieur interne : 000775 ( Hal/Corpus ); précédent : 000774; suivant : 000776

Une approche polyédrale pour le K-partitionnement de graphe appliqué à l'analyse de dialogue

Auteurs : Zacharie Ales ; Arnaud Knippel ; Alexandre Pauchet

Source :

RBID : Hal:hal-00946469

Descripteurs français

Abstract

Nous nous intéressons à un problème de K-partitionnement pour des
applications en analyse de dialogues. Les sommets du graphe
correspondent à des motifs qui ont été déterminés lors d'une phase
préalable. Nous cherchons à partitionner ces motifs en K parties tout
en minimisant une fonction linéaire des coûts associés aux arêtes à
l'intérieur des clusters.

Nous nous basons sur une formulation contenant des variables d'arêtes
et de représentants. Ces dernières indiquent pour chaque partie quel
est le sommet de plus petit indice.

Nous montrons que la dimension du polyèdre correspondant dépend du
paramètre K. Dans le cas général où le polyèdre est de dimension
pleine, nous identifions les inégalités de la formulation définissant
des facettes. Nous avons, de plus, étudié trois familles d'inégalités
(les inégalités de 2-partitions, les inégalités "two-chorded cycle"
ainsi que les inégalités d'ensembles dépendants) et identifié les cas
où ces dernières définissent des facettes. Nous montrons, par la
suite, que les inégalités triangulaires qui ne définissent pas des
facettes peuvent être renforcées en y ajoutant une variable de
représentants.

Nous illustrons leur efficacité par des résultats numériques.


Url:

Links to Exploration step

Hal:hal-00946469

Le document en format XML

<record>
<TEI>
<teiHeader>
<fileDesc>
<titleStmt>
<title xml:lang="fr">Une approche polyédrale pour le K-partitionnement de graphe appliqué à l'analyse de dialogue</title>
<author>
<name sortKey="Ales, Zacharie" sort="Ales, Zacharie" uniqKey="Ales Z" first="Zacharie" last="Ales">Zacharie Ales</name>
<affiliation>
<hal:affiliation type="laboratory" xml:id="struct-23832" status="VALID">
<orgName>Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes</orgName>
<orgName type="acronym">LITIS</orgName>
<desc>
<address>
<addrLine>Avenue de l'Université UFR des Sciences et Techniques 76800 Saint-Etienne du Rouvray</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.litislab.eu</ref>
</desc>
<listRelation>
<relation active="#struct-300317" type="direct"></relation>
<relation name="EA4108" active="#struct-300318" type="direct"></relation>
<relation active="#struct-301288" type="direct"></relation>
<relation active="#struct-301232" type="indirect"></relation>
</listRelation>
<tutelles>
<tutelle active="#struct-300317" type="direct">
<org type="institution" xml:id="struct-300317" status="VALID">
<orgName>Université du Havre</orgName>
<desc>
<address>
<country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle name="EA4108" active="#struct-300318" type="direct">
<org type="institution" xml:id="struct-300318" status="VALID">
<orgName>Université de Rouen</orgName>
<desc>
<address>
<addrLine> 1 rue Thomas Becket - 76821 Mont-Saint-Aignan</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.univ-rouen.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-301288" type="direct">
<org type="department" xml:id="struct-301288" status="VALID">
<orgName>Institut National des Sciences Appliquées - Rouen</orgName>
<orgName type="acronym">INSA Rouen</orgName>
<desc>
<address>
<country key="FR"></country>
</address>
</desc>
<listRelation>
<relation active="#struct-301232" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-301232" type="indirect">
<org type="institution" xml:id="struct-301232" status="VALID">
<orgName>Institut National des Sciences Appliquées</orgName>
<orgName type="acronym">INSA</orgName>
<desc>
<address>
<country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
</affiliation>
</author>
<author>
<name sortKey="Knippel, Arnaud" sort="Knippel, Arnaud" uniqKey="Knippel A" first="Arnaud" last="Knippel">Arnaud Knippel</name>
<affiliation>
<hal:affiliation type="laboratory" xml:id="struct-90" status="VALID">
<orgName>Laboratoire de Mathématique de l'INSA de Rouen</orgName>
<orgName type="acronym">LMI</orgName>
<desc>
<address>
<addrLine>Normandie Université, INSA de ROUEN, LMI, Av. de l'Université, BP 08, 76801 St Etienne du Rouvray cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://lmi.insa-rouen.fr/</ref>
</desc>
<listRelation>
<relation active="#struct-358441" type="direct"></relation>
</listRelation>
<tutelles>
<tutelle active="#struct-358441" type="direct">
<org type="institution" xml:id="struct-358441" status="INCOMING">
<orgName>Institut National des Sciences Appliquées [INSA] - Rouen : EA3226</orgName>
<desc>
<address>
<country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
</affiliation>
</author>
<author>
<name sortKey="Pauchet, Alexandre" sort="Pauchet, Alexandre" uniqKey="Pauchet A" first="Alexandre" last="Pauchet">Alexandre Pauchet</name>
<affiliation>
<hal:affiliation type="laboratory" xml:id="struct-23832" status="VALID">
<orgName>Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes</orgName>
<orgName type="acronym">LITIS</orgName>
<desc>
<address>
<addrLine>Avenue de l'Université UFR des Sciences et Techniques 76800 Saint-Etienne du Rouvray</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.litislab.eu</ref>
</desc>
<listRelation>
<relation active="#struct-300317" type="direct"></relation>
<relation name="EA4108" active="#struct-300318" type="direct"></relation>
<relation active="#struct-301288" type="direct"></relation>
<relation active="#struct-301232" type="indirect"></relation>
</listRelation>
<tutelles>
<tutelle active="#struct-300317" type="direct">
<org type="institution" xml:id="struct-300317" status="VALID">
<orgName>Université du Havre</orgName>
<desc>
<address>
<country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle name="EA4108" active="#struct-300318" type="direct">
<org type="institution" xml:id="struct-300318" status="VALID">
<orgName>Université de Rouen</orgName>
<desc>
<address>
<addrLine> 1 rue Thomas Becket - 76821 Mont-Saint-Aignan</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.univ-rouen.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-301288" type="direct">
<org type="department" xml:id="struct-301288" status="VALID">
<orgName>Institut National des Sciences Appliquées - Rouen</orgName>
<orgName type="acronym">INSA Rouen</orgName>
<desc>
<address>
<country key="FR"></country>
</address>
</desc>
<listRelation>
<relation active="#struct-301232" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-301232" type="indirect">
<org type="institution" xml:id="struct-301232" status="VALID">
<orgName>Institut National des Sciences Appliquées</orgName>
<orgName type="acronym">INSA</orgName>
<desc>
<address>
<country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
</affiliation>
</author>
</titleStmt>
<publicationStmt>
<idno type="wicri:source">HAL</idno>
<idno type="RBID">Hal:hal-00946469</idno>
<idno type="halId">hal-00946469</idno>
<idno type="halUri">https://hal.archives-ouvertes.fr/hal-00946469</idno>
<idno type="url">https://hal.archives-ouvertes.fr/hal-00946469</idno>
<date when="2014-02-26">2014-02-26</date>
<idno type="wicri:Area/Hal/Corpus">000775</idno>
</publicationStmt>
<sourceDesc>
<biblStruct>
<analytic>
<title xml:lang="fr">Une approche polyédrale pour le K-partitionnement de graphe appliqué à l'analyse de dialogue</title>
<author>
<name sortKey="Ales, Zacharie" sort="Ales, Zacharie" uniqKey="Ales Z" first="Zacharie" last="Ales">Zacharie Ales</name>
<affiliation>
<hal:affiliation type="laboratory" xml:id="struct-23832" status="VALID">
<orgName>Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes</orgName>
<orgName type="acronym">LITIS</orgName>
<desc>
<address>
<addrLine>Avenue de l'Université UFR des Sciences et Techniques 76800 Saint-Etienne du Rouvray</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.litislab.eu</ref>
</desc>
<listRelation>
<relation active="#struct-300317" type="direct"></relation>
<relation name="EA4108" active="#struct-300318" type="direct"></relation>
<relation active="#struct-301288" type="direct"></relation>
<relation active="#struct-301232" type="indirect"></relation>
</listRelation>
<tutelles>
<tutelle active="#struct-300317" type="direct">
<org type="institution" xml:id="struct-300317" status="VALID">
<orgName>Université du Havre</orgName>
<desc>
<address>
<country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle name="EA4108" active="#struct-300318" type="direct">
<org type="institution" xml:id="struct-300318" status="VALID">
<orgName>Université de Rouen</orgName>
<desc>
<address>
<addrLine> 1 rue Thomas Becket - 76821 Mont-Saint-Aignan</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.univ-rouen.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-301288" type="direct">
<org type="department" xml:id="struct-301288" status="VALID">
<orgName>Institut National des Sciences Appliquées - Rouen</orgName>
<orgName type="acronym">INSA Rouen</orgName>
<desc>
<address>
<country key="FR"></country>
</address>
</desc>
<listRelation>
<relation active="#struct-301232" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-301232" type="indirect">
<org type="institution" xml:id="struct-301232" status="VALID">
<orgName>Institut National des Sciences Appliquées</orgName>
<orgName type="acronym">INSA</orgName>
<desc>
<address>
<country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
</affiliation>
</author>
<author>
<name sortKey="Knippel, Arnaud" sort="Knippel, Arnaud" uniqKey="Knippel A" first="Arnaud" last="Knippel">Arnaud Knippel</name>
<affiliation>
<hal:affiliation type="laboratory" xml:id="struct-90" status="VALID">
<orgName>Laboratoire de Mathématique de l'INSA de Rouen</orgName>
<orgName type="acronym">LMI</orgName>
<desc>
<address>
<addrLine>Normandie Université, INSA de ROUEN, LMI, Av. de l'Université, BP 08, 76801 St Etienne du Rouvray cedex</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://lmi.insa-rouen.fr/</ref>
</desc>
<listRelation>
<relation active="#struct-358441" type="direct"></relation>
</listRelation>
<tutelles>
<tutelle active="#struct-358441" type="direct">
<org type="institution" xml:id="struct-358441" status="INCOMING">
<orgName>Institut National des Sciences Appliquées [INSA] - Rouen : EA3226</orgName>
<desc>
<address>
<country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
</affiliation>
</author>
<author>
<name sortKey="Pauchet, Alexandre" sort="Pauchet, Alexandre" uniqKey="Pauchet A" first="Alexandre" last="Pauchet">Alexandre Pauchet</name>
<affiliation>
<hal:affiliation type="laboratory" xml:id="struct-23832" status="VALID">
<orgName>Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes</orgName>
<orgName type="acronym">LITIS</orgName>
<desc>
<address>
<addrLine>Avenue de l'Université UFR des Sciences et Techniques 76800 Saint-Etienne du Rouvray</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.litislab.eu</ref>
</desc>
<listRelation>
<relation active="#struct-300317" type="direct"></relation>
<relation name="EA4108" active="#struct-300318" type="direct"></relation>
<relation active="#struct-301288" type="direct"></relation>
<relation active="#struct-301232" type="indirect"></relation>
</listRelation>
<tutelles>
<tutelle active="#struct-300317" type="direct">
<org type="institution" xml:id="struct-300317" status="VALID">
<orgName>Université du Havre</orgName>
<desc>
<address>
<country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
<tutelle name="EA4108" active="#struct-300318" type="direct">
<org type="institution" xml:id="struct-300318" status="VALID">
<orgName>Université de Rouen</orgName>
<desc>
<address>
<addrLine> 1 rue Thomas Becket - 76821 Mont-Saint-Aignan</addrLine>
<country key="FR"></country>
</address>
<ref type="url">http://www.univ-rouen.fr/</ref>
</desc>
</org>
</tutelle>
<tutelle active="#struct-301288" type="direct">
<org type="department" xml:id="struct-301288" status="VALID">
<orgName>Institut National des Sciences Appliquées - Rouen</orgName>
<orgName type="acronym">INSA Rouen</orgName>
<desc>
<address>
<country key="FR"></country>
</address>
</desc>
<listRelation>
<relation active="#struct-301232" type="direct"></relation>
</listRelation>
</org>
</tutelle>
<tutelle active="#struct-301232" type="indirect">
<org type="institution" xml:id="struct-301232" status="VALID">
<orgName>Institut National des Sciences Appliquées</orgName>
<orgName type="acronym">INSA</orgName>
<desc>
<address>
<country key="FR"></country>
</address>
</desc>
</org>
</tutelle>
</tutelles>
</hal:affiliation>
</affiliation>
</author>
</analytic>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc>
<textClass>
<keywords scheme="mix" xml:lang="fr">
<term>Approche polyédrale</term>
<term>partitionnement de graphe</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front>
<div type="abstract" xml:lang="fr">

Nous nous intéressons à un problème de K-partitionnement pour des
applications en analyse de dialogues. Les sommets du graphe
correspondent à des motifs qui ont été déterminés lors d'une phase
préalable. Nous cherchons à partitionner ces motifs en K parties tout
en minimisant une fonction linéaire des coûts associés aux arêtes à
l'intérieur des clusters.

Nous nous basons sur une formulation contenant des variables d'arêtes
et de représentants. Ces dernières indiquent pour chaque partie quel
est le sommet de plus petit indice.

Nous montrons que la dimension du polyèdre correspondant dépend du
paramètre K. Dans le cas général où le polyèdre est de dimension
pleine, nous identifions les inégalités de la formulation définissant
des facettes. Nous avons, de plus, étudié trois familles d'inégalités
(les inégalités de 2-partitions, les inégalités "two-chorded cycle"
ainsi que les inégalités d'ensembles dépendants) et identifié les cas
où ces dernières définissent des facettes. Nous montrons, par la
suite, que les inégalités triangulaires qui ne définissent pas des
facettes peuvent être renforcées en y ajoutant une variable de
représentants.

Nous illustrons leur efficacité par des résultats numériques.

</div>
</front>
</TEI>
<hal api="V3">
<titleStmt>
<title xml:lang="fr">Une approche polyédrale pour le K-partitionnement de graphe appliqué à l'analyse de dialogue</title>
<author role="aut">
<persName>
<forename type="first">Zacharie</forename>
<surname>ALES</surname>
</persName>
<email>zacharie.ales@insa-rouen.fr</email>
<idno type="idhal">zacharie-ales</idno>
<idno type="halauthor">985041</idno>
<idno type="ORCID">http://orcid.org/0000-0003-4602-2638</idno>
<affiliation ref="#struct-23832"></affiliation>
<affiliation ref="#struct-90"></affiliation>
</author>
<author role="crp">
<persName>
<forename type="first">Arnaud</forename>
<surname>KNIPPEL</surname>
</persName>
<email>arnaud.knippel@insa-rouen.fr</email>
<ptr type="url" target="http://lmi.insa-rouen.fr/membres/25-lknippel.html"></ptr>
<idno type="halauthor">984654</idno>
<affiliation ref="#struct-90"></affiliation>
</author>
<author role="crp">
<persName>
<forename type="first">Alexandre</forename>
<surname>PAUCHET</surname>
</persName>
<email>alexandre.pauchet@insa-rouen.fr</email>
<ptr type="url" target="http://asi.insa-rouen.fr/enseignants/~apauchet/"></ptr>
<idno type="halauthor">985042</idno>
<affiliation ref="#struct-23832"></affiliation>
</author>
<editor role="depositor">
<persName>
<forename>Martine</forename>
<surname>Courbin-Coulaud</surname>
</persName>
<email>martine.courbin@inria.fr</email>
</editor>
</titleStmt>
<editionStmt>
<edition n="v1" type="current">
<date type="whenSubmitted">2014-02-13 16:08:30</date>
<date type="whenWritten">2014</date>
<date type="whenModified">2016-02-09 20:19:15</date>
<date type="whenReleased">2014-02-13 16:08:30</date>
<date type="whenProduced">2014-02-26</date>
</edition>
<respStmt>
<resp>contributor</resp>
<name key="100380">
<persName>
<forename>Martine</forename>
<surname>Courbin-Coulaud</surname>
</persName>
<email>martine.courbin@inria.fr</email>
</name>
</respStmt>
</editionStmt>
<publicationStmt>
<distributor>CCSD</distributor>
<idno type="halId">hal-00946469</idno>
<idno type="halUri">https://hal.archives-ouvertes.fr/hal-00946469</idno>
<idno type="halBibtex">ales:hal-00946469</idno>
<idno type="halRefHtml">ROADEF - 15ème congrès annuel de la Société française de recherche opérationnelle et d'aide à la décision, Feb 2014, Bordeaux, France</idno>
<idno type="halRef">ROADEF - 15ème congrès annuel de la Société française de recherche opérationnelle et d'aide à la décision, Feb 2014, Bordeaux, France</idno>
</publicationStmt>
<seriesStmt>
<idno type="stamp" n="ROADEF-2014">ROADEF 2014 - 15ème congrès annuel de la Société française de recherche opérationnelle et d'aide à la décision</idno>
<idno type="stamp" n="LITIS">Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes</idno>
<idno type="stamp" n="LMI-ROUEN">Laboratoire de Mathématiques de l'INSA Rouen - Normandie Université - INSA Rouen</idno>
</seriesStmt>
<notesStmt>
<note type="audience" n="2">International</note>
<note type="invited" n="0">No</note>
<note type="popular" n="0">No</note>
<note type="peer" n="1">Yes</note>
<note type="proceedings" n="0">No</note>
</notesStmt>
<sourceDesc>
<biblStruct>
<analytic>
<title xml:lang="fr">Une approche polyédrale pour le K-partitionnement de graphe appliqué à l'analyse de dialogue</title>
<author role="aut">
<persName>
<forename type="first">Zacharie</forename>
<surname>ALES</surname>
</persName>
<email>zacharie.ales@insa-rouen.fr</email>
<idno type="idHal">zacharie-ales</idno>
<idno type="halAuthorId">985041</idno>
<idno type="ORCID">http://orcid.org/0000-0003-4602-2638</idno>
<affiliation ref="#struct-23832"></affiliation>
<affiliation ref="#struct-90"></affiliation>
</author>
<author role="crp">
<persName>
<forename type="first">Arnaud</forename>
<surname>KNIPPEL</surname>
</persName>
<email>arnaud.knippel@insa-rouen.fr</email>
<ptr type="url" target="http://lmi.insa-rouen.fr/membres/25-lknippel.html"></ptr>
<idno type="halAuthorId">984654</idno>
<affiliation ref="#struct-90"></affiliation>
</author>
<author role="crp">
<persName>
<forename type="first">Alexandre</forename>
<surname>PAUCHET</surname>
</persName>
<email>alexandre.pauchet@insa-rouen.fr</email>
<ptr type="url" target="http://asi.insa-rouen.fr/enseignants/~apauchet/"></ptr>
<idno type="halAuthorId">985042</idno>
<affiliation ref="#struct-23832"></affiliation>
</author>
</analytic>
<monogr>
<idno type="localRef">Approches polyédrales, formulations étendues et décomposition en programmation entière</idno>
<meeting>
<title>ROADEF - 15ème congrès annuel de la Société française de recherche opérationnelle et d'aide à la décision</title>
<date type="start">2014-02-26</date>
<date type="end">2014-02-28</date>
<settlement>Bordeaux</settlement>
<country key="FR">France</country>
</meeting>
<respStmt>
<resp>conferenceOrganizer</resp>
<name>Société française de recherche opérationnelle et d'aide à la décision</name>
</respStmt>
<imprint></imprint>
</monogr>
</biblStruct>
</sourceDesc>
<profileDesc>
<langUsage>
<language ident="fr">French</language>
</langUsage>
<textClass>
<keywords scheme="author">
<term xml:lang="fr">Approche polyédrale</term>
<term xml:lang="fr">partitionnement de graphe</term>
</keywords>
<classCode scheme="halDomain" n="info.info-ro">Computer Science [cs]/Operations Research [cs.RO]</classCode>
<classCode scheme="halTypology" n="COMM">Conference papers</classCode>
</textClass>
<abstract xml:lang="fr">

Nous nous intéressons à un problème de K-partitionnement pour des
applications en analyse de dialogues. Les sommets du graphe
correspondent à des motifs qui ont été déterminés lors d'une phase
préalable. Nous cherchons à partitionner ces motifs en K parties tout
en minimisant une fonction linéaire des coûts associés aux arêtes à
l'intérieur des clusters.

Nous nous basons sur une formulation contenant des variables d'arêtes
et de représentants. Ces dernières indiquent pour chaque partie quel
est le sommet de plus petit indice.

Nous montrons que la dimension du polyèdre correspondant dépend du
paramètre K. Dans le cas général où le polyèdre est de dimension
pleine, nous identifions les inégalités de la formulation définissant
des facettes. Nous avons, de plus, étudié trois familles d'inégalités
(les inégalités de 2-partitions, les inégalités "two-chorded cycle"
ainsi que les inégalités d'ensembles dépendants) et identifié les cas
où ces dernières définissent des facettes. Nous montrons, par la
suite, que les inégalités triangulaires qui ne définissent pas des
facettes peuvent être renforcées en y ajoutant une variable de
représentants.

Nous illustrons leur efficacité par des résultats numériques.

</abstract>
</profileDesc>
</hal>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/France/explor/LeHavreV1/Data/Hal/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000775 | SxmlIndent | more

Ou

HfdSelect -h $EXPLOR_AREA/Data/Hal/Corpus/biblio.hfd -nk 000775 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/France
   |area=    LeHavreV1
   |flux=    Hal
   |étape=   Corpus
   |type=    RBID
   |clé=     Hal:hal-00946469
   |texte=   Une approche polyédrale pour le K-partitionnement de graphe appliqué à l'analyse de dialogue
}}

Wicri

This area was generated with Dilib version V0.6.25.
Data generation: Sat Dec 3 14:37:02 2016. Site generation: Tue Mar 5 08:25:07 2024