文献

J-GLOBAL ID：202002214872205804   整理番号：20A0853460

低ランク二値行列近似問題のための近似スキーム【JST・京大機械翻訳】

Approximation Schemes for Low-rank Binary Matrix Approximation Problems

著者 (5件)： Fomin Fedor V. (Department of Informatics, University of Bergen, Bergen, Norway) ,  Golovach Petr A. (Department of Informatics, University of Bergen, Bergen, Norway) ,  Lokshtanov Daniel (University of California Santa Barbara, USA) ,  Panolan Fahad (Department of Computer Science and Engineering, IIT Hyderabad, Kandi, Sangareddy, India) ,  Saurabh Saket (The Institute of Mathematical Sciences, HBNI, Tharamani, Chennai, Tamil Nadu, India)
資料名： ACM Transactions on Algorithms  (ACM Transactions on Algorithms)
巻： 16  号： 1  ページ： 1-39  発行年： 2019年 
JST資料番号： W5685A  ISSN： 1549-6325  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 付加的制約を受ける二値ベクトルのクラスタリングに関する一般的問題に対するランダム化線形時間近似スキームを与えた。新しい制約クラスタリング問題は多くの問題を一般化し,それを解くことにより,二値ベクトルのクラスタリングと二値行列の低ランク近似に関する多くの良く研究された基本問題に対する最初の線形時間近似スキームを得た。著者らのアプローチによって解決可能な問題の中で,低GF(2)ランク近似,低Boolean-Rank近似,および様々なバージョンの二値クラスタリングがある。例えば,m×n二値行列Aと整数r>0に対する低GF(2)ランク近似問題に対して,行列A-Bのl_0ノルムが最小である場合,f(r,ε)nノルムは最小である。ここで,fは最小(1+ε)近似解を最小(1-1e)で出力する。これはこれらの問題に対する最初の線形時間近似スキームである。また,時間n~f(r)1ε~2log1εにおいて実行するこれらの問題に対する(決定論的)PTASを与えた。ここでfは問題に依存していくつかの関数である。制約されたクラスタリング問題のための著者らのアルゴリズムは,それ自身に関して興味深い新しいサンプリング補助定理に基づいている。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件)： 二値行列因子分解 ,  近似スキーム ,  クラスタリング ,  ランダムサンプリング

分類 (1件)： 数値計算  (JE02000J)

タイトルに関連する用語 (5件)： 二値 ,  行列 ,  近似 ,  問題 ,  スキーム