Show simple item record

hal.structure.identifier
dc.contributor.authorUchoa, Eduardo*
hal.structure.identifier
dc.contributor.authorSimonetti, Luidi*
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorMahjoub, Ali Ridha*
dc.date.accessioned2012-07-18T15:36:38Z
dc.date.available2012-07-18T15:36:38Z
dc.date.issued2012
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/9768
dc.language.isoenen
dc.subjectFlowen
dc.subjectSurvivable Networken
dc.subjectHop-constrainten
dc.subject.ddc4en
dc.titleHop-Level Flow Formulation for the Hop Constrained Survivable Network Design Problemen
dc.typeCommunication / Conférence
dc.contributor.editoruniversityotherUniversidade Federal Fluminense;Italie
dc.description.abstractenThe HSNDP consists in finding a minimum cost subgraph containing K edge-disjoint paths with length at most H joining each pair of vertices in a given demand set. The only formulation found in the literature that is valid for any K and any H is based on multi-commodity flows over suitable layered graphs (Hop-MCF) and has typical integrality gaps in the range of 5% to 25%. We propose a new formulation called Hop-Level-MCF (in this short paper only for the rooted demands case), having about H times more variables and constraints than Hop-MCF, but being significantly stronger. Typical gaps for rooted instances are between 0% and 6%. Some instances from the literature are solved for the first time.en
dc.identifier.citationpages176-181en
dc.relation.ispartofseriestitleLecture Notes in Computer Science
dc.relation.ispartofseriesnumber6701/2012
dc.relation.ispartoftitleNetwork Optimizationen
dc.relation.ispartofeditorVoß, Stefan
dc.relation.ispartofeditorReiners, Torsten
dc.relation.ispartofeditorPahl, Julia
dc.relation.ispartofpublnameSpringeren
dc.relation.ispartofdate2012
dc.relation.ispartofurlhttp://dx.doi.org/10.1007/978-3-642-21527-8en
dc.description.sponsorshipprivateouien
dc.subject.ddclabelInformatique généraleen
dc.relation.ispartofisbn978-3-642-21526-1en
dc.relation.conftitleINOC 2011en
dc.relation.confdate2011-06
dc.relation.confcityHambourgen
dc.relation.confcountryGermanyen
dc.identifier.doi10.1007/978-3-642-21527-8_23
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
hal.identifierhal-01497102*
hal.version1*
hal.update.actionupdateMetadata*
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record