文献

J-GLOBAL ID：202202275904537218   整理番号：22A0797075

多段最適化のための単純な丸め方式【JST・京大機械翻訳】

A simple rounding scheme for multistage optimization

著者 (8件)： Bampis Evripidis (Sorbonne Universite, CNRS, LIP6 UMR 7606, 4 place Jussieu, 75005 Paris, France) ,  Christou Dimitris (University of Texas, Austin, USA) ,  Escoffier Bruno (Sorbonne Universite, CNRS, LIP6 UMR 7606, 4 place Jussieu, 75005 Paris, France) ,  Escoffier Bruno (Institut Universitaire de France, France) ,  Kononov Alexander (Sobolev Institute of Mathematics, Russian Federation) ,  Kononov Alexander (Novosibirsk State University, Russian Federation) ,  Nguyen Kim Thang (Sorbonne Universite, CNRS, LIP6 UMR 7606, 4 place Jussieu, 75005 Paris, France) ,  Nguyen Kim Thang (IBISC, Univ Evry, University Paris-Saclay, France)
資料名： Theoretical Computer Science  (Theoretical Computer Science)
巻： 907  ページ： 1-10  発行年： 2022年 
JST資料番号： T0022A  ISSN： 0304-3975  CODEN： TCSDIQ  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： (Gupta et al.,Eisenstat et al.,ICALP 2014)に導入された多段フレームワークを考察し,ここでは,(静的)コンビナトリアル最適化問題(各時間ステップに対して1つ)の一連のインスタンスと,各時間ステップにおける解の品質と連続時間ステップにおける解の安定性/相似性の間のトレードオフに到達するための一連の解(各時間ステップに対して1つ)を見出した。最初に,隣接解の移動コスト(または安定性収入)を説明する多段問題に対して調整した新しい丸め方式を導入した。この丸め方式を用いて,著者らは,Prized-Collecting Steiner TreeとPrized-Collecting Traveling Salesman問題の多段階バリアントのための改良近似アルゴリズムを提案した。さらに,ツリー上の多段マルチCutに対する2近似アルゴリズムを導入し,また,MaxSatの多段バリアントに対する0.75近似アルゴリズムを提供することにより,一般的スキームを最大化問題に拡張したことを示した。Copyright 2022 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *最適化 ,  最大化問題 ,  類似性 ,  連続時間系
準シソーラス用語： 近似アルゴリズム ,  時間ステップ , 【Automatic Indexing@JST】

著者キーワード (3件)： 多段最適化 ,  近似アルゴリズム ,  LPラウンド

分類 (2件)： システム最適化手法  (IA02050Z) ,  その他のオペレーションズリサーチの手法  (KA03070E)

タイトルに関連する用語 (3件)： 多段 ,  最適化 ,  丸め