Posimodular Function Optimization
Posimodular Function Optimization
复制标题
正调函数优化
DOI：
10.1007/s00453-021-00910-y
复制
发表时间：
2022
期刊：
影响因子：
1.1
通讯作者：
Kenjiro Takazawa
中科院分区：
文献类型：
--
作者：
Magnus M. Halldorsson;Toshimasa Ishii;Kazuhisa Makino;Kenjiro Takazawa
A functionon a finite setVisposimodularif, for all. Posimodular functions often arise in combinatorial optimization such as undirected cut functions. We consider the problem of finding a nonempty subsetXminimizingf(X), when the posimodular functionfis given by oracle access. We show that posimodular function minimization requires exponential time, contrasting with the polynomial solvability of submodular function minimization that forms another generalization of cut functions. On the other hand, the problem is fixed-parameter tractable in terms of the sizeDof the image (or range) off. In more detail, we show thattime is necessary andsufficient, wheredenotes the time for one function evaluation and. When the image offisfor integerd,time is sufficient. We can also generate all sets minimizingfin time. Finally, we also consider the problem of maximizing a given posimodular function, showing that it requires at leasttime in general, while it has time complexity \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varTheta ({n \atopwithdelims ()d-1}T_f)$$\end{document} whenis the image off, for integer.
A functionon a finite setVisposimodularif, for all. Posimodular functions often arise in combinatorial optimization such as undirected cut functions. We consider the problem of finding a nonempty subsetXminimizingf(X), when the posimodular functionfis given by oracle access. We show that posimodular function minimization requires exponential time, contrasting with the polynomial solvability of submodular function minimization that forms another generalization of cut functions. On the other hand, the problem is fixed-parameter tractable in terms of the sizeDof the image (or range) off. In more detail, we show thattime is necessary andsufficient, wheredenotes the time for one function evaluation and. When the image offisfor integerd,time is sufficient. We can also generate all sets minimizingfin time. Finally, we also consider the problem of maximizing a given posimodular function, showing that it requires at leasttime in general, while it has time complexity \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varTheta ({n \atopwithdelims ()d-1}T_f)$$\end{document} whenis the image off, for integer.
登录
查看更多内容
关于无向流网络上称为单覆盖的覆盖问题的推广（第九届轻井泽电路与系统研讨会论文选特部分）
DOI：
10.1016/s0020-0190(01)00183-1
发表时间：
1997
期刊：
IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
影响因子：
--
作者：
H. Tamura;H. Sugawara;M. Sengoku;S. Shinoda
通讯作者：
S. Shinoda
影响因子：
1
作者：
Lokshtanov, Daniel;Marx, Daniel
通讯作者：
Marx, Daniel
最小-最大多路切割
影响因子：
1
作者：
Zoya Svitkina;É. Tardos
通讯作者：
É. Tardos
影响因子：
--
作者：
H. Nagamochi
通讯作者：
H. Nagamochi
影响因子：
1.1
作者：
H. Nagamochi;T. Ibaraki
通讯作者：
T. Ibaraki