Discrete Convex AnalysisDiscrete Convex Analysis is a novel paradigm for discrete optimization that combines the ideas in continuous optimization (convex analysis) and combinatorial optimization (matroid/submodular function theory) to establish a unified theoretical framework for nonlinear discrete optimization. The study of this theory is expanding with the development of efficient algorithms and applications to a number of diverse disciplines like matrix theory, operations research, and economics. This self-contained book is designed to provide a novel insight into optimization on discrete structures and should reveal unexpected links among different disciplines. It is the first and only English-language monograph on the theory and applications of discrete convex analysis. Discrete Convex Analysis provides the information that professionals in optimization will need to "catch up" with this new theoretical development. It also presents an unexpected connection between matroid theory and mathematical economics and expounds a deeper connection between matrices and matroids than most standard textbooks. |
Other editions - View all
Common terms and phrases
algorithm applied associated assume axiom base bounded called characterized Claim combinatorial concave condition conjugacy conjugate consider convex functions correspondence cost criterion defined definition denote derived described directed discrete convex domain equilibrium equivalent Example exchange exists extension fact feasible finite follows function f functions section given graph Hence implies inequality integer-valued integral integrally convex intersection linear M-convex set matrix matroid maximal means minimizer Minkowski sum Murota Note obtain optimal pair points polyhedral polyhedron polynomial potential Proof Proposition prove quadratic R U oo represented respectively satisfies scaling separation theorem shows submodular submodular flow problem submodular functions submodular set function supp suppº Suppose symmetric matrix Theorem theory tion transformation vector vertex whereas