Discrete convex analysis

DOI10.1007/BF02680565zbMath0920.90103OpenAlexW4297069203MaRDI QIDQ1290668

Publication date: 3 June 1999

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02680565

zbMATH Keywords

conjugacy duality theorems Lagrange duality submodular functions discrete convex analysis discrete separation theorem

Mathematics Subject Classification ID

Integer programming (90C10) Combinatorial optimization (90C27)

Related Items

Discrete convexity: Convexity for functions defined on discrete spaces, Convex optimization on mixed domains, Quadratic M-convex and L-convex functions, Independence systems in gross-substitute valuations, Discrete Fenchel duality for a pair of integrally convex and separable convex functions, Multi-attribute based influence maximization in social networks: algorithms and analysis, Minimizing Multimodular Functions and Allocating Capacity in Bike-Sharing Systems, Matroid bases with cardinality constraints on the intersection, Convex analysis and duality over discrete domains, Fair integral submodular flows, A Discrete Convex Min-Max Formula for Box-TDI Polyhedra, M-Convex Function Minimization Under L1-Distance Constraint and Its Application to Dock Reallocation in Bike-Sharing System, Beyond JWP: A Tractable Class of Binary VCSPs via M-Convex Intersection., Personal reminiscence: combinatorial and discrete optimization problems in which I have been interested, Matroid rank functions and discrete concavity, Scaling, proximity, and optimization of integrally convex functions, Dynamic inventory control with payment delay and credit limit, Recent progress on integrally convex functions, A note on the implications of approximate submodularity in discrete optimization, Strategyproof allocation mechanisms with endowments and M-convex distributional constraints, MAP inference algorithms without approximation for collective graphical models on path graphs via discrete difference of convex algorithm, Discrete Midpoint Convexity, Streaming submodular maximization under $d$-knapsack constraints, Graphs with $G^p$-connected medians, Half-integrality of node-capacitated multiflows and tree-shaped facility locations on trees, An efficient algorithm for minimizing M-convex functions under a color-induced budget constraint, Characterization and algorithm for bivariate multi-unit assignment valuations, Geodesic property of greedy algorithms for optimization problems on jump systems and delta-matroids, New sufficient conditions for strong unimodality of multivariate discrete distributions, A discrete fixed point theorem and its applications., Polyhedra with submodular support functions and their unbalanced simultaneous exchangeability, Quasi M-convex and L-convex functions -- quasiconvexity in discrete optimization, New characterizations of M-convex functions and their applications to economic equilibrium models with indivisibilities., Optimization problems with cone constraints in groups and semigroups: an approach based on image space analysis, Theory of Principal Partitions Revisited, Recent Developments in Discrete Convex Analysis, Retrospective optimization of mixed-integer stochastic systems using dynamic simplex linear interpolation, Fast scaling algorithms for M-convex function minimization with application to the resource allocation problem., Discrete convexity built on differences, Projection and convolution operations for integrally convex functions, Application of M-convex submodular flow problem to mathematical economics, A polynomial-time algorithm for a stable matching problem with linear valuations and bounded side payments, Valuated matroid-based algorithm for submodular welfare problem, A framework of discrete DC programming by discrete convex analysis, Stability and competitive equilibria in multi-unit trading networks with discrete concave utility functions, Compression of $\mathrm{M}^\natural$-convex functions -- flag matroids and valuated permutohedra, L-extendable functions and a proximity scaling algorithm for minimum cost multiflow problem, Buyback problem with discrete concave valuation functions, Dijkstra's algorithm and L-concave function maximization, On circuit valuation of matroids, Discrete convexity and unimodularity. I., Conjugacy relationship between M-convex and L-convex functions in continuous variables, The Lovász extension of market games, Discrete convexity and equilibria in economies with indivisible goods and money, Applications of discrete convex analysis to mathematical economics, A general two-sided matching market with discrete concave utility functions, Coordinatewise domain scaling algorithm for M-convex function minimization, A note on discrete convexity and local optimality, Agreeable bets with multiple priors, Robust budget allocation via continuous submodular functions, A capacity scaling algorithm for M-convex submodular flow, Cone superadditivity of discrete convex functions, Directed discrete midpoint convexity, Subdivisions of integral base polytopes, Relationship of M-/L-convex functions with discrete convex functions by Miller and Favati-Tardella., A new approach to two-location joint inventory and transshipment control via $L^{\text{natural}}$-convexity, Discrete Convex Functions on Graphs and Their Algorithmic Applications, Submodular function minimization, Discrete convexity and polynomial solvability in minimum 0-extension problems, Optimal matroid bases with intersection constraints: valuated matroids, M-convex functions, and their applications, Integrality of subgradients and biconjugates of integrally convex functions, Preservation of Structural Properties in Optimization with Decisions Truncated by Random Variables and Its Applications, Convex Analysis in $\mathbb{Z}^n$ and Applications to Integer Linear Programming, Technical Note—Error Noted in “Order-Based Cost Optimization in Assemble-to-Order Systems” by Lu and Song (2005), A Tractable Class of Binary VCSPs via M-Convex Intersection, Coxeter submodular functions and deformations of Coxeter permutahedra, The secretary problem with multiple job vacancies and batch candidate arrivals, Pooling, pricing and trading of risks, Intersection pairings for higher laminations, Convex and quasiconvex functions in metric graphs, Computing the Degree of Determinants via Discrete Convex Optimization on Euclidean Buildings, Ideal Hierarchical Secret Sharing Schemes, New algorithms for convex cost tension problem with application to computer vision, Theoretical and algorithmic results for a class of hierarchical fleet mix problems, $k$-best solutions under distance constraints in valuated $\Delta$-matroids, Polynomial-Time Approximation Schemes for Maximizing Gross Substitutes Utility Under Budget Constraints, A survey of fundamental operations on discrete convex functions of various kinds, On basic operations related to network induction of discrete convex functions, Extension of M-convexity and L-convexity to polyhedral convex functions, Decreasing minimization on M-convex sets: background and structures, Decreasing minimization on M-convex sets: algorithms and applications, Substitutes and complements in network flows viewed as discrete convexity, Discrete polymatroids, 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

Cites Work