文章基本信息

标题：Linearly Representable Submodular Functions: An Algebraic Algorithm for Minimization
本地全文：下载
作者：Rohit Gurjar ; Rajat Rathi
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：168
页码：61:1-61:15
DOI：10.4230/LIPIcs.ICALP.2020.61
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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 â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 â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.
关键词：Submodular Minimization; Parallel Algorithms; Derandomization; Algebraic Algorithms