𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Extension of M-Convexity and L-Convexity to Polyhedral Convex Functions

✍ Scribed by Kazuo Murota; Akiyoshi Shioura

Publisher
Elsevier Science
Year
2000
Tongue
English
Weight
454 KB
Volume
25
Category
Article
ISSN
0196-8858

No coin nor oath required. For personal study only.

✦ Synopsis

The concepts of M-convex and L-convex functions were proposed by Murota in 1996 as two mutually conjugate classes of discrete functions over integer lattice points. M/L-convex functions are deeply connected with the well-solvability in nonlinear combinatorial optimization with integer variables. In this paper, we extend the concept of M-convexity and L-convexity to polyhedral convex functions, aiming at clarifying the well-behaved structure in well-solved nonlinear combinatorial optimization problems in real variables. The extended M/L-convexity often appears in nonlinear combinatorial optimization problems with piecewise-linear convex cost. We investigate the structure of polyhedral M-convex and L-convex functions from the dual viewpoint of analysis and combinatorics and provide some properties and characterizations. It is also shown that polyhedral M/L-convex functions have nice conjugacy relationships.

πŸ“œ SIMILAR VOLUMES

Extremal Approximately Convex Functions
Extremal Approximately Convex Functions and Estimating the Size of Convex Hulls
✍ S.J. Dilworth; Ralph Howard; James W. Roberts πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 540 KB

A real-valued function f defined on a convex set K is an approximately convex function iff it satisfies A thorough study of approximately convex functions is made. The principal results are a sharp universal upper bound for lower semi-continuous approximately convex functions that vanish on the ver

Voronoi Diagrams of Lines in 3-Space Und
Voronoi Diagrams of Lines in 3-Space Under Polyhedral Convex Distance Functions
✍ L.Paul Chew; Klara Kedem; Micha Sharir; Boaz Tagansky; Emo Welzl πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 261 KB

The combinatorial complexity of the Voronoi diagram of n lines in three dimensions under a convex distance function induced by a polytope with a constant Ž 2 Ž . . Ž . number of edges is shown to be O n ␣ n log n , where ␣ n is a slowly growing inverse of the Ackermann function. There are arrangemen

Partial Sums of Starlike and Convex Func
Partial Sums of Starlike and Convex Functions
✍ H Silverman πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 135 KB

Let f z szqÝ a z be the sequence of partial sums of a function a z that is analytic in z -1 and either starlike of order ␣ or ks 2 k Γ„ 4 convex of order ␣, 0 F ␣ -1. When the coefficients a are ''small,'' we deterk Γ„ Ε½ . Ε½ 4 Γ„ Ε½ . Ε½ .4 Γ„ Ε½ . X Ε½ .4 mine lower bounds on Re f z rf z , Re f z rf z , R