Discrete Midpoint Convexity

References

• [1] Ahuja RK, Magnanti TL, Orlin JB (1993) Network Flows—Theory, Algorithms and Applications (Prentice-Hall, Englewood Cliffs, NJ).Google Scholar
• [2] Beckenbach EF (1948) Convex functions. Bull. Amer. Math. Soc. 54(5):439–460.Crossref, Google Scholar
• [3] Begen M, Queyranne M (2011) Appointment scheduling with discrete random durations. Math. Oper. Res. 36(2):240–257.Link, Google Scholar
• [4] De Loera JA, Hemmecke R, Köppe M (2013) Algebraic and Geometric Ideas in the Theory of Discrete Optimization (SIAM, Philadelphia).Google Scholar
• [5] Favati P, Tardella F (1990) Convexity in nonlinear integer programming. Ricerca Operativa 53:3–44.Google Scholar
• [6] Fujishige S (2005) Submodular Functions and Optimization, 2nd ed. (Elsevier, Amsterdam).Google Scholar
• [7] Fujishige S (2014) Bisubmodular polyhedra, simplicial divisions, and discrete convexity. Discrete Optim. 12:115–120.Crossref, Google Scholar
• [8] Fujishige S, Murota K (2000) Notes on L-/M-convex functions and the separation theorems. Math. Programming 88(1):129–146.Crossref, Google Scholar
• [9] Hemmecke R, Köppe M, Lee J, Weismantel R (2010) Nonlinear integer programming. Jünger M, et al.. eds. 50 Years of Integer Programming 1958–2008: From the Early Years to the State-of-the-Art (Springer, Berlin), 561–618.Crossref, Google Scholar
• [10] Hirai H (2015) L-extendable functions and a proximity scaling algorithm for minimum cost multiflow problem. Discrete Optim. 18:1–37.Crossref, Google Scholar
• [11] Hirai H (2018) L-convexity on graph structures. J. Oper. Res. Soc. Japan 61(1):71–109.Crossref, Google Scholar
• [12] Hirai H, Iwamasa Y (2016) On k-submodular relaxation. SIAM J. Discrete Math. 30(3):1726–1736.Crossref, Google Scholar
• [13] Hochbaum DS (2007) Complexity and algorithms for nonlinear optimization problems. Ann. Oper. Res. 153(1):257–296.Crossref, Google Scholar
• [14] Hochbaum DS, Shanthikumar JG (1990) Convex separable optimization is not much harder than linear optimization. J. ACM 37(4):843–862.Crossref, Google Scholar
• [15] Ibaraki T, Katoh N (1988) Resource Allocation Problems: Algorithmic Approaches (MIT Press, Boston).Google Scholar
• [16] Iimura T (2010) Discrete modeling of economic equilibrium problems. Pacific J. Optim. 6(1):57–64.Google Scholar
• [17] Iimura T, Watanabe T (2014) Existence of a pure strategy equilibrium in finite symmetric games where payoff functions are integrally concave. Discrete Appl. Math. 166:26–33.Crossref, Google Scholar
• [18] Iimura T, Murota K, Tamura A (2005) Discrete fixed point theorem reconsidered. J. Math. Econom. 41(8):1030–1036.Crossref, Google Scholar
• [19] Iwata S, Shigeno M (2002) Conjugate scaling algorithm for Fenchel-type duality in discrete convex optimization. SIAM J. Optim. 13(1):204–211.Crossref, Google Scholar
• [20] Iwata S, Moriguchi S, Murota K (2005) A capacity scaling algorithm for M-convex submodular flow. Math. Programming 103(1):181–202.Crossref, Google Scholar
• [21] Jensen JLWV (1905) Om konvekse funktioner og uligheder imellem Middelværdier. Mathematica Scandinavica 16B: 49–68. Also: (1906) Sur les fonctions convexes et les inégalités entre les valeurs moyennes. Acta Mathematica 30:175–193.Crossref, Google Scholar
• [22] Katoh N, Shioura A, Ibaraki T (2013) Resource allocation problems. Pardalos PM, Du DZ, Graham RL, eds. Handbook of Combinatorial Optimization, vol. 5, 2nd ed. (Springer, Berlin), 2897–2988.Crossref, Google Scholar
• [23] Kolmogorov V, Shioura A (2009) New algorithms for convex cost tension problem with application to computer vision. Discrete Optim. 6(4):378–393.Crossref, Google Scholar
• [24] Lee J, Leyffer S, eds. (2012) Mixed Integer Nonlinear Programming (Springer, Berlin).Crossref, Google Scholar
• [25] Lehmann B, Lehmann D, Nisan N (2006) Combinatorial auctions with decreasing marginal utilities. Games Econom. Behav. 55(2):270–296.Crossref, Google Scholar
• [26] Moriguchi S, Tsuchimura N (2009) Discrete L-convex function minimization based on continuous relaxation. Pacific J. Optim. 5(2):227–236.Google Scholar
• [27] Moriguchi S, Murota K, Tamura A, Tardella F (2016) Scaling and proximity properties of integrally convex functions. Hong S, ed. 27th Internat. Sympos. Algorithms Comput. (ISAAC 2016), Leibniz International Proceedings in Informatics (LIPIcs), vol. 64 (Schloss Dagstuhl – Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Wadern, Germany), 57:1–12.Google Scholar
• [28] Moriguchi S, Murota K, Tamura A, Tardella F (2019) Scaling, proximity, and optimization of integrally convex functions. Math. Programming 175(1–2):119–154.Crossref, Google Scholar
• [29] Murota K (1998) Discrete convex analysis. Math. Programming 83(3):313–371.Crossref, Google Scholar
• [30] Murota K (2003) Discrete Convex Analysis (SIAM, Philadelphia).Crossref, Google Scholar
• [31] Murota K (2009) Recent developments in discrete convex analysis. Cook W, Lovász L, Vygen J, eds. Research Trends in Combinatorial Optimization (Springer, Berlin), 219–260.Crossref, Google Scholar
• [32] Murota K (2016) Discrete convex analysis: A tool for economics and game theory. J. Mechanism Institution Design 1(1):149–271.Crossref, Google Scholar
• [33] Murota K, Shioura A (2014) Exact bounds for steepest descent algorithms of L-convex function minimization. Oper. Res. Lett. 42(5):361–366.Crossref, Google Scholar
• [34] Murota K, Tamura A (2002) Proximity Theorems of Discrete Convex Functions, RIMS Preprint (Kyoto University, Kyoto, Japan), 1358.Google Scholar
• [35] Murota K, Shioura A, Yang Z (2016) Time bounds for iterative auctions: A unified approach by discrete convex analysis. Discrete Optim. 19:36–62.Crossref, Google Scholar
• [36] Onn S (2010) Nonlinear Discrete Optimization: An Algorithmic Theory (European Mathematical Society, Zurich).Crossref, Google Scholar
• [37] Shioura A (2017) Algorithms for L-convex function minimization: Connection between discrete convex analysis and other research areas. J. Oper. Res. Soc. Japan 60(3):216–243.Crossref, Google Scholar
• [38] Simchi-Levi D, Chen X, Bramel J (2014) The Logic of Logistics: Theory, Algorithms, and Applications for Logistics Management, 3rd ed. (Springer, New York).Crossref, Google Scholar
• [39] Thomson B (1994) Symmetric Properties of Real Functions (Marcel Dekker, New York).Google Scholar
• [40] Yang Z (2009) Discrete fixed point analysis and its applications. J. Fixed Point Theory Appl. 6(2):351–371.Crossref, Google Scholar
• [41] Zipkin P (2008) On the structure of lost-sales inventory models. Oper. Res. 56(4):937–944.Link, Google Scholar