重み付き次数制約を持つネットワーク設計問題 Network Design with Weighted Degree

Search this Article

Author(s)

    • 福永 拓郎 FUKUNAGA Takuro
    • 京都大学情報学研究科数理工学専攻 Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University
    • 永持 仁 NAGAMOCHI Hiroshi
    • 京都大学情報学研究科数理工学専攻 Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University

Abstract

重みw:E×V→Q_+が与えられている無向グラフG=(V,E)を考える.節点v∈Vの重み付き次数d_w(v;E)をΣ{w(e,v)|vに接続する辺e∈E}と定義する.本研究では,各節点の重み付き次数に対する上限が制約として与えられているネットワーク設計問題を考える.問題の入力は,辺集合E=E_1∪^^・E_2∪^^・E_3を持つ無向グラフG=(V,E),辺コストc:E→Q,次数上限b:V→Q_+である.解は全域木T⊆Eと重みw_i:T_i×V→Q+(i∈{2,3})から成る(ただし,T_i=T∩E_i).w_2(e,u)+w_2(e,v)=μ(e)(e=uv∈T_2),{w_3(e,u),w_3(e,v)}={0,ν(e)}(e=uv∈T_3),d_<w1>(v;T_1)+d_<w2>(v;T_2)+d_<w3>(v;T_3)≤(v)(v∈V)を満たすとき,解が実行可能であると定義する.問題の目的は,Σ_<e∈T>c(e)が最小となる実効可能解を求めることである.我々は,重み付き次数に関する制約を違反することを許した上で,コストと重み付き次数を同時に抑えるような解を計算するアルゴリズムを提案する.また,解の最大重み付き次数を最小化する問題についても考える.

In an undirected graph G=(V,E) with a weight function w:E×V→Q_+, the weighted degree d_w(v;E) of a vertex v∈V is defined as Σ{w(e,v)|e∈E incident with v}. In this paper, we consider a network design problem with the upper-bound on weighted degree of each vertex. Inputs of the problem are an undirected graph G=(V,E) with E=E_1∪^^・E_2∪^^・E_3, weights w_1:E_1×V→Q_+,μ:E_2→Q_+ and ν:E_3→Q_+, an edge-cost c:E→Q, and a degree-bound b:V→Q_+. A solution consists of a spanning tree T⊆E and weights w_i:T_i×V→Q_+ for i∈{2,3}, where T_i stands for T∩E_i. It is defined to be feasible if it satisfies w_2(e,u)+w_2(e,v)=μ(e) for e=uv∈T_2, {w_3(e,u),w_3(e, v)}={0,ν(e)} for e=uv∈T_3, and d_<w1>(v:T_1)+d_<w2>(v;T_2)+d_<w3>(v;T_3)≤b(v) for each v∈V. The goal of this problem is to find a feasible solution that minimizes its cost Σ_<e∈T>c(e). Relaxing the constraints on weighted degree, we propose bi-criteria approximation algorithms based on the iterative rounding. We also consider another problem that asks to minimize the maximum weighted degree of vertices.

Journal

  • IPSJ SIG Notes

    IPSJ SIG Notes 118, 41-48, 2008-05-20

    Information Processing Society of Japan (IPSJ)

References:  14

Codes

  • NII Article ID (NAID)
    110006793663
  • NII NACSIS-CAT ID (NCID)
    AN1009593X
  • Text Lang
    ENG
  • Article Type
    ART
  • ISSN
    09196072
  • NDL Article ID
    9525256
  • NDL Call No.
    Z14-1121
  • Data Source
    CJP  NDL  NII-ELS 
Page Top