Title bin-packingの亜種ふたつにかんする備忘録 Author(s) Citation 小樽商科大学人文研究 (2014), 127: 91-102 Issue Date URL 飯田, 浩志 2014-03-17 http://hdl.handle.net/10252/5296 Rights This document is downloaded at: 2015-01-31T19:48:16Z Barrel - Otaru University of Commerce Academic Collections 91 b i r トp a c k i n gの亜種ふたつにかんする備忘録飯田浩志* この小品は， b i n p a c k i n g問題の亜種(拡張もしくは変形)と in-packingと b i n なるふたつの問題，先行制約っき b s t r e t c h i n gにかんする覚書になる. キーワード:組合せ最適化， b i n p a c k i n g問題本稿は， b i n 予a c k i n g(ビン詰め)問題の亜種となるふたつの問題i先行制約っき b i n p a c k i n gとb i n s t r e t c h i n gにかんするメモ書きである. 初版が出てのち改訂されることのない専門書が多い中， 2 0 1 2年初頭に Korteと Vygenの手になる成書 [ 8 Jは，第 5版が刊行された.その中の第四 i n p a c k i n g問題は，各 ωJε(O，l J なる実数列 ω 1，章で取り上げられてゐる b すペ Wz， … ， ωnが与へられ ( w e i g h tの ω)，それらを容量 1のビン ( b i n )に凡て詰めるにあたり，使用するビンの本数を最小にする詰め方を求めるといふ，有名な巡回セールスマン問題と同じく強 NP困難な組合せ最適化問題である. e m )jをビン b( j )に a s s i g nする函数を b:{ 1 ，2 ， … ，n }→ 式で書くと，項(it { 1 ，2 ， … ，k }として，勝手なビン i( 1三三 t三二 k )について 2 Jj: b(j)=i叫三二 1なる制 (・)を求めるのが b i n予 a c k i n gである.最小なったビ約下で hを最小にする b ン数 hを最適値と呼ぶ. i np a c k i n gに対してはさまざまな近似算法 *1が提案されてゐる.近この b 悶似算法とは，一般に最適な詰め方ではないがゆゑに最適値より大きい数(近 *E m a i l :h i r o g g i i d a @ m e . c o m * 1 本稿では，アルゴリズムの意味で算法といふ語を用ゐる. 92 人文研究第 1 2 7輯似値)を返してしまふけれど，最適値を求めるよりも格段に早く終る手法を指す. i n p a c k i n gのやうな最小化問題，ことに少し言葉の定義をしておき度い. b l .e .何ごとか ( b i n p a c k i n gなら使用するビンの本数)を最小にすることを日ぉ的とする問題への近似算法 A に於いて，どんな問題例(in s t a n c e ) 1についほど己ても， A( J)と OPT( J)が Iに A を施して得られる値と最適値(>0とする) J)ζ kOPT( J )が成り立っとき， k (云 1 )を A の絶をそれぞれ表すとして A( 対性能比と呼ぶことにする ( A (J)注 OPT(J)に注意すると，絶対性能比 1は，近似値ではなく最適値を返す算法を暗に示してゐる).またこれに，定数 C を加えた A( J )skOPT(J)+cが成立するとき，kを A の漸近的性能比と呼ぶ J J)やことにする.以降では，あいまいさを生じるおそれがないのであれば A( OPT(J)の Iを略すことがある.例へば前述したやうに，最小化問題への近似二 OPTと書算法 A は常に最適値以上の値を返すわけだけれども，これを A三くことカ宝ある. b i n p a c k i n gへの代表的な近似算法である FFと FFDに就いて，簡単に説明しておく. FF( F i r s t F i t )は， ω1から ωnの順に，最初のビンから次次に見ていって最初に(fi r s t ) 詰められる ( f i tする)ビンに詰め，入るピンが無ければ新たなビンを用意して詰める，といふ算法である (ω1は必ず最初のビンに這入る). FFD ( F i r s t F i tD e c r e a s i n g )は， ωJを大きい順に整列 ω1と二 μz二三…ミ Wn してから FFを実行する.たとへば問題例 { 0 . 5，0 . 4，0 . 3，0 . 3， 0 . 3，0 . 2 }では OPT=2，最初のビンに 0 . 5と 0 . 4が入ってしまって FFD= 3になる.じつは乙の例は， FFDの絶対性能比が1.5より良く(小さく)ならないことを示してゐる.具体的には， FFD三 ( 3/2)OPTの等号が成り立つ i 列になってゐる.かうした伊』を， t i g h tな{列!といふ * 2 * 2b i n p a c k i n gで P宇 NPの下，いかな近似算法を以てしでも絶対性能比1.5未満は無理 [ 8，p .4 7 2 J . この，あらゆる近似算法を考慮した上での絶対性能比の下限 ( in f i m u m )1 .5を指して， b i n p a c k i n gの a p p r o x i m a t i o nr a t i oは1.5と云ふ [ 8， p . 4 3 3 J . b i n p a c k i n gの亜種ふたつにかんする備忘録 93 2 0 0 7年に Dosa[ 3 Jは， 1 9 9 0年から暫く動かなかった， FFDの漸近的性能比を表す式 FFDζ(11/9)OPT十 l中の定数項 1が，じつは 6 / 9で t i g h tにな i g h tな例は， { 1/2+ε，1/4十 E ，1 /4-2E}X4+{ 1/ 4十 2 E ，ることを示した. t 1/4十 2 E ， 1/4-2E ， 1/4-2E }X2である . ζ れが OPT=6，FFD=8(ニ (11/9)OPT十 6 / 9 )を与へる.ここに E>Oは，非常に小さい実数を表す. 0 1 0年に Xiaと Tan[ 1 1 Jは， S i m c h i L e v i[ 1 0 J による FFの絶対他方 2 / 4を 1 2 / 7に改良した [ 8，p .4 7 5 ] . この 1 2 / 7の証明には，漸近的性性能比 7 能比を表す式 FF三二 ' 17/10)OPT十 7 / 1 0が使われてゐる *3 こちらも， Xiaと Tan[ 1 1 J が導いた結果である(だから，文献口 1 J のタイトルが bounds， / 1 0は， 1 9 7 6年の 9 / 1 0以来じつに 3 4年ぶと複数形になってゐる).定数項 7 りの改良とのこと [ 1 1，p .1 6 6 9 ] . ただし t i g h tとは示されておらず， FFDの / 3で終結した一方， FFのそれ 7 / 1 0は漸近的性能比を表す式中の定数項は 2 未決である.さらに FFにかんしては，絶対性能比についての議論も終つてな iaとT a n [ 1 1 Jの推測どおり1.7 であると証明されるか，はたまた OPT= い.X 7 ，FFニ 1 2を与へる問題例が見つかるか.云ふまでもなく1.7と 1 2 / 7の聞で決着する，といふ可能性もある. i n p a c k i n gそれ自体への研究も然る事ながら b i n p a c k i n g 以上のやうな b の亜種(拡張あるいは変形)となる問題も提案されてゐる.たとへば，各ビ n l i n e(後述)で各ビンンに就いてーヶだけならビンをはみ出しでも可とか， o e s e l l iとの中が大きい順になるやうに詰める問題などがある(それぞれ， C R i g h i n i[ l J，Dosa他 [ 4 J等を参照され度い).以下ニ節では，最近たまたま i n p a c k i n gと b i n s t r e t c h i n gそれぞれにかんする文目にした先行制約っき b 献についてのメモ書きを残しておくことにする. iとC h e n[ 9，p .3 0 0 J でも触れられてゐるやうに， FFの漸近的性能比判例へば L は1.7より良くならないことが知られてゐる. 94 人文研究第 1 2 7 輯先行制約っき b i n p a c k i n gに提案された下界に就いて D e l l ' A m i c o他 [ 2 Jは，先行制約っき b i n p a c k i n gを e x a c tに解く手法を提案するうえで，最適値の下界(見積もり)をいくつか考案してゐる.なかでもらと L 4に就いては，最悪の場合の性能比がそれぞれ 1 / 3，1 / 2であることを示してゐる.本節では其れら下界ふたつに就いて少し書きとめておき度い. まづ，本節で扱ふのは使用するビン数の最小化問題であって，必要最低限のビン数を示す最適値より大きくない値が下界であり，その見積もりを表してゐる (0-1ナップサック問題のやうな最大化問題なら上界にあたる).精度の良い下界は，分枝限定法を適用するにあたって展開するノード数を減らすために重要な役割を果たす.ただ，下界の精度が良いに越したことはないけれど，一般に下界を得るまでにかかる時間と精度とのあいだには t r a d e o f fの関係がある.拙稿 [ 5 Jで示したやうに，精度が多少悪い見積もりであっても，それが素早く求まるのであれば，全体として見れば実用になることもある. b i np a c k i n gは，いずれも非負重量判 ω1，ωぃ.，仇をもっ】 η ヶの項を容量 C のどン(通常は C ニ 1 ) に凡て詰めるにあたり，使ふビンの本数を最小に i n p a c k i n gは，特定のふたつの項する問題であった.さらに先行制約のある b を詰めるにあたって，先行する方 ( p r e d e c e s s o r )を s t r i c tに番号の小さいビンに詰めなければならない(同じビンでは不可).先行制約は，項を節点とする，サイクルをもたない有向グラフで表すことができる.図 1に例を示す. 0-1ナップサック問題に先行制約があると，例へば図 lなら，項 jを詰めるにあたって項 t がナップサックに入っていなくてはならない;つまり，項 t 抜きで項 jを詰めることはできない [ 7， 1 3 . 2節J .bin-packingでの図 lは，先述のとおり項 iを詰めるビンの番号が項 jを詰めるビンのそれよりも確か * 4重量 Oの項は，先行制約がある場合には意味を持たせることができる.例へば，ふたつの項がそれぞれ格納されるビンの聞に少なくともひとつビンを挟みたい (隣にはしたくない)といふ向きには，先行制約を表すグラフに於いて当該二項を結ぶ校の中間に重量 0のダミー項を設けるとよい. b i n p a c k i n gの亜種ふたつにかんする備忘録 95 の一一一図 1 項 iは項 Jに先行するという制約 ie .b ( i )<b( j )を要請する. に小さくあること， . D e l l ' A m i c o他 [ 2 Jは，先行制約っき b i n p a c k i n gへの最適解を求める手法を提案した.その手法は分枝限定法に基づくが，その分校限定法を実装する 3と L 4に就いては，最悪のにあたって幾つかの下界を考案してゐる.こと L / 3，1 / 2であることを，しかも t i g h tであることを場合の性能比がそれぞれ 1 も示してゐる ( t i g h tであることから，求められたら，L 4それぞれの性能比の導き方に改善の余地なし).このことについて以下，すこ，しメモっておく. 4 e l l ' Am i c o他 [ 2 J に倣い，とある問題のいかなる例 Iについても，以降 D その最適{直 OPT(J)と下界 L (I)(ζOPT(I))について Eζ L(J)/OPT(I) (三 1 )を最悪の場合の性能比，または単に性能比と呼が成り立っとき，この E ぶ、ことにする.たとへば性能比 Eニ 1 / 2の下界なら，最適値の半分より悪い ε のとき， (小さい)見積もりは出さない，と云ふこと.これに加へてイ > >L(I)/OPT(I)を満足する問題例 Iの存在を必ず示せるなら E ' Eは t i g h t といふ * 5 (もうこれより大きくできないギリ). ゆるさて，最適値の見積もりには，元の問題におげる制約条件を緩めた問題を考える.制約条件を緩和した結果，元の問題よりも実行可能解(制約条件を凡て満たす解)が増えるから最適値が向上するであらう，といふ理屈である. 一般的な緩和の枠組みとして線形緩和，ラグランジュ緩和，代理緩和等あるけれど，先行制約を投げるみ ζ とで緩和する，つまり通常の b i n p a c k i n gと看倣すことで得られる下界が L l:=r~j 助/cl ( K o r t eと Vygen[ 8，p .4 7 3 J ) * 5[ 2，p .1 4 9 3 J では，だらう. i ff o ra n yc '<c ，と書いたあるものの，不等号が逆の誤植 96 人文研究第 1 2 7 輯で* 6 逆に先行制約のみ考慮してビンの容量を忘れる，つまり先行制約を表す zである.たとへば先行有効グラフに於いて，最長パスを構成する節点数が L 制約に推移的なものがなく，図 1のやうな二項間の関係で凡てが完結すると zニ 2である(図 2参照).これら下界ふたつに就いては，最適値(必要最きL かかわ低限のビン数)がいくらでも大きくできる(=n )にも拘らず常に 1を返す最 3: =m aX{Ll，L z }とし悪の例をそれぞれに対して簡単に構成できるけれど，L / 3が出てゐるのは面白い. ただけで性能比 1 定理 1が，下界 L 3の性能比は 1 / 3だと主張してゐる.さらに証明の最後には，項数 n→ ∞ のときに L3/0PTが上から 1 / 3に限りなく近づく例題がある証明中で構成される実行可能解 H が使うビン数は最適値以上につき，最終的に，最適値が 3L 14 ) の前に，先 3以下であると云ってゐる.また，式 ( i n p a c k i n gにおける最適解ではロード(詰められた項行制約がない通常の b の重量の総和)がどンの半分未満(実際には半分以下* 7 )であるやうなビンは図 2 L2はビンの容量を気にしない * 6 天井 ( c e i l i n g ) 函数 r1は，小数以下を切り上げる. r Z . 3 13 . ニ * 7 だから，細かいことなんだけど，半分以下しか入つてないかも知れないビン一本 1 4 ) は厳密に不等号で成立し，最終的に 1 / 3< の中味のことを加味せずとも ( L3/0PTではあるまひか. b i n p a c k i n gの頂種ふたつにかんする備忘録 97 高高ひとつとある.といふのは，もしそんなビンがふたつあったら，合はせてひとつにしてビンを減らせるからである. 4は，先行制約を表すグラフにおける最長ノ Tスを与へる項群 P の元下界 L それぞれがひとつずつ収められてゐる L 2個のビンに就いて，残りの項全体の集合 Qから，先行制約があって同じビンには入れられない項の組を考慮しつつ最初から全部は入らない項を排除しつつ，その一部でも構わないのでその L2個のビン全体に向かつて重量合計/を流し込み(最大流問題)，結果として余る ~jEQWj - fについては Llと同じ考え方 ( 1 1 ) をあて撮める，といふものである. 4の性能比が 1 / 2であることが示される.証明は定理 1のそれ定理 2で，L と同じ初期解 H (ビン数 L 2 )から始まり，各ビン tには最長ノ fスを与える項群 P の元 ρ(i)がひとつずつ収まってゐる. i )を通常の b i n p a c k i n gとして解いたとき(ビン数 1 ; )，証明の途中，R( ( i )がもっともロードの少ないビンに入らない場合項t ( B ) について:もし叫(i)が C/2以下であれば，それが入らない解であるなら，どのビンのロード ( i )が R ( i )U{ t ( i ) }の最軽も C/2を超えてゐるし ;C/2より大きければ， t 量であることから，R( i )に属する元の重量はどれも C/2を超えてゐることになる *8 よって，どっちの場合であっても ( C / 2 ) l i<~jER (i)叫がしたがう. 最終的に定理 1の証明と同様，ここで構成される実行可能解 H の使うピ L 4以下ン数 ZHが ZH三 2Lを満たすから，最適値が 2 つまり， 1 / 2 : ' 二 L4/0PT*9. 以下では，話を簡単にするために慣例に倣って C=lとする.定理 2の証 / 2が t i g h tであることを示すために，ム/OPTを上からいくら明の最後に， 1 ほんとうに些細なことながら [ 2，p 1 4 9 6 J では，t ( i )が R( i )U{ t ( i ) }の中で最小のピン ( b i n ) とあるけれど，最小の項(it e m ) のミスプリ. * 9小さいことで恐縮だが，解 H を構成する各ビン iに於いて， C 仰 (i)<ωt( i )十 LJjES(i )ω Jでなければ S ( i )の最適性に反する一-S ( i )に加えてはもう何も入ら ω 州 )+ LJj e s( i) ω j )であり，最終的に 1 /2< ないはず.したがって f<記乞 1( L4/0PTではないか. *8 目 98 人文研究第 1 2 7輯でも 1 / 2に近づけることのできる例題として，先行制約は皆無で，凡ての項 / 2十 εなる例 ( Eは，十分小さい正の数)が提示してある.そこでの重量が 1 項数 n は偶数であり，先行制約がないから例えば P={1}として，どのふたつの項も同じピンには入らないので Qから P に伸びる枝はなく 1=0であ z=1 と合はせて L 4=1 十 r~jEQωjl り，L =r 1十 ( 1 / 2十 ε)(n-1)1ェ r n/2+1/2+(n-1)叶ニ η/2+1.ゆゑに L = L=n / 2十 1を得る.思ふに， 4 1 / 2十 1より大きい下界を返す簡便な手はないものだらうか.それこの例に n lに替はって L 4を良くするやも知れない. がL b i n s t r e t c h i n gにかんするメモ i n s t r e t c h i n gへの Ke l 1 e r e rと Kotov[ 6 Jが提案した算法一一号 i 本節は， b 伸し係数これまでの最小値1.6を塗り替へる 1 1 / 7= 1 .5 7 1 4 2 8を実現するーーにかんするメモになる. 用意された容量 1のビン m ヶに凡てを納め得ることがあらかじめ分かつ n l i n eで次次にやってくる端からビてゐる，それぞれが重さを持つ項の列が o ン m ヶに詰めてい〈ことを考える.通常，ビンの容量がそのままで o n l i n eの格納は無理だから *10 ビンの容量を s (二三 1 )に引き伸すとして，この引き伸す s t r e t c h i n gf a c t o r ) sの最小化を目的とするのが b i n s t r e t c h i n gであ係数 ( る. m=lならもちろんビンを伸ばす必要はなく s =1 . Ke l 1e r e rと Kotov[ 6 Jが提案した， b i ns t r e t c h i n gへの引伸し係数 1 1 / 7を n l i n e算法は，ふたつの段階 ( p h a s e )から構成される:段階 1[ 6，実現する o p . 3 4 5の図 1 J では，段階 2で使うパッチの列を構成するための準備を行う. 例へば s e q u e n c e s { 0 . 4，0 . 4，0 . 5，0 . 6 }と { 0 . 4，0 . 4， O .7 }では，ふたつ日の 0 . 4を格納すべきビンが異なるが， o n l i n e算法は今の項の後にどんな列が続いてくるか知らない. o n l i n e算法は o f f l i n e算法(開始前に全情報が開示される)のように振る舞えるけれども逆は無理.前出の FFは o n l i n e算法だけど， FFDはさうでない [ 8，p .4 7 7J . *10 b i n p a c k i n gの亜種ふたつにかんする備忘録 99 具体的に段階 1は 3 eBζ msB(ニ mB十 s B )三二3 eB十 3が成立した時点で終 sB，mB， f 2B それぞれ空ビン，小ビン，中ビン，大ビンの了する.ここに eB，総数を指す.各ビンはその中にある項の総重量別に次のやうに呼び分げられる: その名称は空ビン小ビン中ビン大ビン超ビン中味の総重量 w ( B )が O 0<ω ( B )玉 4/7 4 / 7<ω (B)ζ11/14 1 1 / 1 4<ω (B): S : :1 ω(B)>1 加へて各項の名称も，その重量がこの区分けに準じたものになる.段階 1終了時に sB>0のとき，段階 2では基本的には三つの小ビンと一つ'の空ピン d からなるパッチと呼ばれる四つ組 B の列 Bl ， B2， …，B k 'を構成し，小項 ( s m a l litem，: : 0 : ; :4 / 7 ) と中項 (mediumitem;( 4 / 7，1 1 / 1 4 J ) を前のノてッチから大項 O argeitem; ( 1 1 / 1 4，1 J ) を後ろのパッチから FFで詰めていく. どのビンにも入らないとき，今のパッチを閉じて次のパッチを開ける.段階 1の終了条件に関聯して，Aニ msB-3eBと定義される .A=0なら最後の : ニe B )はビン四つ;でなければ最後のパッチ k 'ニh十 1は空ノてッチ k'=k( 1三 A三 3 ) . また，大項は小ビンに入る (ζ1+4/7= 1 1 / ピンなしでビン数 A( 7;ついでに逆で，小項は大ビンに入る). 段階 1で特徴的な点として， @小項を集めても中ビンにはならない.小項が ( o n 1 i neで)来たとき， argeitemb i n，大ビンか超ビン)に入れる(結果，大項の入るビン O 大ピンが超ビンになるかも)か，小ビンに入れて小ビンのまま * 1 1か， * 1 1t i n y項 ( ζ 2 / 7 )を t i n yビンに入れても小ビンのままだから t i n yビンは高高ひとつ(補題 1( c ) ) . 100 人文研究第 1 2 7輯空ビンに詰めて小ビンを作るかの三通りしかない. @中項が絡むのは，それがビンに一つだけ入って他は無しか，あるいは 1 / 1 4十 1 1 / 1 4ニ 1 1 / 7でギリ)かの二通りだけ二つ入って超ビン(玉 1 (補題 1の ( b ) と (e)).つまり中項は，他の種類の項と一緒になることがない. @大項を空ビンに入れる前に考慮するのは，最大の重量を持つ小ビンのみ* ' 2で，先に触れたように，中ビンとは絡まない. が挙げられよう. 補題 lの(f)ではらB ニ oor f2 B ニ O~ とある.段階 2 における算法の説明では， C ase1が sB=0のとき， Case2が 2 f Bニ 0 ，s B>0のときで， sBニ 2 f B=0の場合の指示は特にない. Case1に含まれる特殊な場合ではあるけれど，ちょっと気になる.補題 1の(f)の証明で，s B = 0，2 f Bj= 1か j っ時刻 jで来たのが小項のとき，大ビンにその小項が加へられて超ピンに H1 なったとすると，SB =2 f BH 1=0は起こり得る.では実際に sB= f 2B=0 のとき，定理 1の証明で C ase1 ，i . e .sB= 0の場合には eB=Oが示されてゐる.したがって，凡てのビンのロード(入ってゐる項の総重量)が 1を超え ' 3ところへ mBζ1(補題 1の(c))を加味すれば， mB二 1しることはない * かない(超ビンが無くてもさうだけれど，そもそも超ピンが無いなら m ニ 1 で，さう云った例は最初から除外してよい).よって，段階 2で、加へられる項は乙の，唯一ロードが 1未満の中ビンに残らず入ることになる.結局，段階 1の終了時に sB=0のときは，段階 2ではただ FFで残りを詰めるとあるけ * ' 2なぜ小ビンの中でも最大の重量のなのかは，補題 1の(f)の証明と関係してゐる. * 1 3項全体は最初に与へられた m ヶのビンに入ることが前提なので，全部のビンの . . . . . r -， . r十 1 k' ロードが lを超えるのは物理的に不可能.同様に，定理 1の証明で B，に属するビンのロードが平均して lを超えてゐるのだから，残るひとつのパッチ Brに属する四つのビンのロード，1.e .段階 1で入ったのと段階 2で入る予定の項の総重量が 4以上のはずがない.これは，ビンが三つ以下の r=k十 1のときも同じ. 川 b i n p a c k i n gの亜種ふたつにかんする備忘録 101 れど，sB QB=0であれば FFを持ち出すまでもないやうだ. こ段階 1終了時 eB=sB=Oで全部が中ビン以上である Case1につけ加へて， (もともと全部の項が mヶのビンに入る前提なんだから)この場合には 1 / 2を超える中項や大項が j u s tmヶ(結局，中項は一個以下)で，段階 2で ζ4/7)である.まだ算法が未終了の時点でやってくる残りの項はみな小項 ( m ヶのビン全部のロードが二三 1は不可能で，どれかのビンのロードは<1. / 7=1 1 / 7が， C ase1 したがって， FFが乙れから入れるビンについて <1十4 では保証され続ける. 定理 1の証明中最後の段落 rニ k+1( 最後に開いたパッチが列の最後尾 )のとき:ビンが二つ Bh B2の場合で，でEつ A>0 最初の項とすると， R に段階 1で入った重量との総計は 2 -ω (BI)-XI<3/7未満だから， <3 / 7十1= 1 0 / 7<1 1 / 7なので， X Iが B Iに入らなかった X I以降にやってくる残り重量 XIが大項であったとしても X Iを含めて以降全部が品に入る，と云ふことなのだらう.別の見方をすると， X Iを含んで以降の残りを凡て品に詰めたとして， ω(B ) 十ω( B 2 )<2 だから ω(R)<2 ω( B 1 ) x I十XI<3 / 7十1= 1 0 / 7 . 1 さらに r=k+1でビンが三つのとき，最初に B Iに f i tしなかったに入ったら， X Iがまだどのビンにも X Iが品 a s s i g nされていないときの s n a p s h o tに BI)+ω(品 )+ω(品)十均十(残り )<3とすると， ω(品)十(残り)< 於いて ω( ω(品 )+ω(品)+(残り)<3一ω(B1)-xI<1 0 / 7 .これから， XIが島に入ったあと残り全部が品に入る， XIが B2 にも f i tしなかったら *14 w(B1)十y十 ω(品)十 XI十(残り)<3から(残り )<ω(品)+(残り )<3ω (BI)-y-xI< * ' 4本文中 W a s i n(b)~ とあるやうに，最後に閉じられるパッチ B，にかんする考察の ( b ) と同じく，B ，に最初に入らなかった m が(まだ段階 2では手つかずの) &に入らないとは，大項は小ビンに入るから，つまり&が(中項 y を含む)中ビンだったということ(なおかつ m は大項一一中ビンに中項は入るから).存在すれば唯一の中ビンは，先頭パッチ B，のふたつ日に配置してある(ついでにいうと，存在すれば唯一の t i n yビンは B，のひとつ呂に配置済)から，これは，パッ 1 '= 1 )でしかもビンは三つ(段階 1の終了時に空ビン無し)とチがひとっきり ( 云ふことになる.段階 1終了時に e B (=k )=0 ，msB=A=3はアル. 人文研究第 1 2 7輯 102 1 0 / 7 y . よって品では y+( 残り)<10/7となって m後の残りが全部入る，と云ふ解釈でいいのだらう，たぶ、ん. 最後に記述されてゐる，sの下界 4/3と，そこで示された 1 1 / 7の差がどう云ふ風に縮まっていくのか，興味深いところである. 参考文献 [ l J Alb巴r t oC e s e l l iandG i o v a n n iR i g h i n i，Ano p t i m i z a t i o na l g o r i t h mf o rt h e o r d 巴r e do p e n e n db i n p a c k i n gp r o b l e m .Q ρe rRes5 6 ( 2 )4 2 5 3 6( 2 0 0 8 )h t t p : / / d x . d o i . o r g / 1 0 . 1 2 8 7/ o p r ・ e . 1 0 7 0 . 0 4 1 5 . o s eC a r l o sDiazD i a zandManuelI o r i，Theb i np a c k i n g [ 2 J MauroD e l l ' A m i c o，J problemw i t hp r e c e d e n c ec o n s t r a i n t s .OperRes6 0 ( 6 )1 4 9 1 5 0 4( 2 0 1 2 )h t t p : / / d x . d o. io r g / 1 0 . 1 2 8 7/ o p r e . 1 1 2 0 . 1 1 0 9 . [ 3 J GyorgyDosa，Thet i g h tboundo ff i r s tf i td e c r e a s i n gb i n p a c k i n ga l g o r i t h m i sFFD(I): S :1 1/90PTI 十 6 / 9 .I n :B .Chen，M.P a t e r s o nandG .Zhang( E d s . ) 6 1 4， p p .1 1 1， S p r i n g e r2 0 0 7， h t t p : / / d x . d o i . o r g / 1 0 . 1 0 0 7/ ESCAPE2 0 0 7，LNCS4 9 7 8 3 5 4 0 7 4 4 5 0 41 . [ 4 J GyδrgyDosa，Z s o l tTuza andD e s h i Ye，Binp a c k i n gw i t h“ L a r g e s tI n Bottom"c o n s t r a i n t :t i g h t e rboundsandg e n e r a l i z a t i o n s .JCombOptim( 2 0 1 1 ) h t t p : / /d x . d o i . o r g / 1 0 . 1 0 0 7/ s 1 0 8 7 8・0 1 1 9 4 0 8 0 . ida， An o t eont h emax-min0 1knapsackp r o b l e m .JCombQ戸t i m [ 5 JH i r o s h iI 3 ( 1 )8 9 9 4( 1 9 9 9 )h t t p : / / d x . d o. ip r g / 1 0 . 1 0 2 3 /A :1 0 0 9 8 2 1 3 2 3 2 7 9 . [ 6 J HansK e l l e r e randV l a d i m i rKotov，Ane f f i c i e n ta l g o r i t h mf o rb i ns t r e t c h ゆe rResL e t t4 1 ( 4 )3 4 3 6( 2 0 1 3 )h t t p : / / d x . d o i . o r g / 1 0 . 1 0 1 6/ j .o r. 12 0 1 3 . 0 3 . ing.O 0 0 5 . r i c hP f e r s c h yandDavidP i s i n g e r，Kn~ρsacl， P r o b l e m s . [ 7 J HansK e l l e r e r，Ul S p r i n g e r2 0 0 4 . [ 8 J BernhardKorteandJ e n sVygen，C o m b i n a t o r i a lOptimization-Theoη and A l g o r i t h m s( A l g o r i t h m sandC o m b i n a t o r i c s ，Volume2 1 )5 t hE d i t i o n，S p r i n g e r 2 0 1 2，h t t p : / / d x . d o. io r g / 1 0 . 1 0 0 7/ 9 7 8 36 4 2 2 4 4 8 891 8 . [ 9 J ChungLunL iandZhi-LongCh巴n，B i n p a c k i n gproblemw i t hconcavec o s t s o fb i nu t i l i z a t i o n .NavalResL o g i s t5 3 ( 4 )2 9 8 3 0 8( 2 0 0 6 )h t t p : / / d x . d o. io r g / 1 0 1 0 0 2 / n a v . 2 0 1 4 2 [ 1 0 J DavidS i m c h i L e v i，Neww o r s t c a s er e s u l t sf o rt h eb i n p a c k i n gproblem NavalResL o g i s t4 1 ( 4 )5 7 9 8 5( 1 9 9 4 ) [ l 1JBinzhouXiaandZ h i y iTan，T i g h t e rboundso ft h eF i r s tF i ta l g o r i t h mf o r t h eb i n p a c k i n gp r o b l e m .D i s c r e t eA p p l i e dM a t h e m a t i c s1 5 8 ( 1 5 )1 6 6 8 7 5( 2 0 1 0 ) h t t p : / / d x . d o. io r g / 1 0 . 1 0 1 6 / i . d a m . 2 0 1 0 . 0 5 . 0 2 6 . ω 目田田目目