Linearly Representable Submodular Functions: An Algebraic Algorithm for Minimization
Linearly Representable Submodular Functions: An Algebraic Algorithm for Minimization
复制标题
线性可表示子模函数：一种最小化代数算法
DOI：
10.4230/lipics.icalp.2020.61
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Rajat Rathi
中科院分区：
文献类型：
--
作者：
R. Gurjar;Rajat Rathi
A set function f : 2^E → ℝ on the subsets of a set E is called submodular if it satisfies a natural diminishing returns property: for any S ⊆ E and x,y ∉ S, we have f(S ∪ {x,y}) - f(S ∪ {y}) ≤ f(S ∪ {x}) - f(S). Submodular minimization problem asks for finding the minimum value a given submodular function takes. We give an algebraic algorithm for this problem for a special class of submodular functions that are "linearly representable". It is known that every submodular function f can be decomposed into a sum of two monotone submodular functions, i.e., there exist two non-decreasing submodular functions f₁,f₂ such that f(S) = f₁(S) + f₂(E ⧵ S) for each S ⊆ E. Our class consists of those submodular functions f, for which each of f₁ and f₂ is a sum of k rank functions on families of subspaces of ?ⁿ, for some field ?.
Our algebraic algorithm for this class of functions can be parallelized, and thus, puts the problem of finding the minimizing set in the complexity class randomized NC. Further, we derandomize our algorithm so that it needs only O(log²(kn|E|)) many random bits.
We also give reductions from two combinatorial optimization problems to linearly representable submodular minimization, and thus, get such parallel algorithms for these problems. These problems are (i) covering a directed graph by k a-arborescences and (ii) packing k branchings with given root sets in a directed graph.
A set function f : 2^E → ℝ on the subsets of a set E is called submodular if it satisfies a natural diminishing returns property: for any S ⊆ E and x,y ∉ S, we have f(S ∪ {x,y}) - f(S ∪ {y}) ≤ f(S ∪ {x}) - f(S). Submodular minimization problem asks for finding the minimum value a given submodular function takes. We give an algebraic algorithm for this problem for a special class of submodular functions that are "linearly representable". It is known that every submodular function f can be decomposed into a sum of two monotone submodular functions, i.e., there exist two non-decreasing submodular functions f₁,f₂ such that f(S) = f₁(S) + f₂(E ⧵ S) for each S ⊆ E. Our class consists of those submodular functions f, for which each of f₁ and f₂ is a sum of k rank functions on families of subspaces of ?ⁿ, for some field ?.
Our algebraic algorithm for this class of functions can be parallelized, and thus, puts the problem of finding the minimizing set in the complexity class randomized NC. Further, we derandomize our algorithm so that it needs only O(log²(kn|E|)) many random bits.
We also give reductions from two combinatorial optimization problems to linearly representable submodular minimization, and thus, get such parallel algorithms for these problems. These problems are (i) covering a directed graph by k a-arborescences and (ii) packing k branchings with given root sets in a directed graph.
准NC中的二分完美匹配
DOI：
10.1145/2897518.2897564
发表时间：
2016
期刊：
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing
影响因子：
--
作者：
Stephen A. Fenner;Rohit Gurjar;Thomas Thierauf
通讯作者：
Thomas Thierauf
DOI：
10.1145/3313276.3316361
发表时间：
2019-04
期刊：
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
Sepehr Assadi;Yu Chen;S. Khanna
通讯作者：
Sepehr Assadi;Yu Chen;S. Khanna
线性拟阵交集处于准数控状态
影响因子：
1.4
作者：
Rohit Gurjar;Thomas Thierauf
通讯作者：
Thomas Thierauf