文献

J-GLOBAL ID：202002263591338276   整理番号：20A1713066

低直径クラスタに対する節約型定式化【JST・京大機械翻訳】

Parsimonious formulations for low-diameter clusters

著者 (2件)： Salemi Hosseinali (School of Industrial Engineering and Management, Oklahoma State University, Stillwater, USA) ,  Buchanan Austin (School of Industrial Engineering and Management, Oklahoma State University, Stillwater, USA)
資料名： Mathematical Programming Computation  (Mathematical Programming Computation)
巻： 12  号： 3  ページ： 493-528  発行年： 2020年 
JST資料番号： W4714A  ISSN： 1867-2949  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： ネットワークの解析において,1つは,堅くknitクラスタをしばしば探索する。「良い」クラスタの1つの特性は,小さな直径(say,kによって有界)であり,k-clubの概念に導いた。本論文では,これらの低直径部分グラフを検出するための新しい経路様およびカット様整数プログラミング定式化を提案した。それらは,いくつかの既存の定式化を単純化し,一般化し,そして/または支配する。最良の定式化は,ノード変数(以前の定式化とは異なり)のみを使用し,指数的に大きなクラスのカット状不等式を介して,直径-最大-k制約を課す。カット様定式化の比較的簡単な実装は,以前のアプローチを容易に凌駕し,他の定式化によって時間を取る2つまたは2つで,最大k-clb問題の実例の1つを解いた。さらに,切断のような定式化は,距離がホップに関して測定されない場合でも適用されるという意味においてより一般的である。本論文では,k-clb問題のみを考察したが,提案技法は,コンパクトな解が鍵(例えば,政治的地域と野生生物保護設計)である他のアプリケーションにも有用である。Copyright Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society 2020 Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 不等式 ,  簡素化 ,  整数計画法 ,  ネットワーク ,  部分グラフ ,  *クラスタ ,  応用プログラム ,  野生生物 ,  *定式化
準シソーラス用語： 有界 , 【Automatic Indexing@JST】

著者キーワード (8件)： k-クラブ ,  低直径 ,  クラスタ ,  整数計画法 ,  ホップ制約 ,  距離制約 ,  有界直径 ,  長さ限界カット

分類 (3件)： グラフ理論基礎  (IA02020S) ,  システム・制御理論一般  (IA02010H) ,  人工知能  (JE08000Z)

タイトルに関連する用語 (4件)： 直径 ,  クラスタ ,  節約 ,  定式化