バンド幅問題に対するvolume respecting embedding法の実験的評価 (計算機科学基礎理論の新展開)

バンド幅問題に対する

volume respecting embedding

法の実験的評価

群馬大学・駒原 雄祐 (Yuusuke Komahara), 中野 泰男 (Yasuo Nakano), 山崎浩一 (Koichi Yamazaki)

Department of Computer Science,

Gunma

University

1.

はじめ (こ

1998

年にFeigeが, バンド幅問題に対する近似

率$O$($(\log n)^{3}\sqrt{\mathrm{o}\mathrm{g}}$nlog log$n$) の近似アルゴリズ

ムを提案した [8]. Feigeのアルゴリズムが提案さ れる以前では, CuthiU-McKee(CM) 法や改良逆 Cuthill-McKee(GPS)法などの (バンド幅問題に 対する) 幾つかの発見的手法が知られていた. し かしそれらアルゴリズムの近似率の正確な解析 はされておらず, 実験的な評価のみであった. 文 献[8]で Feigeは, 従来と全く異なる手法を提案 し, さらに従来無し得なかった近似率の解析を初 めて行った. 本論文では, バンド幅問題に対し

,

良く知られていて比鞍的実装が簡単な Cuthill-McKee(CM) 法と Feige のアルゴリズムとの比 校を行う. 1.1. バンド幅問題とは $G=(V, E)$ をグラフとし, $LO(G)$ を $V$から

\emptyset{1

バン

\vdash’

$|\backslash \backslash$

幅

},

/b\w(G

全

)

単は

,

の集合とする

.

グラフ $G$ $bw(G)=$ $\min$ _{$\max|f(u)-f(v)|$} $f\in LO(G)\{u,v\}\in E$ で定義される. $M$ _を $n$次の対称正方行列とする. $M$の全て の行に対して, 対角或分から非零成分までの列数 の最大値, 細(M), を行列$M$_{のバンド幅と呼ぶ}. $PM_{n}$ をサイズ$n$の置換行列の集合とする. $b= \min_{P\in PM_{n}}bw(PMP^{T})$ のとき, 行列$M$_{は最小バンド幅}$b$を持つ行列に 変換可能であると言う. グラフのバンド幅を求 める問題や, 行列を最小バンド幅を持つ行列に変 換する問題をバンド幅問題と呼ぶ. 1.2. バンド幅問題の応用例 帯行夕Uに対するガウスの洞去法 $M$ _を $n$次の 対称正方行列とする. バンド幅問題を解くこと により, $M$ _{をバンド幅}$b$ を持つ行列に変換でき たとする. このとき, (通常$O(n^{3})$ _かかる) _ガウ スの消去法は $O(nb^{2})$_{で実行でき}, _{$b\ll n$の場合} 計算コストがかなり削減できる. 1.3. バンド幅問題の研究の歴史 1.3.1. レベル構造 バンド幅問題に対して従来からよく用いられ ている

CM

法や

GPS

法などの発見的手法は, レ ベル構造を構成している. グラフ $G=(V, E)$ の 頂点の部分集合の列$(L_{1}, \ldots,L_{M})$がレベル構造 を成すとは, 1. $\sum_{i=1}^{M}L_{i}=V$

,

2. $\{u, v\}\in E,$$u\in L_{i},$$v\in Lj\Rightarrow|i-j|\leq 1$

を滴たすときをいう. $\max_{1\leq i<M}L$

:

をレベノレ構 造$(L1, \ldots, LM)$_{の幅と呼ぶ}. _グラフ $G$のレベル 構造での最小の幅を $lw(G)$ _{で表すと,} $lw(G)\leq$ 紬(G) $<2lw(G\underline{)}-1$ という関係が威り立つ. 従っ て, もし最小の幅を持つレベル構造を見つけるこ とができれば, バンド幅の2倍近似が実現できる ことになる. しかしながら, 最小の幅を持つレベ ル構造を見つけることは$\mathrm{N}\mathrm{P}$ 困難であることが 知られている [2]. 1.3.2. 距離に蟇づいたレベル構造 先に述べた通り, 最小の幅を持つレベル構造 を見つけることは計算量的に困難である. 従っ て, 最小の幅は保証しないが, 比校的簡単にレベ ル構造が実現できる, 距離に基づいてレベルを構 成する方法がよく用いられる. $R_{0}$ を頂点のある部分集合とし, $R_{\dot{4}}$ を烏か ら距離 $i$ にある点の集合とする. このとき Rか$R_{1},$ $\ldots,$$R_{h}(h$はゐから最も遠い点までの距 離) はレベル構造を成す. 通常$R_{0}$ のサイズは 1 である. 距離に基づいてレベルを構成する方法 は手軽であるが, (理論的には) それにより得ら れるレベル構造の幅が最小の幅$lw(G)$ よりかな り大きくなる揚合が起こり得る. また距離に基 づいて構成されたレベルの中での最小幅を求め る問題は, たとえグラフを木に制限したとして も, 4/3 未溝に近似率を下げられないことが知ら れている [17]. 実際, 距離に基づいて得られたレ ベル構造の幅が$O(lw(G)\log|V|)$ となる (人工的 な) グラフは簡単に作ることが出来る. しかしな がら, ランダムに生成されたグラフなどに対して は, この距離に基づいたレベル構造を用いたバン ド幅問題の発見的手法は実験的には良い結果を 出力することが知られている [14]. 数理解析研究所講究録 1325 巻 2003 年 158-163

158

158

1.3.3. Cuthill-McKee(CM) 法 CM法はCuthillと McKeeにより

1960

年代後 半に提案された方法で, 距離に基づいたレベル構 造を用いている [6].

CM

法の改良としてGPS法 が良く知られている [9]. 1. 各頂点$v$に対し, $R_{0}=\{v\}$ とし距離に基づ くレベル構造を生成し, そのレベル構造の 幅を計算する

1.

2. 得られた幅の中で最小の幅を持つレベル構 造Rか..

.

,

$R_{h}$ を選ぶ.

3. $u\in R_{i},v\in Rj,$$i<i\Rightarrow f(u)<f(v)\text{と}fx$

るようにある$\ovalbox{\tt\small REJECT} \mathrm{F}\int|_{}^{}$

したがって各頂点の並 ひ (すなわち $f$ : $Varrow\{1,$$\ldots,$$|V|\}$) を計算 する2.

1.3.4.

バンド幅問題の難しさ バンド幅問題は入力を最大次数が

3

の木に制 限しても, 対応する判定問題が $\mathrm{N}\mathrm{P}$ 完全である 3 _{[10]. また, 入力を木に制限しても, 近似率は} 4/3 より良くならない [3]. 一般のグラフに対し ては (つまり, 入力に何も制限を設けない場合), ($P\neq NP$_{の仮定の下で) 定数近似は不可能であ} ることも知られている [15]. 従って, Feigeのアル ゴリズムの近似率は決して悪くはないと言える. さらに, 与えられた正整数$k$に対しバンド幅が $k$ 以下であるかの判定問題は実質brute forceで行 う方法しかないことが予想されている [4]. 4 1.3.5. 最近の研究 バンド幅問題に対する他の近似アルゴリズム としては, Feige の論文 [8] と同年に, 半正定 値計画法と射影法を組み合わせた技法が [1] で 発表されている. Feige の論文 [8] 以降, [13, 7, 11] などの幾つかの論文が発表されている. 文献 [7] では Feige のアルゴリズムの近似率が $O((\log n)^{3}\sqrt{\mathrm{o}\mathrm{g}\log n})$ に改善されている. グラ フをあるノルム空間に埋め込む研究やランダム 射影 [16] の研究が近年盛んに行われている. 1 _{計算時間を節約したい揚合,次数の低い頂点}$v$のみに 対し

&=

$\{v\}$の計算を行う 2 _{規則の詳細な記述は文献 [5] を参照} 3 _{良く知られている問題で,木に制限しても}$\mathrm{N}\mathrm{P}$完全であ るものはあまり無い (他には例えばsubgraph isomorphism やachromaticnumberなと)

4 _{正確にはfixed parameterized intractableであること}

が知られている.

2.

volume respecting

$\mathrm{e}\mathrm{m}\mathrm{b}\mathrm{e}\mathrm{d}\mathrm{d}\mathrm{i}\mathrm{n}\mathrm{g}/\backslash \xi\backslash$

Linial 等は, 各 2 頂点に対し , それらのグラ

フ上での距離をそれらの空間上での距離以下に

保ち, かつあまり短くならないように, グラフ

をあるノル\Delta 空間に埋め込む研究を行った [12].

Feige はこの研究に触発されvolume respecting

embedding法の研究を開始した. Feigeは以下の 性質を満す (グラフの空間への) 埋め込みのアル ゴリズムを開発した. 埋め$\llcorner\backslash \lambda$みが満たす性質$P$ 1. 任意の2頂点$u,$$v$に関して, $u$ と $v$の空間上 での距離は高々グラフ上での距離, 2. 任意の $k$頂点に対し, それらの $k$頂点が成 す単体の $k-1$次元の体積が, ある程度の大 きさを持つ. この性質2の$k=2$の場合は, 任意の

2

頂点が成 す1 次元の体積つまり長さが小さくならないこと を意味する. つまり, Linial等の埋め込みはFeige の埋め込みの$k=2$ の楊合に相当し, Feigeの埋 め込みはLinial等の埋め込みの拡張と言える. 2.1. 基本アイディア VRE法は, 1)埋め込みと 2) 射影の 2段階 からなる. 埋め込みでは, 体積をある程度保つよ う, グラフの各頂点を $L=\Theta((\log n)^{4}\log\log n)$ 次元空間に埋め込む. 性質 1 を滴たさなければ ならないので, そのように埋め込む為には工夫 が必要である. 射影は空間内にランダムな直線 をJ き, その直線に, 埋め込まれた頂点が射影さ れる. この直線上に射影された並びが出力解と なる. ランダムにJいた直線に各点を射影すると, 当 然直線の最も端に射影された 2つの頂点(右端と 左端) が存在する. この

2

頂点の距離が短いとバ ンド幅が大きくなる傾向がある

.

この 2頂点の

距離が短くなる確率は体積の大きさに反比例す

るので, 性質

2

が必要となる. 22. 近似率の算定方法 5 $ld(G)$ 自身を求める問題はAPX 完全であることが知 られている 6_{バンド幅問題では, この$ld(G)$ が下界として良く用い} られる

159

2.3. アルゴリズハ アルゴリズムは 1) 埋め込みと 2) 射影の2段 階からなる.

どちらの段階も確率的アルゴリズ

ムなので,

良い解を得るためには適当な回数繰

り返しが必要となる. 射影よりも埋め込みの方 が手間がかかる. 時間計算量は $O(|E(G)|L)\simeq$ $O(|E(G)|(\log n)^{5})$ _である. 埋め$\llcorner\backslash \lambda$ みのアルゴリズb 入力 グラフ $G=(V, E)$ 出力: $\varphi$ : $Varrow R^{L}$

1. $L=((\log n)^{4}\log\log n),$ $k_{j}=\lceil j\log n/L\rceil$

,

$p_{j}=2^{-k_{j}},$ $(1<j<L)$ とする.

2. $L$個の部分集合

Sj-

を作成する

:

各頂点 M こ対し , v 詠確率$pj$で集合$S_{j}$ に

入れる.

3.

各$\mathrm{f}\mathrm{f}\mathrm{l}_{1}\mathrm{f}\mathrm{f}_{\backslash }$

$v_{i}$ に対し, $\varphi(v:)$ の各$i$ 座標$\varphi j(v_{i})$

を $\varphi j(v:)=d(Sj,v:)$ とセットする.

射影のアルゴリズ b

入力: $\varphi$ 出力 頂点の並ひ 1. ランダムに $rj\in N[0,1]$ を選択する.

2.

各$\mathrm{f}\mathrm{f}\mathrm{l}_{1}\mathrm{f}\mathrm{f}_{\backslash }$ $v_{1}$. に対し, $h(v_{1}.)= \sum^{L}j=1rj\varphi j(v_{1}.)$ を 計算する.

3.

頂点集合$V$_{を $h(v:)$} の値で昇順にソートし, その並ひを出力する.

3.

実験結果

CM

法

$\mathrm{v}\mathrm{s}$

.

VRE

法

7

回の埋め込み $\mathrm{x}40$ 回の射影を

1

セットと勘 定する. 1 セットの中で最も良い値を解として

出力する. 実験環境は, CPU,

intel

pentium 4/

$2.2\mathrm{G}\mathrm{H}\mathrm{z}.$

,

メモリ, 1GB., $\mathrm{O}\mathrm{S}$

,

Vine

Linux

2.5, コ

ンパイラ, Ja

SDK 140

である. 3.1. ランダ

b

グラフに対する結果 それぞれ辺の密度が異なる

3000

頂点の

50

個 のランダムグラフに対し実験を行った. $n$ を頂 点数とすると, $L=((\log n)^{4}\log\log n)$ なので $n=3000$ のとき $L=62835$ となる. 1つのランダムグラフに対し, 幾つかの次元で

VRE

法を行った. 正確には, $L/10$次元から始め, 次元が

20

以上の間は1/2倍づつして行き,

20

を 下回った時点で

1

づつ減らし, 次元が

2

になるま で実験を行った. 我々の実験環境では $L$次元で の$\mathrm{V}\mathrm{R}\mathrm{E}$ 法が実行できなかった

.

そのため, $L/10$ 次元から実験を始めた. これにより 1つのランダムグラフに対し

19

個 のバンド幅の値を得るが, その中での最も良いバ ンド幅を得る次元は全て一桁台であった. また, 次元が小さくなるに連れ出力解が良い値を取り, 最も良い値を出す次元は 3から

8

の間に集中し ていることがわかった. 典型的な例として, 辺の 密度が異なる

3000

頂点の3つのランダムグラフ でのバンド幅と次元の関係を図

1

に,処理時間と 次元の関係を図 2 に示す. $r\backslash _{\grave{d}}\cdot\vdash.\mathrm{B}$ $\underline{l_{\{\sim\ddot{\overline{\overline{\mathrm{a}}}}\overline{\ddot{\dot{\propto}}}\ddot{\overline{\mathrm{k}}}\mathrm{f}\overline{\overline{\ddot{\mathrm{f}\mathrm{i}}}}\cdot\tilde{\ddot{\ddot{\dot{8}}}}\mathrm{f}\overline{\dot{\overline{\overline{\mathrm{f}\mathrm{i}}}}}\ddot{\mathrm{t}}i\mathrm{z}\ddot{\ddot{\overline{\mathrm{B}}}}\mathrm{f}\ddot{\ddot{\ddot{\ddot{\mathrm{f}\mathrm{i}}}}}\mathrm{f}\overline{\overline{\ddot{\mathrm{f}\mathrm{i}}}}\overline{\ddot{\mathrm{k}}}\ddot{\dot{3}}\mathrm{f}\dot{\overline{\ddot{\ddot{\mathrm{f}\mathrm{i}}}}}_{l}^{\mathrm{i}}}^{\sim\cdot\cdot\sim-\cdot-\cdot--\cdots--\cdot-\cdot-}1^{\cdot}-\cdot..-\cdots.-\neg}\mathrm{i}$ $\alpha 00$ $\mathrm{z}‘ w$ $\mathrm{z}\mathrm{m}$ $\iota \mathrm{m}$ $1\mathrm{m}$ $5\infty$ $0$

$u\iota$”$’\iota’\iota\epsilon r\mathrm{o}$ ll$ $u\mathrm{a}1$

次元

$l9\mathrm{Z}4$ $\prime 2$ $t$ $\theta$

図 1: バンド幅と次元の関係 時間 0) 図

2: 処理時間と次元の関係

3.1.1. 解の精度での評価 大きい次元 $(L/10=6283)$ と小さい次元 (5) の 2つの次元での

VRE

法と

CM

法のそれぞれ の出力解の値が図3にプロットされている. 図

3: 3000 頂点のランダムグラフでの解の比校

160

ランダムグラフでの解の精度においては, 図

3

が 示すとおり, 次元の大きさにかかわらず

CM

法 の圧勝である. 3.1.2. 処理時間での評価 大きい次元 $(L/10=6283)$ と小さい次元 (5) の 2つの次元での VRE法と

CM

法のそれぞれ の処理時間が図4にプロットされている. ランダ\Delta グラフの処理時間においては, 図 4が 示すとおり, 次元が大きい場合はCM法の圧勝 である. 図4ではわかりにくいが, 次元が小さい 場合は, 辺の密度が小さいと

CM

法の方が処理 時間は短いが, 辺の密度が多くなると逆転が起き ている. 図

4:

3000

頂点のランダムグラフでの処理時間 の比較

3.2. CM

法が苦手とする特殊なグラフ 3.2.1. 風車グラフ 風車グラフとは図

5

にあるように, 2部グラフ の辺を根に近付く程より多くストレツチして得 られるグラフである. 図

6

が示すように, 解は oe_{法がかなり良い}. 図 5: 風車グラフ 図

6:

風車グラフ 図

7

は, 深さ 9(3071 頂点) の風車グラフに対し ての,

CM

法と

VRE

法の処理時間の比校を示し ている.

CM

法より良い値を出すかまたは1セッ ト処理しきるまでの時間が

VRE

法の曲線とし て記されている. 次元が小さい場合でも, VRE法が

CM

法より 良い値を得るためには, 少ない埋め込みで十分 であることが図 7から読み取れる. 次元が 2で VRE法の曲線が跳ね上がっているのは, 埋め込 みの失敗が続いたためと考えられる. [-.$\cdot$

9\check 沖\sim --.-.v..B年\sim |

$\iota \mathrm{m}\prime^{-}|$

$\mathrm{r}\mathrm{m}.\frac{1}{\mathrm{I}\}\mathrm{i}}$.

n瞑\kappa $\underline{\overline{j|}\mathrm{i}}--,$$\cdot$

$\overline{@\mathrm{r}}2\mathrm{K}\frac{\mathrm{l}}{}\mathrm{I}\mathrm{I}r-|‘.--\frac{\mathrm{I}}{-1!}.\cdot.\cdot$

$\mathrm{g}_{\mathfrak{l}\epsilon \mathfrak{m}\frac{1\mathfrak{l}}{1}}$

..

$———\cdot--\cdotrightarrow.\cdot$

$\mathrm{I}\mathrm{K}\mathrm{L}\mathrm{t}^{1}\overline{..,|}.\underline{-}.$.

$\mathrm{a}\mathfrak{m}|$

「$-\infty.\mathrm{r}^{-*\cdot-\sim---\frac{-}{-}}...$’.

$\backslash ^{\phi\backslash \backslash \backslash }l^{\frac{1}{\backslash \theta\backslash ^{\mathrm{b}}\backslash ^{\grave{\mathrm{t}}\grave{\mathrm{t}}}}-}.\backslash \cdot....\vee*4$

4 $\mathrm{t}$ $\backslash \cdot$ . $\mathrm{X}\overline{\pi}$ 図

7:

風車グラフでの時間の比校

322.

$C_{n}$の $k$乗グラフ $C_{n}$ の$k$乗グラフとは, _$n$頂点から成るサイク ル $C_{n}$の各頂点$v$に対し, $v$ と距離$k$以下にある

すべての頂点を辺で結ぶことにより得られるグ

ラフである. 辺を結ぶ間隔$k$が大きくなる程

CM

法と $\mathrm{V}\mathrm{R}\mathrm{E}$ 法の差が開いて来ることが図

9

からわかる.

161

図

8:

$C_{12}$_の

3

乗グラフ 図

9:

$C_{1}000$ _の$k$乗グラフでの解の比鮫

4. 近似率での評価

(

完全

2

分木に対する結

果)

図 10: 2部グラフでの解の比較 図10からわかるように解の精度に関しては CM 法と RE法の差はあまり無い. 約2000頂点で両 者の解は最適解の約

5

倍程度で抑えられている.

5.

まとめ及び考察 5.1. VRE法の評価 文献 [8] に沿って, 1. 埋め込み先の次元を大きくとり, 2. 埋め込みのアルゴリズ$\text{ム}$を繰り返し,

3.

射影のアルゴリズムも繰り返す と処理時間は, 従来手法と比べるとかなりかか る. また解の精度も

CM

法と比べやや劣る. ラ ンダムなグラフに対しては, 時間及び精度の再面 で VRE法に勝ち目は無いという印象を (実験結 果から) 受ける. しかしながら,

CM

法が苦手と する風車グラフや $C_{n}$ の $k$乗グラフに対しては, $\mathrm{V}\mathrm{R}\mathrm{E}$ 法の方が随分良い値を出力する. 埋め込みのアルゴリズ\Delta のステップ3の座標 の計算は, 幅優先探索により行われている. 次元 の大きさ分幅優先探索が行われ, これが処理時間 がかかる原因である. これらのことは, 文献[8] の結論にかかれている内容と一致している. 実 装という点から言えば, VRE法は

CM

法より手 軽である. 5.2. 次元の大きさの設定 埋め込み先の空間の次元の値が小さくなれば なる程,処理時間が格段に短くなるという利点が ある. 今回の実験の結果は, 次元はそれほど大きくと る必要が無く, むしろ小さく抑えた方が解の精度 が上がる事を示している. この現象はランダム グラフに限らず, 風車グラフや $C_{n}$ の$k$乗グラフ などの特殊なグラフに対しても見られる. 文献 [8]では, 1. 次元が $\Theta((\log n)^{4}\log\log n))$ 程度あれば埋 め込みのアルゴリズムが高い確率で埋め込 みの性質$P$ _を満たす, 2. 性質$P$ を満たす埋め込みに対して射影のア ルゴリズムを適用すると, 比校的精度の良 い解が得られる, が証明されている. 今回の実験から導かれる推 測として: 1. 次元が小さくても性質$P$を滴たすことがで きる, 2. 次元が小さい場合は性質$P$を満たさないが, 別の性質$P’$ _を滴たし, $P’$ _{を滴たす埋め込み} に対して射影のアルゴリズムを適用すると, 比鮫的精度の良い解が得られる, 3. どんな埋め込みに対しても, 射影のアルゴ リズムを適用すると比校的精度の良い解が 得られる, の

3

つが考えられる. しかし, 小さい次元でラン ダムな埋め込みを行い, その後射影のアルゴリズ ムを適用すると極めて悪い精度の解しか得られ ない事が実験によりわかるので, 可能性としては

1

が

2

のどちらかだと考えられる. つまり, 小さ い次元での埋め込みのアルゴリズムは, バンド幅

162

問題に有利に働く何らがの性質を満たすよう埋 め込みを行っていると考えられる. しかしその 性質が $P$かそれ以外の性質なのかは, 現時点で は不明である.

6.

ら後の課題 次元の大きさの設定 精度の良いバンド幅を求めるためには, 実験的 には, 小さい次元で良い. (もし事実がそうであ れば)比較的良い解が得られる理由の解明

.

Worst

case

analysis

従来ある多くの発見的手法に対して, その手法 ではうまく働かない人工的なグラフを比鮫的簡 単に作る事が出来る. $\mathrm{V}\mathrm{R}\mathrm{E}$法ではうまく働かな い (つまり解の精度が近似率程度に悪くなる) グ ラフを求める. 参考文献

[1] ABlum, G.Konjevod, R.Ravi and

S.Vempala, Semi-Definite Relaxations for

Minimum Bandwidth and other Vertex-Ordering problems, Proc. of $30\mathrm{t}\mathrm{h}$ STOC,

(1998),

100-105.

[2] H.L.Bodlaender, The complexity of

find-ing uniform emulations

on

paths and ring

networks, Information and Computation

86

(1990)

87-106.

[3]

G.Blache

and M.Karpinski,

On

Approx-imation Intractability of the Bandwidth

Problem,

ECCC

TR98-014 (1998).

[4] H.L.Bodlaender ,M.R.FeUows, and

M.T.HaUett, Beyond $\mathrm{N}\mathrm{P}$-completenessfor

problems ofbounded width (extended

ab-stract): hardness for the $\mathrm{W}$ hierarchy,

Proc. of$26\mathrm{t}\mathrm{h}$STOC, (1994), 449-458.

[5] P.Z.Chinn, J.Chvatalova, A.K.Dewdney, and $\mathrm{N}.\mathrm{E}$.Gibbs, The bandwidth problem

for graphs and $\mathrm{m}\mathrm{a}\mathrm{t}\mathrm{r}\mathrm{i}\mathrm{c}\mathrm{e}\mathrm{s}-\mathrm{a}$ survey, J.

Graph Theory

6

(1982),

223-254.

[6] Cuthill, E.,$\mathrm{M}\mathrm{c}\mathrm{K}\mathrm{e}\mathrm{e},\mathrm{J}.$:Reducingthe

band-width of

sparse

symmetric matrices. In:

Proc.

$\mathrm{A}\mathrm{C}\mathrm{M}$

Nat.Conf.

New York (1969),

157-172.

[7] J.Dunagan and S.Vempala,

On

Euclidean

embeddings andbandwidth minimization,

Proc. ofthe 5thWorkshop

on

Randomiza-tion and Approximation, (2001).

[8] U.Feige, Approximating the bandwidth

via volume respecting embeddings,

(Ex-tended abstract)

STOC

(1998)

90-99:

(Journal version) Journal of Computer

and System

Sciences

60(3), (2000),

510-539.

[9] N. E. Gibbs,

W.

G.

Poole, $\mathrm{J}\mathrm{r}.,$ and P.

K. Stockmeyer, An algorithm

for

reduc-$\mathrm{i}\mathrm{n}\mathrm{g}$the bandwidth and profile of

a

sparse

matrix,

SLAM

J. Numer.

Anal.

(1976),

13:236-250.

[10] M.$\mathrm{G}$

arey,

R.Graham, D.Johnson, and

D.Knuth, Complexity Results For

Band-width Minimization,

SIAM

J. Appl.Math.

34

(1978),

477-495.

[11] AGupta, Improved Bandwidth

Approxi-mation

for Trees and

Chordal

Graphs,

J.

Algorithms 40(1) (2001),

24-36.

[12] N.Linial, E.London, Y.Rabinovich, The

Geometry of Graphs and

Some

of its

Algorithmic Apphcations, Combinatorica

15(2) (1995),

215-245.

[13] S.Rao, Small distortion and volume

pre-serving embeddings for planar and

Eu-clidean metrics, Annual Symposium on

Computational Geometry (1999),

300-306.

[14] J.S.Turner,

On

the Probable Performance

of Heuristics for BandwidthMinimization,

SIAM

J. Comput. 15(2) (1986),

561-580.

[15] W.Unger, The Complexity

of

the

Approx-imation

of the

Bandwidth

Problem,

Proc.

$39\mathrm{t}\mathrm{h}$

FOCS

(1998),

82-91.

[16] S.Vempala, Random Projection: A New

Approach to

VLSI

Layout,

FOCS

(1998).

[17] K.Yamazaki, On Approximation

Intractability of the Path-Distance-Wi(lth

Problem, Discrete Applied Mathematics

$\mathrm{V}\mathrm{o}\mathrm{I}.\mathrm{I}\mathrm{I}\mathrm{O}(2001),$$317- 325$

.