Essec\Faculty\Model\Contribution {#2188
  #_index: "academ_contributions"
  #_id: "2037"
  #_source: array:26 [
    "id" => "2037"
    "slug" => "master-slave-strategy-and-polynomial-approximation"
    "yearMonth" => "2000-09"
    "year" => "2000"
    "title" => "Master-slave Strategy and Polynomial Approximation"
    "description" => "ALFANDARI, L. et PASCHOS, V. (2000). Master-slave Strategy and Polynomial Approximation. <i>Computational Optimization and Applications</i>, pp. 231-245."
    "authors" => array:2 [
      0 => array:3 [
        "name" => "ALFANDARI Laurent"
        "bid" => "B00000901"
        "slug" => "alfandari-laurent"
      ]
      1 => array:1 [
        "name" => "PASCHOS V."
      ]
    ]
    "ouvrage" => ""
    "keywords" => []
    "updatedAt" => "2020-12-17 17:55:06"
    "publicationUrl" => null
    "publicationInfo" => array:3 [
      "pages" => "231-245"
      "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" => "De nombreux problèmes de minimisation de coût consistent à couvrir les sommets ou les arêtes d'un graphe par des sous-graphes vérifiant une certaine propriété. Si le nombre de sous-graphes candidats est une fonction polynomiale de la taille du graphe, l'heuristique gloutonne classique pour le Set Covering, analysée par Chvatal, permet d'approcher l'optimum à rapport logarithmique. Nous étendons ce résultat à des problèmes où le nombre de sous-graphes peut être exponentiel, en utilisant une technique dite "maître-esclave". Les applications concernent des problèmes de télécommunication, de localisation et de conception de circuits électroniques."
      "en" => "Many minimization problems consist in covering vertices or edges of a graph by subgraphs verifying a given property. If the number of candidate subgraphs is a polynomial function depending on the size of the graph, then the classical greedy heuristic for Set Covering, analysed by Chvatal, guarantees a polynomial approximation within a logarithmic ratio. We extend this result to a class of problems with a possible exponential number of subgraphs, by revisiting a technique called "master-slave". Applications are studied for telecommunication, optimal location and VLSI-design."
    ]
    "authors_fields" => array:2 [
      "fr" => "Systèmes d’Information, Sciences de la Décision et Statistiques"
      "en" => "Information Systems, Decision Sciences and Statistics"
    ]
    "indexedAt" => "2024-04-25T13:21:58.000Z"
    "docTitle" => "Master-slave Strategy and Polynomial Approximation"
    "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, Decision Sciences and Statistics</span> | <span class="document-property-year">2000</span>"
    "keywordList" => ""
    "docPreview" => "<b>Master-slave Strategy and Polynomial Approximation</b><br><span>2000-09 | Journal articles </span>"
    "docType" => "research"
    "publicationLink" => "<a href="#" target="_blank">Master-slave Strategy and Polynomial Approximation</a>"
  ]
  +lang: "en"
  +"_type": "_doc"
  +"_score": 9.133459
  +"parent": null
}