WEKO3
アイテム
頂点彩色問題に対する列生成法アプローチの高速化
https://ipsj.ixsq.nii.ac.jp/records/31625
https://ipsj.ixsq.nii.ac.jp/records/3162593b37d5f-4084-414c-95af-6a13fa899d20
名前 / ファイル | ライセンス | アクション |
---|---|---|
![]() |
Copyright (c) 2008 by the Information Processing Society of Japan
|
|
オープンアクセス |
Item type | SIG Technical Reports(1) | |||||||
---|---|---|---|---|---|---|---|---|
公開日 | 2008-03-07 | |||||||
タイトル | ||||||||
タイトル | 頂点彩色問題に対する列生成法アプローチの高速化 | |||||||
タイトル | ||||||||
言語 | en | |||||||
タイトル | Speeding Up a Column Generation Approach for Vertex Coloring Problem | |||||||
言語 | ||||||||
言語 | jpn | |||||||
資源タイプ | ||||||||
資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||
資源タイプ | technical report | |||||||
著者所属 | ||||||||
値 | 明治大学理工学部情報科学科 | |||||||
著者所属 | ||||||||
値 | 明治大学大学院理工学研究科 | |||||||
著者所属(英) | ||||||||
言語 | en | |||||||
値 | Department of Computer Science, Meiji University | |||||||
著者所属(英) | ||||||||
言語 | en | |||||||
値 | Graduate School of Science and Technology, Meiji University | |||||||
著者名 |
玉木, 久夫
× 玉木, 久夫
|
|||||||
著者名(英) |
Hisao, Tamaki
× Hisao, Tamaki
|
|||||||
論文抄録 | ||||||||
内容記述タイプ | Other | |||||||
内容記述 | Mehrotra と Trick はグラフの頂点彩色問題を極大独立点集合による被覆問題として定式化し、その線形緩和問題を厳密に解く列生成法を提案した。しかし全体の目的からは線形緩和問題を厳密に解く必要はなく、最適値を切り上げた整数値が求まれば十分であり、列生成の打ち切り条件を緩和することができる。そのような打ち切り条件の緩和を行うことで、多くの場合に染色数の下界計算が高速化されることを実験により確認した。また、この考え方をさらに進めて、初期列の質が悪く列生成法に時間がかかる時に対処するアプローチを提案し実験した。 | |||||||
論文抄録(英) | ||||||||
内容記述タイプ | Other | |||||||
内容記述 | Mehrotra and Trick formulated the vertex coloring problem as that of covering vertices bymaximal independent sets, and proposed a column generation approach that solves the linear relaxationof the problem exactly. For our purposes, however, we only need an integral lower bound, which we canexploit to stop generating columns before we reach the LP optimal. Experiment show that the lowerbound calculations are often dramatically sped-up with these early stopping conditions. We also extendthis idea to reduce processing time when the initial set of columns is of bad quality. | |||||||
書誌レコードID | ||||||||
収録物識別子タイプ | NCID | |||||||
収録物識別子 | AN1009593X | |||||||
書誌情報 |
情報処理学会研究報告アルゴリズム(AL) 巻 2008, 号 24(2008-AL-117), p. 59-66, 発行日 2008-03-07 |
|||||||
Notice | ||||||||
値 | SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | |||||||
出版者 | ||||||||
言語 | ja | |||||||
出版者 | 情報処理学会 |