Discrete Convex Analysis
This first monograph on discrete convex analysis has the main goal to establish a novel theoretical framework for solvable discrete optimization problems by means of a combination of the ideas in continuous and combinatorial optimization. More precisely, tools from convex analysis and matroid theory are combined. The major convexity concepts in this book are L-convexity (where ``L stands for lattice) and M-convexity (where ``M stands for matroid). The definition of L-convex functions is obtained from a generalization of the Lovász extension of submodular set functions. Beside a submodularity condition, L-convex functions have to be linear with respect to translation in the direction of \(1\). M-convex functions are motivated by a generalization of the simultaneaous exchange property of base polyhedra. Moreover, L-convex and M-convex functions enjoy a conjugacy relationship with respect to the discrete Legendre-Fenchel transformation. The book is divided into 12~chapters. In the first chapter central concepts like convex functions, submodular functions and base polyhedra are introduced. Moreover, definitions and properties of L-convex and M-convex functions are given. This part is a kind of preview of what will be explained in more detail in later chapters. Chapter \(2\) is devoted to convex functions with combinatorial structures. Here, quadratic functions, nonlinear networks, substitutes and complements in network flows and matroids are discussed. The next chapters deals with convex analysis, linear programming and integrality. A detailed introduction to M-convex sets and the relation to submodular set functions is the main topic of Chapter \(4\). In Chapter \(5\) L-convex sets are introduced and their relationship to distance functions is discussed. Chapter \(6\) and Chapter \(7\) are devoted to the properties of M-convex and L-convex functions. Conjugacy and duality for the introduced convexity concepts are treated in Chapter \(8\). In Chapter \(9\) the application of discrete convex analysis to network flows is discussed. Chapter \(10\) is devoted to algorithms for dealing with discrete convex functions and Chapter \(11\) presents an application to mathematical economics. The last chapter deals with an application to system analysis by mixed matrices. Each chapter has at the end some very useful bibliographical notes. The book contains more than 400 pages and lists 222 references. It is very well written and clearly structured. However, it has a quite theoretical focus and does nearly give no examples to illustrate the results.
- New algorithms for convex cost tension problem with application to computer vision
- Discrete convex analysis
- A Simple Algorithm for Exact Multinomial Tests
- Convex models of high dimensional discrete data
- Minimization of an M-convex function
- Fast scaling algorithms for M-convex function minimization with application to the resource allocation problem.
- Application of M-convex submodular flow problem to mathematical economics
- Notes on L-/M-convex functions and the separation theorems
- Enumerating polytropes
- Independence systems in gross-substitute valuations
- Uniqueness of equilibria in atomic splittable polymatroid congestion games
- Optimization problems with color-induced budget constraints
- The stochastic mitra-wan forestry model: risk neutral and risk averse cases
- Convex analysis and duality over discrete domains
- On the complexity of energy storage problems
- Discrete convexity in joint winner property
- Cores and Weber sets for fuzzy extensions of cooperative games
- Algebraic matroids and Frobenius flocks
- Gross substitutability: an algorithmic survey
- Randomized algorithms for finding the shortest negative cost cycle in networks
- The quadratic M-convexity testing problem
- Projection and convolution operations for integrally convex functions
- Simpler exchange axioms for M-concave functions on generalized polymatroids
- A stronger multiple exchange property for \(\mathrm{M}^{\natural }\)-concave functions
- Largest minimal inversion-complete and pair-complete sets of permutations
- Continuous relaxation for discrete DC programming
- Solving the degree-concentrated fault-tolerant spanning subgraph problem by DC programming
- Approximating convex functions via non-convex oracles under the relative noise model
- L-extendable functions and a proximity scaling algorithm for minimum cost multiflow problem
- Time bounds for iterative auctions: a unified approach by discrete convex analysis
- Buyback problem with discrete concave valuation functions
- Inventory rotation of medical supplies for emergency response
- Designing matching mechanisms under constraints: an approach from discrete convex analysis
- Conjugacy relationship between M-convex and L-convex functions in continuous variables
- \(M\)-convex functions and tree metrics
- Applications of discrete convex analysis to mathematical economics
- Coordinatewise domain scaling algorithm for M-convex function minimization
- Use of primal-dual technique in the network algorithm for two-way contingency tables
- A capacity scaling algorithm for M-convex submodular flow
- Exact bounds for steepest descent algorithms of $L$-convex function minimization
- Congestion games viewed from M-convexity
- Some specially structured assemble-to-order systems
- Traveling salesman games with the Monge property
- Discrete polymatroids
- Quadratic M-convex and L-convex functions
- Personal reminiscence: combinatorial and discrete optimization problems in which I have been interested
- Matching with partially ordered contracts
- Matroid rank functions and discrete concavity
- Shortest bibranchings and valuated matroid intersection
- Half-integrality of node-capacitated multiflows and tree-shaped facility locations on trees
- Envy-free matchings with lower quotas
- Walrasian's characterization and a universal ascending auction
- Positively hyperbolic varieties, tropicalization, and positroids
- Directed discrete midpoint convexity
- Relationship of two formulations for shortest bibranchings
- Nucleation and growth of lattice crystals
- Envy-free matchings with one-sided preferences and matroid constraints
- Convex and quasiconvex functions in metric graphs
- Explicit control of 2D and 3D structural complexity by discrete variable topology optimization method
- A cost-scaling algorithm for minimum-cost node-capacitated multiflow problem
- Discrete 2-convex functions
- Decreasing minimization on M-convex sets: background and structures
- Decreasing minimization on M-convex sets: algorithms and applications
- Submodular functions and rooted trees
- Adaptive sampling line search for local stochastic optimization with integer variables
- Computing valuations of the Dieudonné determinants
- Decreasing minimization on base-polyhedra: relation between discrete and continuous cases
- Note on the polyhedral description of the Minkowski sum of two L-convex sets
- Discrete Fenchel duality for a pair of integrally convex and separable convex functions
- A cost-scaling algorithm for computing the degree of determinants
- A constant-factor approximation for generalized malleable scheduling under \(M^\natural \)-concave processing speeds
- Resolution of ideals associated to subspace arrangements
- Fair integral submodular flows
- Logarithmic concavity for morphisms of matroids
- Fundamental polytopes of metric trees via parallel connections of matroids
- Uniform modular lattices and affine buildings
- Quantitative measure of nonconvexity for black-box continuous functions
- Lorentzian polynomials
- A note on M-convex functions on jump systems
- Consistency of the doctor-optimal equilibrium price vector in job-matching markets
- Tropical flag varieties
- Compression of \(\mathrm{M}^\natural\)-convex functions -- flag matroids and valuated permutohedra
- Dijkstra's algorithm and L-concave function maximization
- Geometry of gross substitutes valuations
- Computing Walrasian equilibria: fast algorithms and structural properties
- The discrete separation theorem and price adjustment directions in markets with heterogeneous commodities
- Conic relaxation approaches for equal deployment problems
- Integrality of subgradients and biconjugates of integrally convex functions
- A note on submodularity preserved involving the rank functions
- Discrete Newton methods for the evacuation problem
- Submodular optimization views on the random assignment problem
- Bisubmodular polyhedra, simplicial divisions, and discrete convexity
- A combinatorial formula for principal minors of a matrix with tree-metric exponents and its applications
- On properties of discrete (r,q) and (s,T) inventory systems
- Matroids from hypersimplex splits
- Note on time bounds of two-phase algorithms for \(L\)-convex function minimization
- Convex analysis in groups and semigroups: a sampler
- Scaling, proximity, and optimization of integrally convex functions
- On substitutability and complementarity in discrete choice models
- Private Bayesian persuasion
This page was built for publication: Discrete Convex Analysis
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4425020)
