特定領域全体会議・A10班
変移する要素間の関係を条件とする組合せ最適化モデル
研究組織：
 宮野英次（九州工業大学）
 廣瀬英雄（九州工業大学）
 朝廣雄一（九州産業大学）
2007/5/14
全体会議
1
目標
 最適化モデル
オフライン，静的，固定的
オンライン，未知情報
2007/5/14
全体会議
2
論文・会議録






Y. Asahiro, E. Miyano, and S. Shimoirisa. K-collect tours for
moving objects with release time and deadline, Proc World
Multi-Conf Systems, Cybernetics and Informatics, 2005.
Y. Asahiro. Simple greedy methods for DNA word design. Proc
World Multi-Conf Systems, Cybernetics and Informatics, 2005.
H. Hirose. Optimal boundary finding method for the bumpy
regions. Proc Int. Federation of Operational Research Societies
Conference, 2005.
Y. Asahiro, E. Miyano, and S. Shimoirisa. Pickup and delivery
for moving objects on broken lines, Proc Italian Conference on
Theoretical Computer Science (ICTCS), 2005.
Y. Asahiro, E. Miyano, H. Ono, and K. Zenmyo. Graph
orientation algorithms to minimize the maximum outdegree.
Proc Computing: Australasian Theory Symp (CATS), 2006.
H. Hirose, T. Yukizane, E. Miyano. The bump hunting method
using the genetic algorithm and the extreme-value statistics
with application to a messy customer database. Proc Hawaii Int.
Conference on Statistics, Mathematics and Related Fields, 2006.
2007/5/14
全体会議
3
論文・会議録





Y. Asahiro, T. Furukawa, K. Ikegami, and E. Miyano. How to
pack directed acyclic graphs into small blocks. Proc Int.
Conference on Algorithms and Complexity (CIAC), 2006.
H. Hirose, T. Yukizane, and E. Miyano. Boundary detection for
bumps using the Gini’s index in messy classification problems.
Proc Int Conference on Cybernetics and Information
Technologies, Systems and Applications, 2006.
T. Yukizane, S. Ohi, E. Miyano, and H. Hirose. The bump
hunting method using the genetic algorithm with the extremevalue statistics. IEICE Trans on Information and Systems, 2006.
Y. Kiyonari, E. Miyano, and S. Miyazaki. Computational
complexity issues in university interview timetabling. Proc Int
Conference on the Practice and Theory of Automated
Timetabling (PATAT), 2006.
Y. Asahiro, T. Horiyama, K. Makino, H. Ono, T. Sakuma, and M.
Yamashita. How to collect balls moving in the Euclidean plane.
Discrete Applied Mathematics, 2006.
2007/5/14
全体会議
4
論文・会議録






Y. Asahiro, E. Miyano, S. Miyazaki, and T. Yoshimuta. Weighted
nearest neighbor algorithms for the graph exploration problem
on cycles. Proc Conference on Current Trends in Theory and
Practice of Informatics (SOFSEM), 2007.
H. Hirose, S. Ohi, T. Yukizane. Assessment of the prediction
accuracy in the bump hunting procedure. Proc Hawaii Int Conf
Statistics, Mathematics, and Related Fields, 2007.
Y. Asahiro, E. Miyano, H. Ono, and K. Zenmyo. Graph
orientation algorithms to minimize the maximum outdegree.
International Journal of Foundation of Computer Science, 2007.
Y. Asahiro, J. Jansson, E. Miyano, H. Ono, and K. Zenmyo.
Approximation algorithms for the graph orientation minimizing
the maximum weighted outdegree. Proc Conf on Algorithmic
Aspects in Information and Management (AAIM), 2007.
K. Iwama, E. Miyano, and H. Ono. Drawing borders efficiently.
Proc Int Conf on FUN with Algorithms (FUN), 2007.
Y. Asahiro, E. Miyano, and S. Shimoirisa. Grasp and delivery
for moving objects on broken lines. Theory of Computing
Systems, to appear.
2007/5/14
全体会議
5
経路最適化
2007/5/14
全体会議
6
オフラインモデル＋静的
 TSP （巡回セールスマン問題）
 固定点
 移動距離
 最小化問題
 制約（グラフ，平面，三角不等式，．．．）
2007/5/14
全体会議
7
オフラインモデル＋動的
 低速移動TSP
 低速移動点
 移動距離
 最小化問題
 制約（軌跡，移動点個数，．．．）
2007/5/14
全体会議
8
オフラインモデル＋動的
 低速移動TSP
 低速移動点
 移動距離
 最小化問題
 制約（軌跡，移動点個数，．．．）
• Chalasani, Motwani, Rao, IWAFR (1996)
• Helvig, Robins, Zelikovsky. ESA (1998)
• Hammar and Nilsson, ICALP (1999)
2007/5/14
全体会議
9
（課題） オフラインモデル＋動的+
 高速移動TSP
 高速移動点
 個数
 最大化問題
2007/5/14
全体会議
10
（課題） オフラインモデル＋動的+

Y. Asahiro, E. Miyano, and S. Shimoirisa. Grasp and delivery
for moving objects on broken lines. Theory of Computing
Systems, to appear.
条件：
 容量制約： １
 移動軌跡： 折れ線上
結果：
 直線を移動する場合の
O(n log n) 時間アルゴリズム
 一度以上曲った場合には MAXSNP困難
 2近似アルゴリズム
記事：
朝廣，小野，宮野，山下．移動物体回収問題．電子情報通信学会誌2007年3月号
2007/5/14
全体会議
11
（課題） オンラインモデル
 オンラインTSP
 局所情報
 移動距離
 最小化問題
 制約
A
?
2007/5/14
5
10
未知グラフ
全体会議
B
?
12
（課題） オンラインモデル
 オンラインTSP
 局所情報
 移動距離
 最小化問題
 制約
A
5
10
20
C
未知グラフ
B
?
?
2007/5/14
全体会議
13
（課題） オンラインモデル
 オンラインTSP
 局所情報
 移動距離
 最小化問題
 制約
A
5
10
B
40
20
D
C
?
2007/5/14
前進 or 後退
全体会議
?
14
（課題） オンラインモデル

Y. Asahiro, E. Miyano, S. Miyazaki, and T. Yoshimuta. Weighted
nearest neighbor algorithms for the graph exploration problem
on cycles, SOFSEM2007.
前進距離
既知
後退距離
 前進 or 後退？
ALG(Δ)
If Δ×（前進距離）＞後退距離， Then 後退
Else 前進
2007/5/14
全体会議
15
（課題） オンラインモデル

Y. Asahiro, E. Miyano, S. Miyazaki, and T. Yoshimuta. Weighted
nearest neighbor algorithms for the graph exploration problem
on cycles, SOFSEM2007.
10
既知
25
 前進 or 後退？
ALG(3)
If 3×（前進距離）＞後退距離， Then 後退
Else 前進
2007/5/14
全体会議
後退
16
（課題） オンラインモデル

Y. Asahiro, E. Miyano, S. Miyazaki, and T. Yoshimuta. Weighted
nearest neighbor algorithms for the graph exploration problem
Rosenkrantz,
Stearns, Lewis. SIAM J Comp (1997)
on
cycles, SOFSEM2007.
• ALG(1) は (log n)-競合
前進距離
既知
Kalyanasundaram and Pruhs, TCS (1994)
• 平面グラフに対して，ALG(3) は 16-競合
後退距離
 前進 or 後退？
ALG(Δ)
If Δ×（前進距離）＞後退距離， Then 後退
Else 前進
2007/5/14
全体会議
17
（課題） オンラインモデル

Y. Asahiro, E. Miyano, S. Miyazaki, and T. Yoshimuta. Weighted
nearest neighbor algorithms for the graph exploration problem
on cycles, SOFSEM2007.
ALG(Δ)
IF Δ×(前進）>後退， Then 後退
Else 前進
条件：
 サイクルグラフ
結果：
 ALG(1) は 1.5-競合
 1.5のタイトな例
 ALG(Δ1)の競合比は1.5以上
一般の場合
 任意の決定性オンラインアルゴリズムの1.25下限
2007/5/14
全体会議
18
ページ転送数最適化
2007/5/14
全体会議
19
オンラインページ転送
 Paging

オンライン・アクセスパターン
 Page単位
 転送ページ数
 最小化問題
CPU
2007/5/14
?
abc
def
?
全体会議
a
f
c
b
e
d
20
（課題） オフラインページ転送
 Paging

オフライン・アクセスパターン
 Page単位
 転送ページ数
 最小化問題
CPU
a ○○
b ○○
a
f
b
e
c
d
3回転送
2007/5/14
全体会議
21
（課題） オフラインページ転送
 Paging

オフライン・アクセスパターン
 Page単位
 転送ページ数
 最小化問題
CPU
abc
a
f
b
e
c
d
1回転送
2007/5/14
全体会議
22
（課題） オフラインページ転送
 Paging

オフライン・アクセスパターン
 Page単位
 転送ページ数
 最小化問題
abc
アクセスパターンが木の場合
CPU
• Gil and Itai. ESA (1995)
• Clark and Muro. SODA (1996)
a
f
b
e
c
d
• Diwan, Rane, Seshadri,1回転送
Sudarshan. VLDB (1996)
• Bender, Demaine, Frach-Colton. ESA (2002)
2007/5/14
全体会議
23
（課題） オフラインページ転送

Y. Asahiro, T. Furukawa, K. Ikegami, and E. Miyano. How to
pack directed acyclic graphs into small blocks. CIAC 2006.
条件
 オフライン・アクセスパターン
 有向非巡回グラフ（DAG）
 ページサイズ B
 最小化問題
B =2
結果
 1.5 の近似下限
 B = 2 の場合の 1.5近似アルゴリズム
 B = 3 の場合の 2近似アルゴリズム
2007/5/14
全体会議
24
目標
 最適化モデル
オフライン，静的，固定的
オンライン，未知情報
2007/5/14
全体会議
25

産学連携学 第 11巻 第 2号 2015年 6月 目 次

宿題4問題