A Structure Theory for the Parametric Submodular Intersection Problem

References

• Edmonds J., Guy R., Hanani H., Sauer N., Schönheim J. Submodular functions, matroids, and certain polyhedra. Combinatorial Structures and Their Applications (1970) (Gordon and Breach, New York) 69–87Google Scholar
• Fleischer L., Iwata S. A push-relabel framework for submodular function minimization and applications to parametric optimization. Discrete Appl. Math. (2003) 131:311–322Crossref, Google Scholar
• Fujishige S. Lexicographically optimal base of a polymatroid with respect to a weight vector. Math. Oper. Res. (1980) 5:186–196Link, Google Scholar
• Fujishige S.Submodular Functions and Optimization (2005) 2nd ed.(Elsevier, Amsterdam) Google Scholar
• Gallo G., Grigoriadis M. D., Tarjan R. E. A fast parametric maximum flow algorithm and applications. SIAM J. Comput. (1989) 18:30–55Crossref, Google Scholar
• Iri M. A review of recent work in Japan on principal partitions of matroids and their applications. Ann. New York Acad. Sci. (1979) 319:306–319Crossref, Google Scholar
• Iri M., Pulleyblank W. R. Structural theory for the combinatorial systems characterized by submodular functions. Progress in Combinatorial Optimization (1984) (Academic Press, New York) 197–219Crossref, Google Scholar
• Iwata S. Submodular function minimization. Math. Programming (2008) 112:45–64Crossref, Google Scholar
• Iwata S., Murota K., Shigeno M. A fast parametric submodular intersection algorithm for strong map sequences. Math. Oper. Res. (1997) 22:803–813Link, Google Scholar
• McCormick S. T. Fast algorithms for parametric scheduling come from extensions to parametric maximum flow. Oper. Res. (2000) 47:744–756Link, Google Scholar
• McCormick S. T., Aardal K., Nemhauser G. L., Weismantel R. Submodular function minimization. Discrete Optimization. Handbooks in Operations Research and Management Science (2005) 12(Elsevier, Amsterdam) 321–391Crossref, Google Scholar
• Megiddo N. Optimal flows in networks with multiple sources and sinks. Math. Programming (1974) 7:97–107Crossref, Google Scholar
• Murota K.Matrices and Matroids for Systems Analysis (2000) (Springer-Verlag, Berlin) Google Scholar
• Nagano K. A faster parametric submodular function minimization algorithm and applications. (2007) . Mathematical Engineering Technical Reports METR 2007-43, Department of Mathematical Informatics, Graduate School of Information Science and Technology, University of Tokyo, Tokyo, Japan, July, http://www.keisu.t.u-tokyo.ac.jp/research/techrep/Google Scholar
• Nakamura M. Structural theorems for submodular functions, polymatroids and polymatroid intersections. Graphs Combinatorics (1988) 4:257–284Crossref, Google Scholar
• Nakamura M., Iri M. A structural theory for submodular functions, polymatroids and polymatroid intersections. (1981) . Research Memorandum RMI 81-06, Department of Mathematical Engineering and Instrumentation Physics, Faculty of Engineering, University of Tokyo, TokyoGoogle Scholar
• Recski A.Matroid Theory and Its Applications in Electric Network and in Statics (1989) (Springer-Verlag, Berlin) Crossref, Google Scholar
• Shapley L. S. A value for n-person games. Ann. Math. Stud. (1953) 28:307–317Google Scholar
• Shapley L. S. Cores of convex games. Internat. J. Game Theory (1971) 1:11–26Crossref, Google Scholar
• Topkis D. M. Minimizing a submodular function on a lattice. Oper. Res. (1978) 26:305–321Link, Google Scholar