A faster strongly polynomial time algorithm for submodular function minimization

By James B. Orlin. Mathematical programming, 2007

327 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/d066dcccf868a5e74c0635d41803c9a013290e3c

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Pushmeet Kohli
2. Philip H. S. Torr
3. Lubor Ladicky
4. Raquel Urtasun
5. Anurag Arnab
6. Bernt Schiele
7. Sanja Fidler
8. Silvio Savarese

In Computational Theory and Mathematics

1. Philip H. S. Torr
2. Pushmeet Kohli
3. Lubor Ladicky

Citations in the corpus

• Robust Higher Order Potentials for Enforcing Label Consistency (2008, background): “It is known that a move function can be minimized in polynomial time if it is submodular (Orlin 2007) (see Appendix A).”
• Proposal Scaling Distributed Machine Learning with System and Algorithm Co-design (2016, unknown): “Standard submodular minimization problems have runtime in the order of O(n(6)) [107], which is impractical for large n.”
• Reflection methods for user-friendly submodular optimization (2013, unknown): “maximum flow methods; the currently theoretically fastest c ombinatorial algorithm for SFM scales asO(n(6) + n(5)τ), whereτ is the time to evaluate the function oracle [40] (for an overv i w of other algorithms, see e.”