Access count of this item: 17

Files in This Item:
File Description SizeFormat 
IEICE_tec.rep_COMP97-69.pdf2.64 MBAdobe PDFView/Open
Title: 部分最適化問題の完全性
Other Titles: On the Completeness of Partial Optimiziation Problems
Authors: 宮崎, 修一  kyouindb  KAKEN_id
岩間, 一雄  KAKEN_name
Author's alias: Miyazaki, Shuichi
Iwama, Kazuo
Keywords: 最適化問題
部分最適化問題
部分MAXSAT
完全性
optimization problems
partial optimization problems
partial MAXSAT
completeness
Issue Date: 14-Nov-1997
Publisher: 電子情報通信学会
Journal title: 電子情報通信学会技術研究報告 = IEICE technical report : 信学技報
Volume: 97
Issue: 375
Start page: 73
End page: 79
Thesis number: COMP97-69
Abstract: 部分MAXSATは, MAXSATを一般化した組合せ最適化問題であり, スケジュ-ル問題等の現実社会に則した組合せ最適化問題を模倣する能力を持っている.また, 部分MAXSATは, 項の重みづけを施すことにより, 従来のMAXSATアルゴリズムを用いて, 効率良く解けることが実験によって示されている.このように, 部分MAXSATは有用な問題であるが, どのような問題を模倣することができるかを理論的に明らかにする必要がある.本論文では, 部分MAXSATの組合せ最適化問題のクラスでの完全性を示すことにより, 部分MAXSATが幅広い最適化問題を模倣可能であることを示す.また, 他の組合せ最適化問題に対応する部分最適化問題の完全性も示す.
Partial NIAXSAT (PMSAT) is a generalization of MAXSAT and has flexibility to simulate general combinatorial optimization problems, such as scheduling problems. However, it is shown empirically that it can be solved efficiently by local search algorithm for MAXSAT using weighting strategy. In this paper, we show the completeness of PMSAT and other partial optimization problems in order to demonstrate their usefulness.
Rights: © 1997 電子情報通信学会(IEICE)
URI: http://hdl.handle.net/2433/227136
Related Link: http://db.ieice.org/gakkai/show.php?id=95218
Appears in Collections:Journal Articles

Show full item record

Export to RefWorks


Export Format: 


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.