La fonctionnalité de recherche est en construction.
La fonctionnalité de recherche est en construction.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

Approximation to the Minimum Cost Edge Installation Problem Approximation du problème d’installation du coût minimum

Ehab MORSY, Hiroshi NAGAMOCHI

  • Vues en texte intégral

    0

  • Citer

Résumé:

Nous considérons le problème d'installation de bord à coût minimum (MCEI) dans un graphique G=(V,E) avec poids de bord w(e)≥ 0, eE. On nous donne un sommet sV désigné comme un puits, une capacité de bord λ>0 et un ensemble source SV avec demande q(v)∈ [0,λ], vS. Pour chaque bord eE, nous sommes autorisés à installer un nombre entier h(e) de copies de e. MCEI demande d'envoyer la demande q(v) de chaque source vS le long d'un seul chemin Pv à l'évier s sans diviser la demande d'aucune source vS. Pour chaque bord eE, un ensemble de ces chemins peut passer par une seule copie de e in G tant que la demande totale le long des chemins ne dépasse pas la capacité de bord λ. L'objectif est de trouver un ensemble P={Pv| vS∈ des chemins de G qui minimise le coût d'installation ∑eE h(e)w(e). Dans cet article, nous proposons un (15/8+ρST)-algorithme d'approximation du MCEI, où ρST est-ce qu'un rapport d'approximation est réalisable pour le Problème d'arbre de Steiner.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E93-A No.4 pp.778-786
Date de publication
2010/04/01
Publicisé
ISSN en ligne
1745-1337
DOI
10.1587/transfun.E93.A.778
Type de manuscrit
PAPER
Catégories
Algorithmes et Structures de Données

Auteurs

Mots-clés

Table des matières