Deeparnab Chakrabarty: Provable Submodular Function Minimization via Fujishige Wolfe Algorithm
- Casey Anderson, Microsoft
The Fujishige-Wolfe heuristic is empirically one of the fastest algorithms for Submodular Function Minimization and is based upon Wolfe’s algorithm to find the nearest point on a polytope to the origin. There was no theoretical guarantees known for the same. In this work we give a convergence analysis for Wolfe’s algorithm which implies a pseudo-polynomial running time for the Fujishige Wolfe algorithm.
-
-
Casey Anderson
-
-
Watch Next
-
-
-
From Microfarms to the Moon: A Teen Innovator’s Journey in Robotics
- Pranav Kumar Redlapalli
-
-
Microsoft Research India - The lab culture
- P. Anandan,
- Indrani Medhi Thies,
- B. Ashok
-
GenAI for Supply Chain Management: Present and Future
- Georg Glantschnig,
- Beibin Li,
- Konstantina Mellou
-
Using Optimization and LLMs to Enhance Cloud Supply Chain Operations
- Beibin Li,
- Konstantina Mellou,
- Ishai Menache
-
-
-
