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
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, e∈ E. On nous donne un sommet s∈ V désigné comme un puits, une capacité de bord λ>0 et un ensemble source S⊆ V avec demande q(v)∈ [0,λ], v∈ S. Pour chaque bord e∈ E, 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 v∈ S le long d'un seul chemin Pv à l'évier s sans diviser la demande d'aucune source v∈ S. Pour chaque bord e∈ E, 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| v∈ S∈ des chemins de G qui minimise le coût d'installation ∑e∈ E 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.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copier
Ehab MORSY, Hiroshi NAGAMOCHI, "Approximation to the Minimum Cost Edge Installation Problem" in IEICE TRANSACTIONS on Fundamentals,
vol. E93-A, no. 4, pp. 778-786, April 2010, doi: 10.1587/transfun.E93.A.778.
Abstract: We consider the minimum cost edge installation problem (MCEI) in a graph G=(V,E) with edge weight w(e)≥ 0, e∈ E. We are given a vertex s∈ V designated as a sink, an edge capacity λ>0, and a source set S⊆ V with demand q(v)∈ [0,λ], v∈ S. For each edge e∈ E, we are allowed to install an integer number h(e) of copies of e. MCEI asks to send demand q(v) from each source v∈ S along a single path Pv to the sink s without splitting the demand of any source v∈ S. For each edge e∈ E, a set of such paths can pass through a single copy of e in G as long as the total demand along the paths does not exceed the edge capacity λ. The objective is to find a set P={Pv| v∈ S∈ of paths of G that minimizes the installing cost ∑e∈ E h(e)w(e). In this paper, we propose a (15/8+ρST)-approximation algorithm to MCEI, where ρST is any approximation ratio achievable for the Steiner tree problem.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E93.A.778/_p
Copier
@ARTICLE{e93-a_4_778,
author={Ehab MORSY, Hiroshi NAGAMOCHI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Approximation to the Minimum Cost Edge Installation Problem},
year={2010},
volume={E93-A},
number={4},
pages={778-786},
abstract={We consider the minimum cost edge installation problem (MCEI) in a graph G=(V,E) with edge weight w(e)≥ 0, e∈ E. We are given a vertex s∈ V designated as a sink, an edge capacity λ>0, and a source set S⊆ V with demand q(v)∈ [0,λ], v∈ S. For each edge e∈ E, we are allowed to install an integer number h(e) of copies of e. MCEI asks to send demand q(v) from each source v∈ S along a single path Pv to the sink s without splitting the demand of any source v∈ S. For each edge e∈ E, a set of such paths can pass through a single copy of e in G as long as the total demand along the paths does not exceed the edge capacity λ. The objective is to find a set P={Pv| v∈ S∈ of paths of G that minimizes the installing cost ∑e∈ E h(e)w(e). In this paper, we propose a (15/8+ρST)-approximation algorithm to MCEI, where ρST is any approximation ratio achievable for the Steiner tree problem.},
keywords={},
doi={10.1587/transfun.E93.A.778},
ISSN={1745-1337},
month={April},}
Copier
TY - JOUR
TI - Approximation to the Minimum Cost Edge Installation Problem
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 778
EP - 786
AU - Ehab MORSY
AU - Hiroshi NAGAMOCHI
PY - 2010
DO - 10.1587/transfun.E93.A.778
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E93-A
IS - 4
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - April 2010
AB - We consider the minimum cost edge installation problem (MCEI) in a graph G=(V,E) with edge weight w(e)≥ 0, e∈ E. We are given a vertex s∈ V designated as a sink, an edge capacity λ>0, and a source set S⊆ V with demand q(v)∈ [0,λ], v∈ S. For each edge e∈ E, we are allowed to install an integer number h(e) of copies of e. MCEI asks to send demand q(v) from each source v∈ S along a single path Pv to the sink s without splitting the demand of any source v∈ S. For each edge e∈ E, a set of such paths can pass through a single copy of e in G as long as the total demand along the paths does not exceed the edge capacity λ. The objective is to find a set P={Pv| v∈ S∈ of paths of G that minimizes the installing cost ∑e∈ E h(e)w(e). In this paper, we propose a (15/8+ρST)-approximation algorithm to MCEI, where ρST is any approximation ratio achievable for the Steiner tree problem.
ER -