Connectedness and Local Search for Bicriteria Knapsack Problems
Identifieur interne : 002727 ( Main/Curation ); précédent : 002726; suivant : 002728Connectedness and Local Search for Bicriteria Knapsack Problems
Auteurs : Arnaud Liefooghe [France] ; Luís Paquete [Portugal] ; Marco Sim Es [Portugal] ; José R. Figueira [France]Source :
- Lecture Notes in Computer Science [ 0302-9743 ]
Abstract
Abstract: This article reports an experimental study on a given structural property of connectedness of optimal solutions for two variants of the bicriteria knapsack problem. A local search algorithm that explores this property is then proposed and its performance is compared against exact algorithms in terms of running time and number of optimal solutions found. The experimental results indicate that this simple local search algorithm is able to find a representative set of optimal solutions in most of the cases, and in much less time than exact approaches.
Url:
- https://api.istex.fr/ark:/67375/HCB-SFW4H26L-1/fulltext.pdf
- https://hal.archives-ouvertes.fr/hal-00575922
DOI: 10.1007/978-3-642-20364-0_5
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: Pour aller vers cette notice dans l'étape Curation :003551
- to stream Istex, to step Curation: Pour aller vers cette notice dans l'étape Curation :003509
- to stream Istex, to step Checkpoint: Pour aller vers cette notice dans l'étape Curation :000627
- to stream Hal, to step Corpus: Pour aller vers cette notice dans l'étape Curation :001838
- to stream Hal, to step Curation: Pour aller vers cette notice dans l'étape Curation :001838
- to stream Hal, to step Checkpoint: Pour aller vers cette notice dans l'étape Curation :001E64
- to stream Main, to step Merge: Pour aller vers cette notice dans l'étape Curation :002769
Links to Exploration step
ISTEX:E06DA8C2C11154A65313AF0DB584658B3D0ACD5DLe document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Connectedness and Local Search for Bicriteria Knapsack Problems</title>
<author><name sortKey="Liefooghe, Arnaud" sort="Liefooghe, Arnaud" uniqKey="Liefooghe A" first="Arnaud" last="Liefooghe">Arnaud Liefooghe</name>
</author>
<author><name sortKey="Paquete, Luis" sort="Paquete, Luis" uniqKey="Paquete L" first="Luís" last="Paquete">Luís Paquete</name>
</author>
<author><name sortKey="Sim Es, Marco" sort="Sim Es, Marco" uniqKey="Sim Es M" first="Marco" last="Sim Es">Marco Sim Es</name>
</author>
<author><name sortKey="Figueira, Jose R" sort="Figueira, Jose R" uniqKey="Figueira J" first="José R." last="Figueira">José R. Figueira</name>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">ISTEX</idno>
<idno type="RBID">ISTEX:E06DA8C2C11154A65313AF0DB584658B3D0ACD5D</idno>
<date when="2011" year="2011">2011</date>
<idno type="doi">10.1007/978-3-642-20364-0_5</idno>
<idno type="url">https://api.istex.fr/ark:/67375/HCB-SFW4H26L-1/fulltext.pdf</idno>
<idno type="wicri:Area/Istex/Corpus">003551</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">003551</idno>
<idno type="wicri:Area/Istex/Curation">003509</idno>
<idno type="wicri:Area/Istex/Checkpoint">000627</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">000627</idno>
<idno type="wicri:doubleKey">0302-9743:2011:Liefooghe A:connectedness:and:local</idno>
<idno type="wicri:source">HAL</idno>
<idno type="RBID">Hal:hal-00575922</idno>
<idno type="url">https://hal.archives-ouvertes.fr/hal-00575922</idno>
<idno type="wicri:Area/Hal/Corpus">001838</idno>
<idno type="wicri:Area/Hal/Curation">001838</idno>
<idno type="wicri:Area/Hal/Checkpoint">001E64</idno>
<idno type="wicri:explorRef" wicri:stream="Hal" wicri:step="Checkpoint">001E64</idno>
<idno type="wicri:Area/Main/Merge">002769</idno>
<idno type="wicri:Area/Main/Curation">002727</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Connectedness and Local Search for Bicriteria Knapsack Problems</title>
<author><name sortKey="Liefooghe, Arnaud" sort="Liefooghe, Arnaud" uniqKey="Liefooghe A" first="Arnaud" last="Liefooghe">Arnaud Liefooghe</name>
<affiliation wicri:level="4"><country xml:lang="fr">France</country>
<wicri:regionArea>LIFL – CNRS – INRIA Lille-Nord Europe, Université Lille 1</wicri:regionArea>
<placeName><settlement type="city">Lille</settlement>
<region type="region" nuts="2">Hauts-de-France</region>
<region type="old region" nuts="2">Nord-Pas-de-Calais</region>
</placeName>
<orgName type="university">Université Lille I - Sciences et technologies</orgName>
<orgName type="institution" wicri:auto="newGroup">Université Lille Nord de France</orgName>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">France</country>
</affiliation>
</author>
<author><name sortKey="Paquete, Luis" sort="Paquete, Luis" uniqKey="Paquete L" first="Luís" last="Paquete">Luís Paquete</name>
<affiliation wicri:level="1"><country xml:lang="fr">Portugal</country>
<wicri:regionArea>CISUC, Department of Informatics Engineering, University of Coimbra</wicri:regionArea>
<wicri:noRegion>University of Coimbra</wicri:noRegion>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">Portugal</country>
</affiliation>
</author>
<author><name sortKey="Sim Es, Marco" sort="Sim Es, Marco" uniqKey="Sim Es M" first="Marco" last="Sim Es">Marco Sim Es</name>
<affiliation wicri:level="1"><country xml:lang="fr">Portugal</country>
<wicri:regionArea>CISUC, Department of Informatics Engineering, University of Coimbra</wicri:regionArea>
<wicri:noRegion>University of Coimbra</wicri:noRegion>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">Portugal</country>
</affiliation>
</author>
<author><name sortKey="Figueira, Jose R" sort="Figueira, Jose R" uniqKey="Figueira J" first="José R." last="Figueira">José R. Figueira</name>
<affiliation wicri:level="1"><country xml:lang="fr">France</country>
<wicri:regionArea>INPL, École des Mines de Nancy, Laboratoire LORIA</wicri:regionArea>
<wicri:noRegion>Laboratoire LORIA</wicri:noRegion>
<wicri:noRegion>Laboratoire LORIA</wicri:noRegion>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">France</country>
</affiliation>
</author>
</analytic>
<monogr></monogr>
<series><title level="s" type="main" xml:lang="en">Lecture Notes in Computer Science</title>
<idno type="ISSN">0302-9743</idno>
<idno type="eISSN">1611-3349</idno>
<idno type="ISSN">0302-9743</idno>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt><idno type="ISSN">0302-9743</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass></textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Abstract: This article reports an experimental study on a given structural property of connectedness of optimal solutions for two variants of the bicriteria knapsack problem. A local search algorithm that explores this property is then proposed and its performance is compared against exact algorithms in terms of running time and number of optimal solutions found. The experimental results indicate that this simple local search algorithm is able to find a representative set of optimal solutions in most of the cases, and in much less time than exact approaches.</div>
</front>
</TEI>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Curation
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 002727 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Curation/biblio.hfd -nk 002727 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Wicri/Lorraine |area= InforLorV4 |flux= Main |étape= Curation |type= RBID |clé= ISTEX:E06DA8C2C11154A65313AF0DB584658B3D0ACD5D |texte= Connectedness and Local Search for Bicriteria Knapsack Problems }}
This area was generated with Dilib version V0.6.33. |