Lisa Fleischer
- 1.W. H. Cunningham. Testing membership in matroid polyhedra. J. Combinatorial Theory B, 36:161-188, 1984.]]Google Scholar
Cross 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
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 ...
Submodular function minimization under a submodular set covering constraint
TAMC'11: Proceedings of the 8th annual conference on Theory and applications of models of computationIn this paper, we consider the problem of minimizing a submodular function under a submodular set covering constraint. We propose an approximation algorithm for this problem by extending the algorithm of Iwata and Nagano [FOCS'09] for the set cover ...
Comments