Tata Institute of Fundamental Research
An algebraic algorithm for minimizing linearly representable submodular functions
STCS Seminar
Speaker:
Rohit Gurjar (Indian Institute of Technology Bombay
Mumbai)
Organiser:
Arkadev Chattopadhyay
Date:
Tuesday, 15 Sep 2020, 14:45 to 15:45
Venue:
https://zoom.us/j/93694032340?pwd=WFh1dFFlZzhPUVlQelU5c3A2UUdTQT09
(Scan to add to calendar)
Abstract:
A set function f on the subsets of a set E is called submodular if it satisfies a natural diminishing returns property: for any two subsets S \subseteq T \subseteq E and an element x outside T, we have f(T + x) - f(T) \leq f(S+x) - f(S).
Submodular minimization problem asks for finding the minimum value a given submodular function takes. There are many combinatorial optimization problems that reduce to submodular minimization, for example, bipartite matching, max flow min cut, arborescences, disjoint spanning trees etc. All these problems admit algebraic algorithms, i.e., algorithms involving matrix rank computations. One can ask what is the most general class of submodular functions whose minimization admits an algebraic algorithm. Towards this, we define the class of 'linearly representable submodular functions (LRSF)', which is based on the rank functions of families of subspaces and captures all the above combinatorial examples. We give an algebraic algorithm for minimizing LRSF.
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 poly-logarithmic random bits. We also identify combinatorial problems which are captured by LRSF minimization, but any explicit algebraic algorithms were not given before.
Joint work with Rajat Rathi.
| Speaker: | Rohit Gurjar (Indian Institute of Technology Bombay Mumbai) |
| Organiser: | Arkadev Chattopadhyay |
| Date: | Tuesday, 15 Sep 2020, 14:45 to 15:45 |
| Venue: | https://zoom.us/j/93694032340?pwd=WFh1dFFlZzhPUVlQelU5c3A2UUdTQT09 |
(Scan to add to calendar)
Abstract:
A set function f on the subsets of a set E is called submodular if it satisfies a natural diminishing returns property: for any two subsets S \subseteq T \subseteq E and an element x outside T, we have f(T + x) - f(T) \leq f(S+x) - f(S).
Submodular minimization problem asks for finding the minimum value a given submodular function takes. There are many combinatorial optimization problems that reduce to submodular minimization, for example, bipartite matching, max flow min cut, arborescences, disjoint spanning trees etc. All these problems admit algebraic algorithms, i.e., algorithms involving matrix rank computations. One can ask what is the most general class of submodular functions whose minimization admits an algebraic algorithm. Towards this, we define the class of 'linearly representable submodular functions (LRSF)', which is based on the rank functions of families of subspaces and captures all the above combinatorial examples. We give an algebraic algorithm for minimizing LRSF.
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 poly-logarithmic random bits. We also identify combinatorial problems which are captured by LRSF minimization, but any explicit algebraic algorithms were not given before.
Joint work with Rajat Rathi.
Submodular minimization problem asks for finding the minimum value a given submodular function takes. There are many combinatorial optimization problems that reduce to submodular minimization, for example, bipartite matching, max flow min cut, arborescences, disjoint spanning trees etc. All these problems admit algebraic algorithms, i.e., algorithms involving matrix rank computations. One can ask what is the most general class of submodular functions whose minimization admits an algebraic algorithm. Towards this, we define the class of 'linearly representable submodular functions (LRSF)', which is based on the rank functions of families of subspaces and captures all the above combinatorial examples. We give an algebraic algorithm for minimizing LRSF.
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 poly-logarithmic random bits. We also identify combinatorial problems which are captured by LRSF minimization, but any explicit algebraic algorithms were not given before.
Joint work with Rajat Rathi.