Fetching the paper…
Reading the bibliography…
In this paper we provide improved running times and oracle complexities for approximately minimizing a submodular function.
Theory of capacities
Gustave Choquet · 1954
Earlier work this paper cites.
Submodular functions, matroids, and certain polyhedra
Jack Edmonds · 1970
Earlier work this paper cites.
Finding the nearest point in a polytope
Philip Wolfe · 1976
Earlier work this paper cites.
Lexicographically optimal base of a polymatroid with respect to a weight vector
Satoru Fujishige · 1980
Earlier work this paper cites.
Submodular functions and convexity
L. Lovász · 1983
Earlier work this paper cites.
Problem complexity and method efficiency in optimization
Arkadii Semenovich Nemirovsky and David Borisovich Yudin · 1983
Earlier work this paper cites.
Corrigendum to our paper: “The ellipsoid method and its consequences in combinatorial optimization” [Combinatorica
M. Grötschel, L. Lovász, and A. Schrijver · 1984
Earlier work this paper cites.
On submodular function minimization
William H. Cunningham · 1985
Earlier work this paper cites.
Active set algorithms for isotonic regression; A unifying framework
Michael J. Best and Nilotpal Chakravarti · 1990
Earlier work this paper cites.
Fast approximate energy minimization via graph cuts
Yuri Boykov, Olga Veksler, and Ramin Zabih · 1999
Earlier work this paper cites.
A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
Satoru Iwata, Lisa Fleischer, and Satoru Fujishige · 2000
Earlier work this paper cites.
A combinatorial algorithm minimizing submodular functions in strongly polynomial time
Alexander Schrijver · 2000
Earlier work this paper cites.
Submodular functions and optimization
Satoru Fujishige · 2005
Earlier work this paper cites.
Submodular function minimization
S Thomas McCormick · 2005
Earlier work this paper cites.
Cubic regularization of newton method and its global performance
Yurii Nesterov and Boris T. Polyak · 2006
Cited alongside, same era.
A simple combinatorial algorithm for submodular function minimization
Satoru Iwata and James B. Orlin · 2009
Cited alongside, same era.
Dynamic graph cuts and their applications in computer vision
Pushmeet Kohli and Philip HS Torr · 2010
Cited alongside, same era.
An application of the submodular principal partition to training data subset selection
Hui Lin and Jeff Bilmes · 2010
Cited alongside, same era.
Maximizing non-monotone submodular functions
Uriel Feige, Vahab S Mirrokni, and Jan Vondrak · 2011
Cited alongside, same era.
Online submodular minimization for combinatorial structures
Stefanie Jegelka and Jeff A. Bilmes · 2011
Cited alongside, same era.
Submodular function maximization via the multilinear relaxation and contention resolution schemes
Chandra Chekuri, Jan Vondrák, and Rico Zenklusen · 2014
Later among the works it cites.
Convex optimization: Algorithms and complexity
Sébastien Bubeck · 2015
Later among the works it cites.
On the global linear convergence of frank-wolfe optimization variants
Simon Lacoste-Julien and Martin Jaggi · 2015
Later among the works it cites.
A faster cutting plane method and its implications for combinatorial and convex optimization
Yin Tat Lee, Aaron Sidford, and Sam Chiu-wai Wong · 2015
Later among the works it cites.
Accelerated methods for non-convex optimization
Yair Carmon, John C. Duchi, Oliver Hinder, and Aaron Sidford · 2016
Later among the works it cites.
Matrix completion has no spurious local minimum
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Submodularity and its applications in optimized information gathering
Andreas Krause and Carlos Guestrin · 2011
Cited alongside, same era.
Optimal selection of limited vocabulary speech corpora
Hui Lin and Jeff Bilmes · 2011
Cited alongside, same era.
A class of submodular functions for document summarization
Hui Lin and Jeff A. Bilmes · 2011
Cited alongside, same era.
Online submodular minimization
Elad Hazan and Satyen Kale · 2012
Cited alongside, same era.
How to make the gradients small
Yurii Nesterov · 2012
Cited alongside, same era.
Learning with submodular functions: A convex optimization perspective
Francis R. Bach · 2013
Cited alongside, same era.
Rong Ge, Jason D. Lee, and Tengyu Ma · 2016
Later among the works it cites.
Worst-case evaluation complexity for unconstrained nonlinear optimization using high-order regularized models
Ernesto G. Birgin, J. L. Gardenghi, José Mario Martínez, Sandra Augusta Santos, and Philippe L. Toint · 2017
Later among the works it cites.
Subquadratic submodular function minimization
Deeparnab Chakrabarty, Yin Tat Lee, Aaron Sidford, and Sam Chiu-wai Wong · 2017
Later among the works it cites.
Sergey Guminov and Alexander Gasnikov · 2017
Later among the works it cites.
Yurii Nesterov, Alexander Gasnikov, Sergey Guminov, and Pavel Dvurechensky · 2018
Later among the works it cites.
Submodular functions: from discrete to continuous domains
Francis Bach · 2019
Closest in time.
Quantum and classical algorithms for approximate submodular function minimization
Yassine Hamoudi, Patrick Rebentrost, Ansis Rosmanis, and Miklos Santha · 2019
Closest in time.
Near-optimal methods for minimizing star-convex functions and beyond
Oliver Hinder, Aaron Sidford, and Nimit Sharad Sohoni · 2019
Closest in time.