ダウンロード数: 44
このアイテムのファイル:
ファイル | 記述 | サイズ | フォーマット | |
---|---|---|---|---|
s10107-021-01661-y.pdf | 617.33 kB | Adobe PDF | 見る/開く |
完全メタデータレコード
DCフィールド | 値 | 言語 |
---|---|---|
dc.contributor.author | Kobayashi, Yusuke | en |
dc.contributor.alternative | 小林, 佑輔 | ja |
dc.date.accessioned | 2022-03-10T05:37:33Z | - |
dc.date.available | 2022-03-10T05:37:33Z | - |
dc.date.issued | 2022-03 | - |
dc.identifier.uri | http://hdl.handle.net/2433/268759 | - |
dc.description | A preliminary version of this paper appears in [Kobayashi, Y.: Weighted triangle-free 2-matching problem with edge-disjoint forbidden triangles. In: Integer Programming and Combinatorial Optimization, pp. 280–293. Springer, New York (2020).]. | en |
dc.description.abstract | The weighted T-free 2-matching problem is the following problem: given an undirected graph G, a weight function on its edge set, and a set T of triangles in G, find a maximum weight 2-matching containing no triangle in T. When T is the set of all triangles in G, this problem is known as the weighted triangle-free 2-matching problem, which is a long-standing open problem. A main contribution of this paper is to give the first polynomial-time algorithm for the weighted T-free 2-matching problem under the assumption that T is a set of edge-disjoint triangles. In our algorithm, a key ingredient is to give an extended formulation representing the solution set, that is, we introduce new variables and represent the convex hull of the feasible solutions as a projection of another polytope in a higher dimensional space. Although our extended formulation has exponentially many inequalities, we show that the separation problem can be solved in polynomial time, which leads to a polynomial-time algorithm for the weighted T-free 2-matching problem. | en |
dc.language.iso | eng | - |
dc.publisher | Springer Nature | en |
dc.rights | This version of the article has been accepted for publication, after peer review (when applicable) and is subject to Springer Nature’s AM terms of use, but is not the Version of Record and does not reflect post-acceptance improvements, or any corrections. The Version of Record is available online at: http://dx.doi.org/10.1007/s10107-021-01661-y. | en |
dc.rights | The full-text file will be made open to the public on 08 May 2022 in accordance with publisher's 'Terms and Conditions for Self-Archiving'. | en |
dc.rights | This is not the published version. Please cite only the published version. この論文は出版社版でありません。引用の際には出版社版をご確認ご利用ください。 | en |
dc.subject | Restricted 2-matching | en |
dc.subject | Polynomial-time algorithm | en |
dc.subject | Triangle-free | en |
dc.subject | Extended formulation | en |
dc.subject | 90C27 | en |
dc.subject | 90C35 | en |
dc.title | Weighted Triangle-free 2-matching Problem with Edge-disjoint Forbidden Triangles | en |
dc.type | journal article | - |
dc.type.niitype | Journal Article | - |
dc.identifier.jtitle | Mathematical Programming | en |
dc.identifier.volume | 192 | - |
dc.identifier.issue | 1-2 | - |
dc.identifier.spage | 675 | - |
dc.identifier.epage | 702 | - |
dc.relation.doi | 10.1007/s10107-021-01661-y | - |
dc.textversion | author | - |
dc.address | Research Institute for Mathematical Sciences, Kyoto University | en |
dc.relation.url | https://doi.org/10.1007/978-3-030-45771-6_22 | - |
dc.relation.url | http://hdl.handle.net/2433/252767 | - |
dcterms.accessRights | open access | - |
datacite.date.available | 2022-05-08 | - |
datacite.awardNumber | 16K16010 | - |
datacite.awardNumber | 16H03118 | - |
datacite.awardNumber | 18H05291 | - |
datacite.awardNumber | 20K11692 | - |
datacite.awardNumber.uri | https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-16K16010/ | - |
datacite.awardNumber.uri | https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-16H03118/ | - |
datacite.awardNumber.uri | https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-18H05291/ | - |
datacite.awardNumber.uri | https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-20K11692/ | - |
dc.identifier.pissn | 0025-5610 | - |
jpcoar.funderName | 日本学術振興会 | ja |
jpcoar.funderName | 日本学術振興会 | ja |
jpcoar.funderName | 日本学術振興会 | ja |
jpcoar.funderName | 日本学術振興会 | ja |
jpcoar.awardTitle | 頑健なネットワークの設計に向けた組合せ最適化理論の研究 | ja |
jpcoar.awardTitle | ネットワーク上の時間軸をもった最適化問題とその応用 | ja |
jpcoar.awardTitle | 巨大グラフとビッグデータ解析の基礎基盤:理論研究と高速アルゴリズム開発 | ja |
jpcoar.awardTitle | 組合せ最適化における多面体手法の高度化 | ja |
出現コレクション: | 学術雑誌掲載論文等 |
![](/dspace/image/articlelinker.gif)
このリポジトリに保管されているアイテムはすべて著作権により保護されています。