文献

J-GLOBAL ID：202002227589957632   整理番号：20A2273937

交差制約を持つ最適マトロイド基底:評価マトロイド,M凸関数,およびその応用【JST・京大機械翻訳】

Optimal Matroid Bases with Intersection Constraints: Valuated Matroids, M-convex Functions, and Their Applications

著者 (2件)： Iwamasa Yuni (National Institute of Informatics, Tokyo, Japan) ,  Takazawa Kenjiro (Hosei University, Tokyo, Japan)
資料名： Lecture Notes in Computer Science  (Lecture Notes in Computer Science)
巻： 12337  ページ： 156-167  発行年： 2020年 
JST資料番号： H0078D  ISSN： 0302-9743  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： 同じ地上セットVと2つのコスト関数[数式:原文を参照]と[数式:原文を参照]の2つのマトロイド[数式:原文を参照]と[数式:原文を参照]に関して,著者らは,それらの交差[数式:原文を参照]に関して,特定の基本的制約を受ける[数式:原文を参照]の[数式:原文を参照]と[数式:原文を参照]の塩基[数式:原文を参照]を見つける問題を考察した。Lendl,Peis,およびTimmermans(2019)は,モジュールコスト関数を議論した:それらは,基数制約が[数式:原文を参照]または[数式:原文を参照]である場合に対して,加重マトロイド交差点への問題を減らした。そして,[数式:原文を参照]があるケースのために新しいプライマー二重アルゴリズムを設計した。本論文の目的は,非線形凸費用関数を持つ問題を一般化し,離散凸解析の観点からそれらを理解することである。著者らは,各一般化問題を,交差制約を有する加重マトロイド交差の包括的な理解を提供するために,評価独立割当て,評価マトロイド交差,または[数式:原文を参照]凸サブモジュールフローを介して解くことができることを証明した。また,これらの問題のいくつかの変異体のNP硬度を示し,これらの問題に対する離散凸解析のカバレッジを明らかにした。最後に,マトロイド輻輳ゲームにおける一般化問題の適用と,相互作用コストによる組合せ最適化問題を示した。Copyright Springer Nature Switzerland AG 2020 Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： アルゴリズム ,  相互作用 ,  交差点 ,  基底 ,  *凸関数 ,  費用関数 ,  *マトロイド ,  凸形 ,  硬度 ,  組合せ最適化問題 ,  基数
準シソーラス用語： 凸解析 , 【Automatic Indexing@JST】

著者キーワード (5件)： 有価な独立割当 ,  評価されたマトロイド交差 ,  M凸劣モジュラ流 ,  マトロイド混雑ゲーム ,  相互作用コストを伴う組合せ最適化問題

分類 (2件)： グラフ理論基礎  (IA02020S) ,  計算理論  (JB02000A)

タイトルに関連する用語 (7件)： 交差 ,  制約 ,  マトロイド ,  基底 ,  評価 ,  凸関数 ,  応用