Geometric Rescaling Algorithms for Submodular Function Minimization

References

• [1] Bach F (2013) Learning with Submodular Functions: A Convex Optimization Perspective, Foundations and Trends in Machine Learning, vol. 6.Crossref, Google Scholar
• [2] Belloni A, Freund RM, Vempala S (2009) An efficient rescaled perceptron algorithm for conic systems. Math. Oper. Res. 34(3):621–641.Link, Google Scholar
• [3] Betke U (2004) Relaxation, new combinatorial and polynomial algorithms for the linear feasibility problem. Discrete Comput. Geometry 32(3):317–338.Crossref, Google Scholar
• [4] Chakrabarty D, Jain P, Kothari P (2014) Provable submodular minimization using Wolfe’s algorithm. Ghahramani Z, Welling M, Cortes C, Lawrence N, Weinberger KQ, eds. Adv. Neural Inform. Processing Systems 27:802–809.Google Scholar
• [5] Chakrabarty D, Lee YT, Sidford A, Wong SCw (2017) Subquadratic submodular function minimization. ACM Sympos. Theory Comput., 1220–1231.Google Scholar
• [6] Chubanov S (2017) A polynomial algorithm for linear feasibility problems given by separation oracles. Accessed March 23, 2017, http://www.optimization-online.org/DB_HTML/2017/01/5838.html.Google Scholar
• [7] Dadush D, Végh LA, Zambelli G (2020) Rescaling algorithms for linear conic feasibility. Math. Oper. Res. 45:403–795.Link, Google Scholar
• [8] Dantzig GB (1991) Converting a converging algorithm into a polynomially bounded algorithm. Technical Report SOL 91-5, Stanford University, Stanford, CA.Crossref, Google Scholar
• [9] Dantzig GB (1992) An ε-precise feasible solution to a linear program with a convexity constraint in 1/ε2 iterations independent of problem size. Technical Report 92-5, Stanford University, Stanford, CA.Google Scholar
• [10] Dunagan J, Vempala S (2008) A simple polynomial-time rescaling algorithm for solving linear programs. Math. Programming 114(1):101–114.Crossref, Google Scholar
• [11] Edmonds J (1970) Submodular functions, matroids, and certain polyhedra. Guy R, Hanani H, Sauer N, Schönheim J, eds. Combinatorial structures and their applications. Proc. Calgary Internat Conf. Combinatorial Structures Their Appl. (Gordon and Breach, New York), 69–87.Google Scholar
• [12] Ene AR, Nguyen HL (2015) Random coordinate descent methods for minimizing decomposable submodular functions. Proc. 32nd Internat. Conf. Machine Learn.Google Scholar
• [13] Ene AR, Nguyen HL, Végh LA (2017) Decomposable submodular function minimization: Discrete and continuous. Guyon I, Luxburg UV, Bengio S, Wallach H, Fergus R, Vishwanathan S, Garnett R, eds. Adv. Neural Inform. Processing Systems 30:2874–2884.Google Scholar
• [14] Fujishige S (1980) Lexicographically optimal base of a polymatroid with respect to a weight vector. Math. Oper. Res. 5(2):186–196.Link, Google Scholar
• [15] Fujishige S (2005) Submodular Functions and Optimization, vol. 58 (Elsevier, Amsterdam).Google Scholar
• [16] Fujishige S (2019) A note on submodular function minimization by Chubanov’s LP algorithm. Discrete Optim. 33:140–145.Crossref, Google Scholar
• [17] Fujishige S, Isotani S (2011) A submodular function minimization algorithm based on the minimum-norm base. Pacific J. Optim. 7(1):3–17.Google Scholar
• [18] Fujishige S, Iwata S (2002) A descent method for submodular function minimization. Math. Programming 92(2):387–390.Crossref, Google Scholar
• [19] Grötschel M, Lovász L, Schrijver A (1981) The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1(2):169–197.Google Scholar
• [20] Grötschel M, Lovász L, Schrijver A (1988) Geometric Algorithms and Combinatorial Optimization, Algorithms and Combinatorics, vol. 2 (Springer, Berlin).Crossref, Google Scholar
• [21] Hazan E, Kale S (2012) Online submodular minimization. J. Machine Learn. Res. 13(Oct):2903–2922.Google Scholar
• [22] Hoberg R, Rothvoß T (2017) An improved deterministic rescaling for linear programming algorithms. Internat. Conf. Integer Programming Combin. Optim., 267–278.Google Scholar
• [23] Iwata S (2003) A faster scaling algorithm for minimizing submodular functions. SIAM J. Comput. 32(4):833–840.Crossref, Google Scholar
• [24] Iwata S, Orlin JB (2009) A simple combinatorial algorithm for submodular function minimization. Proc. 20th Annual ACM-SIAM Sympos. Discrete Algorithms, 1230–1237.Google Scholar
• [25] Iwata S, Fleischer L, Fujishige S (2001) A combinatorial strongly polynomial algorithm for minimizing submodular functions. J. ACM 48(4):761–777.Crossref, Google Scholar
• [26] Jegelka S, Bilmes JA (2011) Online submodular minimization for combinatorial structures. Proc. 28th Internat. Conf. Machine Learn., 345–352.Google Scholar
• [27] Jegelka S, Lin H, Bilmes JA (2011) On fast approximate submodular minimization. Shawe-Taylor J, Zemel RS, Bartlett PL, Pereira F, Weinberger KQ, eds. Adv. Neural Inform. Processing Systems, 24:460–468.Google Scholar
• [28] Lacoste-Julien S, Jaggi M (2015) On the global linear convergence of Frank-Wolfe optimization variants. Proc. 28th Internat. Conf. Neural Inform. Processing Systems, vol. 1 (MIT Press, Cambridge, MA), 496–504.Google Scholar
• [29] Lee YT, Sidford A, Wong SC (2015) A faster cutting plane method and its implications for combinatorial and convex optimization. Preprint, submitted August 20, https://arxiv.org/abs/1508.04874.Google Scholar
• [30] Orlin JB (2009) A faster strongly polynomial time algorithm for submodular function minimization. Math. Programming 118(2):237–251.Crossref, Google Scholar
• [31] Peña J, Soheili N (2016) A deterministic rescaled perceptron algorithm. Math. Programming 155(1–2):497–510.Crossref, Google Scholar
• [32] Schrijver A (2000) A combinatorial algorithm minimizing submodular functions in strongly polynomial time. J. Combin. Theory Ser. B 80(2):346–355.Crossref, Google Scholar
• [33] Schrijver A (2003) Combinatorial Optimization—Polyhedra and Efficiency (Springer, Berlin).Google Scholar
• [34] Sohoni MA (1992) Membership in submodular and other polyhedra. Technical Report TR-102-92, Indian Institute of Technology, Bombay, India.Google Scholar
• [35] Stobbe P, Krause A (2010) Efficient minimization of decomposable submodular functions. Lafferty J, Williams C, Shawe-Taylor J, Zemel R, Culotta A, eds. Adv. Neural Inform. Processing Systems 23:2208–2216.Google Scholar
• [36] Tardos É (1985) A strongly polynomial minimum cost circulation algorithm. Combinatorica 5(3):247–255.Crossref, Google Scholar
• [37] Wolfe P (1976) Finding the nearest point in a polytope. Math. Programming 11(1):128–149.Crossref, Google Scholar