- 1.W. H. Cunningham. Testing membership in matroid polyhedra. J. Combinatorial Theory B, 36:161-188, 1984.]]Google ScholarCross Ref
- 2.W. H. Cunningham. On submodular function minimization. Combinatorica, 5:185-192, 1985.]] Google ScholarDigital Library
- 3.J. Edmonds. Submodular functions, matroids, and certain polyhedra. In R. Guy, H. Hanani, N. Sauer, and J. Sch/Snheim, editors, Combinatorial Structures and their Applications, pages 69-87. Gordon and Breach, 1970.]]Google Scholar
- 4.J. Edmonds and R. Giles. A min-max relation for submodular functions on graphs. Ann. Discrete Math., 1:185-204, 1977.]]Google ScholarCross Ref
- 5.L. Fleischer, S, Iwata, and S. T. McCormick. A faster capacity scaling algorithm for submodular flow. Technical Report 9947, C.O.R.E. Discussion Paper, Louvain-la-Neuve, Belgium, 1999.]]Google Scholar
- 6.A. Frank. Finding feasible vectors of Edmonds-Giles polyhedra. J. Combin. Theory, 36:221-239, 1984.]]Google ScholarCross Ref
- 7.A. Frank and l~. Tardos. An application of submodular flows. Linear algebra and its applications, 114/115:329--348, 1989.]]Google Scholar
- 8.S. Fujishige, H. R6ck, and U. Zimmermann. A strongly polynomial algorithm for minimum cost submodular flow problems. Math. Oper. Res., 14:60-69, 1989.]]Google ScholarDigital Library
- 9.S. Fujishige and X. Zhang. New algorithms for the intersection problem of submodular systems. Japan J. lndust. Appl. Math., 9:369-382, 1992.]]Google Scholar
- 10.A. V. Goldberg and R. E. Tarjan. A new approach to the maximum flow problem. Journal of the ACM, 35:921-940, 1988.]] Google ScholarDigital Library
- 11.M. Grotschel, L. Lovasz, and A, Schrijver. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, 1:169-197, 1981.]]Google ScholarCross Ref
- 12.S. Iwata, L. Fleischer, and S. Fujishige. A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions. In Proceedings of the 32th Annual ACM Symposium on Theory of Computing, 2000. This proceedings.]] Google ScholarDigital Library
- 13.S. Iwata, S. T. McCormick, and M. Shigeno. A fast cost scaling algorithm for submodular flow. To appear.]]Google Scholar
- 14.T. Jordfin. Edge-splitting problems with demands. In G. Cornu6jols, R. E. Burkard, and G. J. Woeginger, editors, Integer Programming and Combinatorial Optimization, volume 1610 of LNCS, pages 273-288, Graz, Austria, June 1999. Springer.]] Google ScholarDigital Library
- 15.M. Queyranne. Minimizing symmetric submodular functions. Math. Programming, 82:3-12, 1998.]]Google ScholarCross Ref
- 16.A. Schrijver. A combinatorial algorithm minimizing submodular functions in strongly polynomial time. Preprint. Submitted to JCTB., 1999.]] Google ScholarDigital Library
Index Terms
- Improved algorithms for submodular function minimization and submodular flow
Recommendations
A lower bound for parallel submodular minimization
STOC 2020: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of ComputingIn this paper, we study submodular function minimization in the adaptive complexity model. Seminal work by Gr'otschel, Lovász, and Schrijver shows that with oracle access to a function f, the problem of submodular minimization can be solved exactly with ...
Subquadratic submodular function minimization
STOC 2017: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of ComputingSubmodular function minimization (SFM) is a fundamental discrete optimization problem which generalizes many well known problems, has applications in various fields, and can be solved in polynomial time. Owing to applications in computer vision and ...
Submodular Function Minimization under Covering Constraints
FOCS '09: Proceedings of the 2009 50th Annual IEEE Symposium on Foundations of Computer ScienceThis paper addresses the problems of minimizing nonnegative submodular functions under covering constraints, which generalize the vertex cover, edge cover, and set cover problems. We give approximation algorithms for these problems exploiting the ...
Comments