文献

J-GLOBAL ID：202002259882557207   整理番号：20A1800072

順序k-メディアンに対する定数因子近似【JST・京大機械翻訳】

Constant-factor approximation for ordered k-median

著者 (3件)： Byrka Jaroslaw (University of Wroclaw, Poland) ,  Sornat Krzysztof (University of Wroclaw, Poland) ,  Spoerhase Joachim (University of Wroclaw, Poland)
資料名： ACM Proceedings  (ACM Proceedings)
号： STOC 2018  ページ： 620-631  発行年： 2018年 
JST資料番号： D0698C  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： クライアント接続コストを最初にソーティングし,次に,あらかじめ定義された非増加重みベクトル(より高い接続コストをより大きな重みで取り入れる)でそれらを乗算することにより,解が評価される順序k-Midian問題を研究した。1990年代以来,この問題は離散最適化と運用研究コミュニティにおいて広く研究され,k-Midianとk-Centerのような多くの基本的クラスタリングと位置問題を統一するフレームワークとして浮上している。非自明な近似アルゴリズムを得ることは,木のような単純なトポロジーに対しても未解決の問題である。最近,AouadとSegev(2017)は,精巧な局所探索手法を用いて,規則化k-MidianのためのO(log n)近似アルゴリズムを得ることができた。しかし,一定因子近似アルゴリズムの存在は,矩形重みベクトルに対してさえ開放された。本論文では,規則化k-平均問題に対するLPラウンド定数因子近似アルゴリズムを提供した。この結果を,古典的なk-Midian問題に対する興味深い接続を明らかにすることにより達成した。特に,k-Midianに対する自然LP緩和の制約を用いた新しいLP緩和を提案したが,非測定歪コストベクトル上で最小化した。この費用関数(約)は最適解における距離の重み付けをエミュレートし,AouadとSegevのクレバー計数スキームによって推測できる。得られたLPは非有界積分ギャップを持つが,元の,計量空間で動作するk-Medianに対するCharikarとLi(2012)によるLP丸めプロセスは,LP値だけでなく,推測相から導かれたコンビナトリアル結合にも関係するとき,一定因子近似を与える。順序付けk-Midianの非線形性,ランキングベース目的の下での丸めプロセスを解析するために,著者らは,順序付け,加重コスト関数に関連したいくつかの他の設定に興味を持つと信じるいくつかの新しいアイデアと技術的成分を採用した。Please refer to this article’s citation page on the publisher website for specific rights information. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 位相幾何学 ,  ベクトル ,  コミュニティ ,  *近似法 ,  クラスタ化 ,  費用関数 ,  エミュレーション ,  ソーティング ,  緩和現象 ,  非線形性 ,  近傍探索法
準シソーラス用語： 最適解 ,  近似アルゴリズム ,  順序づけ ,  有界 , 【Automatic Indexing@JST】

著者キーワード (4件)： 近似アルゴリズム ,  クラスタリング ,  k中心 ,  kメディアン

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

タイトルに関連する用語 (5件)： 順序 ,  メディアン ,  定数 ,  因子 ,  近似