Decomposable Submodular Function Minimization via Maximum Flow
Authors: Kyriakos Axiotis, Adam Karczmarz, Anish Mukherjee, Piotr Sankowski, Adrian Vladu
ICML 2021 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | This paper bridges discrete and continuous optimization approaches for decomposable submodular function minimization, in both the standard and parametric settings. We provide improved running times for this problem by reducing it to a number of calls to a maximum flow oracle. When each function in the decomposition acts on O(1) elements of the ground set V and is polynomically bounded, our running time is up to polylogarithmic factors equal to that of solving maximum flow in a sparse graph with O(|V |) vertices and polynomial integral capacities. We achieve this by providing a simple iterative method which can optimize to high precision any convex function defined on the submodular base polytope, provided we can efficiently minimize it on the base polytope corresponding to the cut function of a certain graph that we construct. |
| Researcher Affiliation | Collaboration | Kyriakos Axiotis 1 MIT Adam Karczmarz 2 University of Warsaw Anish Mukherjee 2 University of Warsaw Piotr Sankowski 3 IDEAS NCBR 4 MIM Solutions 5 CNRS 6 IRIF, Universit e de Paris. Correspondence to: Kyriakos Axiotis <kaxiotis@mit.edu>, Piotr Sankowski <sank@mimuw.edu.pl>, Adrian Vladu <vladu@irif.fr>. |
| Pseudocode | Yes | Algorithm 1 Parametric Decomposable Submodular Function Minimization |
| Open Source Code | No | The paper is theoretical and does not mention releasing any source code or providing links to a code repository for the methodology described. |
| Open Datasets | No | This is a theoretical paper focusing on algorithmic improvements and does not involve empirical evaluation on datasets, hence no training data is mentioned. |
| Dataset Splits | No | This is a theoretical paper and does not involve empirical evaluation or dataset splits for validation. |
| Hardware Specification | No | The paper is theoretical and does not describe any experiments; therefore, no hardware specifications for running experiments are provided. |
| Software Dependencies | No | The paper is theoretical and does not describe any empirical implementations; therefore, no software dependencies with specific version numbers are provided. |
| Experiment Setup | No | The paper is theoretical and does not describe any experiments; therefore, no specific experimental setup details, such as hyperparameters or training configurations, are provided. |