Discrete midpoint convexity
From MaRDI portal
\(L^\natural\)-convexitycombinatoricsconvexitydiscrete convex functionintegral convexitymidpoint convexityproximity theoremscaling algorithm
Convex functions and convex programs in convex geometry (52A41) Stochastic scheduling theory in operations research (90B36) Theory of organizations, manpower planning in operations research (90B70) Integer programming (90C10) Stochastic programming (90C15) Convex programming (90C25) Combinatorial optimization (90C27)
Abstract: For a function defined on a convex set in a Euclidean space, midpoint convexity is the property requiring that the value of the function at the midpoint of any line segment is not greater than the average of its values at the endpoints of the line segment. Midpoint convexity is a well-known characterization of ordinary convexity under very mild assumptions. For a function defined on the integer lattice, we consider the analogous notion of discrete midpoint convexity, a discrete version of midpoint convexity where the value of the function at the (possibly noninteger) midpoint is replaced by the average of the function values at the integer round-up and round-down of the midpoint. It is known that discrete midpoint convexity on all line segments with integer endpoints characterizes L-convexity, and that it characterizes submodularity if we restrict the endpoints of the line segments to be at -distance one. By considering discrete midpoint convexity for all pairs at -distance equal to two or not smaller than two, we identify new classes of discrete convex functions, called local and global discrete midpoint convex functions, which are strictly between the classes of L-convex and integrally convex functions, and are shown to be stable under scaling and addition. Furthermore, a proximity theorem, with the same small proximity bound as that for L-convex functions, is established for discrete midpoint convex functions. Relevant examples of classes of local and global discrete midpoint convex functions are provided.
Recommendations
Cites work
- L-convexity on graph structures
- A capacity scaling algorithm for M-convex submodular flow
- Algebraic and geometric ideas in the theory of discrete optimization
- ALGORITHMS FOR L-CONVEX FUNCTION MINIMIZATION: CONNECTION BETWEEN DISCRETE CONVEX ANALYSIS AND OTHER RESEARCH FIELDS
- Appointment scheduling with discrete random durations
- Bisubmodular polyhedra, simplicial divisions, and discrete convexity
- Combinatorial auctions with decreasing marginal utilities
- Complexity and algorithms for nonlinear optimization problems
- Conjugate Scaling Algorithm for Fenchel-Type Duality in Discrete Convex Optimization
- Convex functions
- Convex separable optimization is not much harder than linear optimization
- Discrete convex analysis
- Discrete Convex Analysis
- Discrete fixed point analysis and its applications
- Discrete fixed point theorem reconsidered
- Discrete L-convex function minimization based on continuous relaxation
- Discrete modeling of economic equilibrium problems
- Exact bounds for steepest descent algorithms of $L$-convex function minimization
- Existence of a pure strategy equilibrium in finite symmetric games where payoff functions are integrally concave
- scientific article; zbMATH DE number 544186 (Why is no real title available?)
- scientific article; zbMATH DE number 651740 (Why is no real title available?)
- L-extendable functions and a proximity scaling algorithm for minimum cost multiflow problem
- Mixed integer nonlinear programming. Selected papers based on the presentations at the IMA workshop mixed-integer nonlinear optimization: Algorithmic advances and applications, Minneapolis, MN, USA, November 17--21, 2008
- Network flows. Theory, algorithms, and applications.
- New algorithms for convex cost tension problem with application to computer vision
- Nonlinear discrete optimization. An algorithmic theory
- Nonlinear integer programming
- Notes on L-/M-convex functions and the separation theorems
- On \(k\)-submodular relaxation
- On the Structure of Lost-Sales Inventory Models
- Recent developments in discrete convex analysis
- Scaling and proximity properties of integrally convex functions
- Scaling, proximity, and optimization of integrally convex functions
- Submodular functions and optimization.
- The logic of logistics. Theory, algorithms, and applications for logistics management
- Time bounds for iterative auctions: a unified approach by discrete convex analysis
Cited in
(13)- Directed discrete midpoint convexity
- Discrete 2-convex functions
- 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
- Scaling, proximity, and optimization of integrally convex functions
- Ameso optimization: a relaxation of discrete midpoint convexity
- The equivalence of discrete convexity and the classical definition of convexity
- Scaling and proximity properties of integrally convex functions
- scientific article; zbMATH DE number 6139733 (Why is no real title available?)
- On basic operations related to network induction of discrete convex functions
- Minimizing Multimodular Functions and Allocating Capacity in Bike-Sharing Systems
- Recent progress on integrally convex functions
- More on discrete convexity
This page was built for publication: Discrete midpoint convexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5108259)
