第24回 KIDS

日時　　２００５年９月27日（火）　15:00--17:10

場所　　京都大学 ベンチャービジネスラボラトリー　２階セミナー室

プログラム　

15:00--16:00	辛川誠吾（永持研）	ユークリッド平面上のミニマックス部分木被覆問題
16:10--17:10	Rolf Harren（岩間研）	Constant ratio approximation algorithms for weighted container packing

---

概要

辛川誠吾（永持研）

題目

ユークリッド平面上のミニマックス部分木被覆問題

概要

本研究では, ユークリッド平面上に点の配置が与えられたときに,

それらの点をすべて被覆するk個の木の重みの最大値が

最小木の重み/kの1.934倍以下にできることを証明する.

この結果を用いることで, ミニマックス部分木被覆問題および

ミニマックス根付き木被覆問題と呼ばれる問題が

ユークリッド平面上の点に対して定義されている場合には

従来の近似アルゴリズムの性能をそれぞれ4から3.867へ,

2から1.934へ改善することができる．

---

Rolf Harren（岩間研）

題目

Constant ratio approximation algorithms for weighted container packing

概要

Given a set of rectangular 3-dimensional items, all of them associated

with a profit, and a single bigger rectangular 3-dimensional bin, we can

ask to find a non-rotational, non-overlapping packing of a selection of

these items into the bin to maximize the profit. This problem differs from

well-studied 3-dimensional strip- and bin- packing as we are to pack into

a single bounded bin.

We derive a (16 + epsilon)- approximation algorithm and improve the

algorithm to an approximation ratio of (9 + epsilon).