ダウンロード数: 387
このアイテムのファイル:
ファイル | 記述 | サイズ | フォーマット | |
---|---|---|---|---|
j.cor.2011.06.005.pdf | 156.63 kB | Adobe PDF | 見る/開く |
完全メタデータレコード
DCフィールド | 値 | 言語 |
---|---|---|
dc.contributor.author | Tanaka, Shunji | en |
dc.contributor.alternative | 田中, 俊二 | ja |
dc.date.accessioned | 2011-08-10T00:41:11Z | - |
dc.date.available | 2011-08-10T00:41:11Z | - |
dc.date.issued | 2012-03 | - |
dc.identifier.issn | 0305-0548 | - |
dc.identifier.uri | http://hdl.handle.net/2433/143685 | - |
dc.description.abstract | The closest string problem that arises in both computational biology and coding theory is to find a string minimizing the maximum Hamming distance from a given set of strings. This study proposes an efficient heuristic algorithm for this NP-hard problem. The key idea is to apply the Lagrangian relaxation technique to the problem formulated as a mixed-integer programming problem. This enables us to decompose the problem into trivial subproblems corresponding to each position of the strings. Furthermore, a feasible solution can be easily obtained from a solution of the relaxation. Based on this, a heuristic algorithm is constructed by combining a Lagrangian multiplier adjustment procedure and a tabu search. Computational experiments will show that the proposed algorithm can find good approximate solutions very fast. | en |
dc.format.mimetype | application/pdf | - |
dc.language.iso | eng | - |
dc.publisher | Elsevier Ltd. | en |
dc.rights | © 2011 Elsevier Ltd. | en |
dc.rights | This is not the published version. Please cite only the published version. | en |
dc.rights | この論文は出版社版でありません。引用の際には出版社版をご確認ご利用ください。 | ja |
dc.subject | Closest string problem | en |
dc.subject | Mixed-integer programming | en |
dc.subject | Lagrangian relaxation | en |
dc.subject | Tabu search | en |
dc.title | A heuristic algorithm based on Lagrangian relaxation for the closest string problem | en |
dc.type | journal article | - |
dc.type.niitype | Journal Article | - |
dc.identifier.ncid | AA11527685 | - |
dc.identifier.jtitle | Computers & Operations Research | en |
dc.identifier.volume | 39 | - |
dc.identifier.issue | 3 | - |
dc.identifier.spage | 709 | - |
dc.identifier.epage | 717 | - |
dc.relation.doi | 10.1016/j.cor.2011.06.005 | - |
dc.textversion | author | - |
dcterms.accessRights | open access | - |
出現コレクション: | 学術雑誌掲載論文等 |
このリポジトリに保管されているアイテムはすべて著作権により保護されています。