WEKO3
アイテム
{"_buckets": {"deposit": "5934339d-7c09-4406-b0ec-18f65529bd1f"}, "_deposit": {"created_by": 188, "id": "27217", "owners": [188], "pid": {"revision_id": 0, "type": "depid", "value": "27217"}, "status": "published"}, "_oai": {"id": "oai:tsukuba.repo.nii.ac.jp:00027217", "sets": []}, "author_link": ["93787", "93788", "93789"], "item_11_biblio_info_6": {"attribute_name": "書誌情報", "attribute_value_mlt": [{"bibliographicIssueDates": {"bibliographicIssueDate": "2012-05", "bibliographicIssueDateType": "Issued"}}]}, "item_11_description_4": {"attribute_name": "抄録", "attribute_value_mlt": [{"subitem_description": "The clique partitioning problem is an NP-hard combinatorial optimization\nproblem with applications to data analysis such as clustering. Though a binary integer\nlinear programming formulation has been known for years, one needs to deal with a\nhuge number of variables and constraints when solving a large instance. In this paper,\nwe propose a size reduction algorithm which is based on the Lagrangian relaxation and\nthe pegging test, and verify its validity through numerical experiments. We modify\nthe conventional subgradient method in order to manage the high dimensionality of the\nLagrangian multipliers, and also make an improvement on the ordinary pegging test by\ntaking advantage of the structural property of the clique partitioning problem.", "subitem_description_language": "en", "subitem_description_type": "Abstract"}]}, "item_11_publisher_27": {"attribute_name": "出版者", "attribute_value_mlt": [{"subitem_publisher": "University of Tsukuba. Graduate School of Systems and Information Engineering. Doctoral Program in Social Systems \u0026 Management", "subitem_publisher_language": "en"}]}, "item_11_relation_36": {"attribute_name": "シリーズ", "attribute_value_mlt": [{"subitem_relation_name": [{"subitem_relation_name_language": "en", "subitem_relation_name_text": "Department of Social Systems and Management Discussion Paper Series;no.1291"}]}]}, "item_access_right": {"attribute_name": "アクセス権", "attribute_value_mlt": [{"subitem_access_right": "open access", "subitem_access_right_uri": "http://purl.org/coar/access_right/c_abf2"}]}, "item_creator": {"attribute_name": "著者", "attribute_type": "creator", "attribute_value_mlt": [{"creatorNames": [{"creatorName": "SUKEGAWA, Noriyoshi", "creatorNameLang": "en"}], "nameIdentifiers": [{"nameIdentifier": "93787", "nameIdentifierScheme": "WEKO"}]}, {"creatorNames": [{"creatorName": "YAMAMOTO, Yoshitsugu", "creatorNameLang": "en"}, {"creatorName": "山本, 芳嗣", "creatorNameLang": "ja"}], "nameIdentifiers": [{"nameIdentifier": "93788", "nameIdentifierScheme": "WEKO"}]}, {"creatorNames": [{"creatorName": "ZHANG, Liyuan", "creatorNameLang": "en"}], "nameIdentifiers": [{"nameIdentifier": "93789", "nameIdentifierScheme": "WEKO"}]}]}, "item_files": {"attribute_name": "ファイル情報", "attribute_type": "file", "attribute_value_mlt": [{"accessrole": "open_date", "date": [{"dateType": "Available", "dateValue": "2013-12-25"}], "displaytype": "detail", "download_preview_message": "", "file_order": 0, "filename": "1291.pdf", "filesize": [{"value": "401.6 kB"}], "format": "application/pdf", "future_date_message": "", "is_thumbnail": false, "mimetype": "application/pdf", "size": 401600.0, "url": {"objectType": "fulltext", "url": "https://tsukuba.repo.nii.ac.jp/record/27217/files/1291.pdf"}, "version_id": "99bfb19b-f0cf-4005-8557-58cb46b9bf0d"}]}, "item_language": {"attribute_name": "言語", "attribute_value_mlt": [{"subitem_language": "eng"}]}, "item_resource_type": {"attribute_name": "資源タイプ", "attribute_value_mlt": [{"resourcetype": "technical report", "resourceuri": "http://purl.org/coar/resource_type/c_18gh"}]}, "item_title": "Lagrangian Relaxation and Pegging Test\\nfor the Clique Partitioning Problem", "item_titles": {"attribute_name": "タイトル", "attribute_value_mlt": [{"subitem_title": "Lagrangian Relaxation and Pegging Test\\nfor the Clique Partitioning Problem", "subitem_title_language": "en"}]}, "item_type_id": "11", "owner": "188", "path": ["2662"], "permalink_uri": "http://hdl.handle.net/2241/117038", "pubdate": {"attribute_name": "PubDate", "attribute_value": "2012-05-22"}, "publish_date": "2012-05-22", "publish_status": "0", "recid": "27217", "relation": {}, "relation_version_is_last": true, "title": ["Lagrangian Relaxation and Pegging Test\\nfor the Clique Partitioning Problem"], "weko_shared_id": -1}
Lagrangian Relaxation and Pegging Test\nfor the Clique Partitioning Problem
http://hdl.handle.net/2241/117038
http://hdl.handle.net/2241/1170386c0251e2-a766-4612-b617-3095bf923834
名前 / ファイル | ライセンス | アクション |
---|---|---|
1291.pdf (401.6 kB)
|
|
Item type | Technical Report(1) | |||||
---|---|---|---|---|---|---|
公開日 | 2012-05-22 | |||||
タイトル | ||||||
言語 | en | |||||
タイトル | Lagrangian Relaxation and Pegging Test\nfor the Clique Partitioning Problem | |||||
言語 | ||||||
言語 | eng | |||||
資源タイプ | ||||||
資源 | http://purl.org/coar/resource_type/c_18gh | |||||
タイプ | technical report | |||||
アクセス権 | ||||||
アクセス権 | open access | |||||
アクセス権URI | http://purl.org/coar/access_right/c_abf2 | |||||
著者 |
SUKEGAWA, Noriyoshi
× SUKEGAWA, Noriyoshi× 山本, 芳嗣× ZHANG, Liyuan |
|||||
抄録 | ||||||
内容記述タイプ | Abstract | |||||
内容記述 | The clique partitioning problem is an NP-hard combinatorial optimization problem with applications to data analysis such as clustering. Though a binary integer linear programming formulation has been known for years, one needs to deal with a huge number of variables and constraints when solving a large instance. In this paper, we propose a size reduction algorithm which is based on the Lagrangian relaxation and the pegging test, and verify its validity through numerical experiments. We modify the conventional subgradient method in order to manage the high dimensionality of the Lagrangian multipliers, and also make an improvement on the ordinary pegging test by taking advantage of the structural property of the clique partitioning problem. |
|||||
言語 | en | |||||
書誌情報 |
発行日 2012-05 |
|||||
出版者 | ||||||
言語 | en | |||||
出版者 | University of Tsukuba. Graduate School of Systems and Information Engineering. Doctoral Program in Social Systems & Management | |||||
シリーズ | ||||||
言語 | en | |||||
関連名称 | Department of Social Systems and Management Discussion Paper Series;no.1291 |