Reverse-Fitを用いた単純な2次元ビンパッキングのアルゴリズム

元データ 2004-01-30 一般社団法人情報処理学会

概要

高さと幅が1以下の長方形を辺の長さが1の単位正方形に重ならないようにパッキングするとき,必要な正方形の個数を最小にするという問題が2次元ビンパッキング問題である.この問題に対して.2002年に発表されたCapraraのアルゴリズムは漸近近似率が良くなるように作られたものであり,現実的な入力においては多くの場合良い結果とならない.本論文では現実的な入力において良い結果を出せるようなアルゴリズムを提案し,計算機上に実装して実験的性能の比較評価を行う.

著者

浅野 孝夫 中央大学理工学部情報工学科
Ono T Graduate School Of Information Science Nagoya University
浅野 孝夫 中央大学大学院理工学研究科情報工学専攻
佐々木 浩高 中央大学大学院理工学研究科情報工学専攻

関連論文

NP-completeness of generalized Kaboozle (コンピュテーション)
単純多角形の生成に関する発見的手法(セッション2)
眼底断層画像の領域抽出・解析手法に関する研究 : 緑内障診断に用いられる視神経構造特徴の自動測定(一般,First Person Visionのための認識・理解)
衝突確率を考慮したバッファ配置問題に対する計算機シミュレーションを利用した手法
搬送計画問題に対するネットワーク理論を利用したアプローチ
組合せ最適化問題に対する効率的手法
より大きな値の最近要素を求める定数作業領域アルゴリズム
グラフ及び領域空間に関する大域丸めの幾何学的性質について
平面点集合のk巡回路被覆問題: kが定数の場合の多項式時間近似スキーム
一般化KaboozleのNP完全性
制約されたメモリ上での2値画像処理の技法
眼底断層画像の領域抽出・解析手法に関する研究 : 緑内障診断に用いられる視神経構造特徴の自動測定(一般,First Person Visionのための認識・理解)
眼底断層画像の領域抽出・解析手法に関する研究 : 緑内障診断に用いられる視神経構造特徴の自動測定(一般,First Person Visionのための認識・理解)
幾何問題に対する定数作業領域アルゴリズム(1)
幾何問題に対する定数作業領域アルゴリズム(2)
2値画像上で連結成分を消去するその場でのアルゴリズム
正方行列上に一様に整数を配置する方法の提案とディジタルハーフトーニングへの応用
計算幾何学でいかに論文を書くか(学生/教養のページ)
Constant-work-space algorithms for geometric problems (1) (コンピュテーション)
Nearest Larger Neighbors問題に対する効率の良いアルゴリズム (理論計算機科学の深化と応用)
Constant-Working-Space Algorithms (Computational Geometry and Discrete Mathematics)
定数の作業領域だけを用いて任意の角度で画像をスキャンする算法
直線上に整数点を一様に生成する算法
定数作業領域だけを用いたユークリッド距離変換アルゴリズム
定数作業領域だけを用いた連結成分ラベル付けアルゴリズム
ゾーンダイアグラム : 存在性,一意性,アルゴリズム
ディジタルハーフトーニングへの応用に向けての魔方陣の一般化(2)
ディジタルハーフトーニングへの応用に向けての魔方陣の一般化(1)
距離和最小化基準による点集合の折れ線近似
精密製造工程における不可視物体の計算幾何学的検知手法
距離和最小化基準による点集合の折れ線近似
復元画像の最適化によるハーフトーン化 : ハードウェアによる高速化を含めた新しい手法
適応型クラスタードットハーフトーニング
ディジタルハーフトーニングに関連する組み合わせ問題と幾何問題
画像処理に対する新たなアプローチ : アルゴリズム研究者の挑戦(招待講演)
画像処理 : アルゴリズム工学研究者の視点
画像の等高線表現を利用した画像検索手法
Matrix Rounding under the L_p-Discrepancy Measure and Its Application to Digital Halftoning
実数行列のチェッカーボード型整数化について
ディジタルハーフトーニング : ネットワークフローアルゴリズムによる最適化
計算幾何学
線状ロボットのd_1-最適な移動計画問題の新たな特徴付け
ディジタル化された領域の周囲長
格子充填曲線の存在条件
Digital Halftoning : Formulation as a Combinatorial Optimization Problem and Approximation Algorithms Based on Network Flow (Algorithm Engineering as a New Paradigm)
LEDA : 複雑なアルゴリズムも簡単にプログラム化できる魔法のツール
LEDA+アルゴリズム=プログラム (アルゴリズム工学)
ディジタル直線検出問題の計算量に関するアルゴリズム論的考察(情報基礎理論ワークショップ(LAシンポジウム)論文小特集)
木構造ネットワーク上の車両配送計画問題の新しい近似解法
Repairing Flaws in a Picture Based on a Geometric Representation of a Digital Image
画像処理と計算幾何学--Visual Computing 計算幾何学は画像処理に如何に貢献できるか (特集 計算幾何の拡がり--情報科学・応用数理・数学にまたがる発展)
画像の等高線表現とその応用
クラス間分散最大区間を求めるアルゴリズムと多次元への拡張
Contour Representation of an Image with Applications
線状ロボットのd_1-最適な移動問題(2)
ランダムスペースフィリングカーブに基づくディジタルハーフトーニングのアルゴリズム
線状ロボットのd_1-最適な移動問題
イメージ切り出しに関するアルゴリズム
配送計画問題に対する近似アルゴリズムの実際的性能評価
半局所改善に基づく3-Set Cover近似アルゴリズム
4P-2 非一様並列機械型スケジューリング問題に対する近似アルゴリズムの実験的評価(アルゴリズムとその応用,学生セッション,ソフトウェア科学・工学)
最小マンハッタンネットワーク問題に対する近似アルゴリズム
合流フローの混雑最小化アルゴリズムに対する実験的性能評価と貪欲改善
均等多品種フローの最大化アルゴリズムにおける効率の実際的改善
オンラインスケジューリングアルゴリズムの実験的性能評価
施設配置問題とスケジューリング問題に対する高性能アルゴリズムの実験的性能評価
摂動法によるMAX SAT近似アルゴリズムの改良
MAX SATに対するハイブリッド法
摂動法によるMAX SAT近似アルゴリズムの改良
Approximation Algorithms for MAX SAT : Semidefinite Programming and Network Flows Approach
MAX SATに対するYannakakisのアルゴリズムの精密化
グラフ次数列問題
MAX SATに対する近似アルゴリズム
MAX 3-SATに対する高性能近似アルゴリズム
RECENT DEVELOPMENTS IN MAXIMUM FLOW ALGORITHMS
SATアルゴリズムの計算時間の実験的評価
計算幾何学的手法を用いた基本図形の認識
MAX SATに対する新しい3/4-近似アルゴリズムとより高性能な近似アルゴリズム
An Improved Algorithm for the Nearly Equitable Edge-Coloring Problem
MAX SATに対するより単純な近似アルゴリズム
Reverse-Fitを用いた単純な2次元ビンパッキングのアルゴリズム
Designing High-Quality Approximation Algorithms for Combinatorial Optimization Problems(Special Issue on Algorithm Engineering : Surveys)
On Approximation Algorithms for Coloring k-Colorable Graphs
An Approximation Algorithm for MAX 3SAT
4P-1 最小遅延パス問題に対する近似アルゴリズムの実験的評価(アルゴリズムとその応用,学生セッション,ソフトウェア科学・工学)
サービスを考慮した施設配置問題に対する近似アルゴリズムの実験評価(セッション1)
施設配置問題に対する近似アルゴリズムの実験評価(組合せ最適化(3))
A Simpler Analysis of Goemans and Williamson's LP-relaxation for MAX SAT (計算機科学基礎理論の新展開 研究集会報告集)
代表的施設配置近似アルゴリズムの実験的性能評価
スタイナーネットワーク問題に対する近似アルゴリズムの実験的性能評価
ネットワーク設計問題に対する近似アルゴリズムの実験的性能評価
半正定値計画とその応用 : 第4回半正定値計画を用いた近似アルゴリズム
MAX 2SATに対する近似アルゴリズムの実際的性能評価
施設配置問題に対する近似アルゴリズムの実際的性能評価
論理システム解析のための高性能近似アルゴリズム : 四角い問題を丸くして解く(近似アルゴリズムに関する最近の話題)
分散システムにおけるプライオリティ付き相互排他制御
MAX SATに対する近似アルゴリズムの実際的評価
五十嵐善英, 西谷泰昭, アルゴリズムの基礎, コロナ社, 1997年
計算幾何学
グラフ・ネットワーク最適化 (ユーザのための数理計画応用)
▼もっと見る