Approximation Algorithms for Submodular Optimization

子模优化的近似算法

• 批准号: 23300002
• 负责人: Iwata Satoru
• 金额: $ 8.07万
• 依托单位: The University of Tokyo (2012-2015)Kyoto University (2011)
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (B)
• 财政年份: 2011
• 资助国家: 日本
• 起止时间: 2011-04-01 至 2016-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-23300002/
• 关键词: 離散最適化; 劣モジュラ関数; 近似アルゴリズム; NP困難; ネットワーク; 離散凸性; 巡回セールスマン問題; 組合せ剛性理論

项目成果

Approximating max-min weighted T-joins

近似最大-最小加权 T 形连接

• DOI: 10.1016/j.orl.2013.03.004
• 发表时间: 2013
• 期刊: Operations Research Letters
• 影响因子: 1.1
• 作者: T.IIDA;F.SATO;T.YAMAMOTO;S. Iwata and R. Ravi
• 通讯作者: S. Iwata and R. Ravi

Optimal matching forests and valuated delta-matroids,

最佳匹配森林和评估的δ拟阵，

• DOI: 10.1137/110827661
• 发表时间: 2014
• 期刊: SIAM Journal on Discrete Mathematics
• 影响因子: 0.8
• 作者: Yoshida LM;Suzuki M;Thiem VD;Smith WP;Tsuzuki A;Huong VT;Takahashi K;Miyakawa M;Anh NT;Watanabe K;Ai NT;Tho le H;Kilgore P;Yoshino H;Toizumi M;Yasunami M;Moriuchi H;Anh DD;Ariyoshi K;Kenjiro Takazawa
• 通讯作者: Kenjiro Takazawa

Improved Approximation Algorithms for k-Submodular Function Maximization

k-子模函数最大化的改进近似算法

• DOI: 10.1137/1.9781611974331.ch30
• 发表时间: 2016
• 期刊: Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)
• 作者: Satoru Iwata;Shin-ichi Tanigawa;and Yuichi Yoshida
• 通讯作者: and Yuichi Yoshida

Shortest bibranchings and valuated matroid intersection

最短分枝和评估拟阵交集

• DOI: 10.1007/s13160-012-0072-2
• 发表时间: 2012
• 期刊: Japan Journal of Industrial and Applied Mathematics
• 影响因子: 0.9
• 作者: Y. Cui;J. Jansson;and W.-K. Sung.;J. Jansson and A. Lingas.;須田亮平，中野眞一，山中克久;K. Takazawa
• 通讯作者: K. Takazawa

Orientations and detachments of graphs with prescribed degrees and connectivity

具有规定度数和连通性的图的方向和分离

• DOI: 10.1016/j.disopt.2014.02.003
• 发表时间: 2014
• 期刊: Discrete Optimization
• 影响因子: 1.1
• 作者: Matsuo Konagaya;Tetsuo Asano;Satoru Iwata and Tibor Jordan
• 通讯作者: Satoru Iwata and Tibor Jordan