文献

J-GLOBAL ID：201902231009677681   整理番号：19A2622846

無制約XOS関数最大化に対する最適近似アルゴリズム

著者 (3件)： 河瀬康志 (東京工大) ,  小林佑輔 (京大) ,  山口勇太郎 (大阪大)
資料名： 日本応用数理学会年会講演予稿集(CD-ROM)  (JSIAM年会講演予稿集(CD-ROM))
巻： 2019  ページ： 502-503  発行年： 2019年08月21日 
JST資料番号： L6974B  ISSN： 1345-3378  資料種別： 会議録 (C)
記事区分： 短報  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： いくつかの加法的な集合関数の最大値を取る形で表現できる集合関数は,XOS関数と呼ばれ,劣モジュラ関数などを含むことが知られている.本講演では,関数値オラクルで与えられたXOS関数を最大化する問題を考え,最適な近似比を達成する多項式時間アルゴリズムを提案する.(著者抄録)

シソーラス用語： 集合論 ,  *アルゴリズム ,  *最大化問題 ,  関数
準シソーラス用語： XOS関数 ,  近似困難性 ,  *集合関数 ,  *多項式時間アルゴリズム

分類 (1件)： 計算理論  (JB02000A)

タイトルに関連する用語 (4件)： 制約 ,  関数 ,  最大化 ,  近似アルゴリズム