Montag, 01. April 2019, 17:00 - 18:00 iCal

ISOR Colloquium

"Discrete midpoint convexity: a unifying framework for convexity on the integer lattice (joint work with S. Moriguchi, K. Murota and A. Tamura)"

Speaker: Fabio Tardella (Univ. Rome "La Sapienza")

HS 7 OMP1 (#1.303, 1st floor)
Oskar-Morgenstern-Platz 1, 1090 Wien

Vortrag

---

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 segment. Under very mild assumptions, midpoint convexity is a well-known characterization of ordinary convexity. A discrete version of midpoint convexity is proposed here for functions defined on the integer lattice. A discrete midpoint point convex function is characterized by 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. We show that discrete midpoint convexity has nice theoretical and algorithmic properties, including (pseudo) polynomial-time minimization under appropriate assumptions. Furthermore, by restricting the distance between the endpoints in the discrete midpoint convexity definition, one obtains new classes of discretely convex functions and a unifying framework for several well-known notions of discrete convexity and for the notion of submodularity over the integer lattice.

Zur Webseite der Veranstaltung

---

Veranstalter

Institut für Statistik und Operations Research

---

Kontakt

Mag. Vera Lehmwald
Fakultät für Wirtschaftswissenschaften
Institut für Statistik und Operations Research
+43 1 4277 38651
vera.lehmwald@univie.ac.at

Erstellt am Montag, 18. März 2019, 12:47
Letzte Änderung am Montag, 18. März 2019, 13:04