Essec\Faculty\Model\Contribution {#2216
  #_index: "academ_contributions"
  #_id: "665"
  #_source: array:26 [
    "id" => "665"
    "slug" => "approximating-minimum-spanning-tree-of-depth-2"
    "yearMonth" => "1999-06"
    "year" => "1999"
    "title" => "Approximating Minimum Spanning Tree of Depth 2"
    "description" => "ALFANDARI, L. et PASCHOS, V. (1999). Approximating Minimum Spanning Tree of Depth 2. <i>International Transactions in Operational Research</i>, pp. 607-622."
    "authors" => array:2 [
      0 => array:3 [
        "name" => "ALFANDARI Laurent"
        "bid" => "B00000901"
        "slug" => "alfandari-laurent"
      ]
      1 => array:1 [
        "name" => "PASCHOS V."
      ]
    ]
    "ouvrage" => ""
    "keywords" => []
    "updatedAt" => "2021-07-13 14:30:00"
    "publicationUrl" => null
    "publicationInfo" => array:3 [
      "pages" => "607-622"
      "volume" => null
      "number" => null
    ]
    "type" => array:2 [
      "fr" => "Articles"
      "en" => "Journal articles"
    ]
    "support_type" => array:2 [
      "fr" => "Revue scientifique"
      "en" => "Scientific journal"
    ]
    "countries" => array:2 [
      "fr" => null
      "en" => null
    ]
    "abstract" => array:2 [
      "fr" => "Parmi les problèmes d'optimisation dans des réseaux, le problème de l'arbre recouvrant de coût minimum de profondeur 2 possède de nombreuses applications, parmi lesquelles figure la localisation d'émetteurs d'une entreprise de télécommunications. Nous donnons pour ce problème NP-difficile une heuristique de résolution approchée, dont l'efficacité est validée d'un point de vue à la fois théorique et expérimental. L'algorithme exploite une forme de réduction originale avec le problème classique de Set Covering."
      "en" => "Among the Network-Design optimization problems, the minimum-cost spanning tree with depth 2 has several applications. For example, a Telecommunications company located in Paris must select a subset of cities where to build local transmitters so that every other city is connected to a transmitter and all transmitters are connected to Paris. We approximate this NP-hard problem by a greedy heuristic with worst-case performance guarantee and practical efficiency. The algorithm exploits some kind of original reduction with the well-known Set Covering problem."
    ]
    "authors_fields" => array:2 [
      "fr" => "Systèmes d'Information, Data Analytics et Opérations"
      "en" => "Information Systems, Data Analytics and Operations"
    ]
    "indexedAt" => "2024-11-21T10:21:50.000Z"
    "docTitle" => "Approximating Minimum Spanning Tree of Depth 2"
    "docSurtitle" => "Journal articles"
    "authorNames" => "<a href="/cv/alfandari-laurent">ALFANDARI Laurent</a>, PASCHOS V."
    "docDescription" => "<span class="document-property-authors">ALFANDARI Laurent, PASCHOS V.</span><br><span class="document-property-authors_fields">Information Systems, Data Analytics and Operations</span> | <span class="document-property-year">1999</span>"
    "keywordList" => ""
    "docPreview" => "<b>Approximating Minimum Spanning Tree of Depth 2</b><br><span>1999-06 | Journal articles </span>"
    "docType" => "research"
    "publicationLink" => "<a href="#" target="_blank">Approximating Minimum Spanning Tree of Depth 2</a>"
  ]
  +lang: "en"
  +"_type": "_doc"
  +"_score": 9.064929
  +"parent": null
}