講演抄録/キーワード |
講演名 |
2016-06-25 14:05
点容量型多品種フロー問題に対する双対降下アルゴリズムとその応用 ○平井広志(東大) COMP2016-12 |
抄録 |
(和) |
本論文では,点容量型無向ネットワークの半整数最大マルチフローを求める
$O(m n^3 log k)$時間の組合せ的アルゴリズムを与える.ここで,$n$はネットワークの頂点数,$m$は枝数,$k$はターミナルの個数である.これはこの問題に対する最初の組合せ的強多項式時間アルゴリズムである.我々のアルゴリズムは,グラフ構造上の離散凸関数の理論に基いて設計される.このアルゴリズムを用いることで,点マルチウェイカットに対するGarg-Vazirani-Yannakakisの2近似アルゴリズムが組合せ的かつ強多項式時間で実現できるようになった. |
(英) |
In this paper, we develop an $O(m n^3log k)$-time algorithm to find
a half-integral node-capacitated multiflow of the maximum total flow-value in a network with $n$ nodes, $m$ edges, and $k$ terminals.
This is the first combinatorial strongly polynomial time algorithm for this problem.
Our algorithm is designed on the basis of a developing theory of discrete convex functions on certain graph structures.
Applications include ``ellipsoid-free" combinatorial implementations
of a 2-approximation algorithm for the minimum node-multiway cut problem by Garg, Vazirani, and Yannakakis. |
キーワード |
(和) |
点容量型マルチフロー / 離散凸解析 / 劣モジュラフロー / 点マルチウェイカット / / / / |
(英) |
node-capacitated multiflow / discrete convex analysis / submodular flow / node-multiway cut / / / / |
文献情報 |
信学技報, vol. 116, no. 116, COMP2016-12, pp. 105-108, 2016年6月. |
資料番号 |
COMP2016-12 |
発行日 |
2016-06-17 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2016-12 |