Discrete midpoint convexity
From MaRDI portal
combinatoricsconvexitymidpoint convexitydiscrete convex functionscaling algorithmintegral convexityproximity theorem\(L^\natural\)-convexity
Convex programming (90C25) Combinatorial optimization (90C27) Stochastic programming (90C15) Integer programming (90C10) Convex functions and convex programs in convex geometry (52A41) Theory of organizations, manpower planning in operations research (90B70) Stochastic scheduling theory in operations research (90B36)
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
- scientific article; zbMATH DE number 544186 (Why is no real title available?)
- scientific article; zbMATH DE number 651740 (Why is no real title available?)
- A capacity scaling algorithm for M-convex submodular flow
- ALGORITHMS FOR L-CONVEX FUNCTION MINIMIZATION: CONNECTION BETWEEN DISCRETE CONVEX ANALYSIS AND OTHER RESEARCH FIELDS
- Algebraic and geometric ideas in the theory of discrete optimization
- 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 L-convex function minimization based on continuous relaxation
- Discrete convex analysis
- Discrete fixed point analysis and its applications
- Discrete fixed point theorem reconsidered
- 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
- 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
- L-convexity on graph structures
Cited in
(13)- Note on the polyhedral description of the Minkowski sum of two L-convex sets
- Scaling, proximity, and optimization of integrally convex functions
- Minimizing Multimodular Functions and Allocating Capacity in Bike-Sharing Systems
- Discrete Fenchel duality for a pair of integrally convex and separable convex functions
- Directed discrete midpoint convexity
- scientific article; zbMATH DE number 6139733 (Why is no real title available?)
- More on discrete convexity
- The equivalence of discrete convexity and the classical definition of convexity
- Ameso optimization: a relaxation of discrete midpoint convexity
- Recent progress on integrally convex functions
- Scaling and proximity properties of integrally convex functions
- On basic operations related to network induction of discrete convex functions
- Discrete 2-convex functions
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)
