A Characterization of Simultaneous Optimization, Majorization, and (Bi-)Submodular Polyhedra

References

• [1] Ando K (1996) Weak majorization on finite jump systems. Technical report, Institute of Socio-Economic Planning, University of Tsukuba, Tsukuba, Japan.Google Scholar
• [2] Ando K, Fujishige S (1996) On structures of bisubmodular polyhedra. Math. Programming 74(3):293–317.Crossref, Google Scholar
• [3] Arin J, Kuipers J, Vermeulen D (2003) Some characterizations of egalitarian solutions on classes of TU-games. Math. Soc. Sci. 46(3):327–345.Crossref, Google Scholar
• [4] Arnold BC, Sarabia JM (2018) Majorization and the Lorenz Order with Applications in Applied Mathematics and Economics, 1st ed. (Springer, Cham, Switzerland).Crossref, Google Scholar
• [5] Bach F (2013) Learning with submodular functions: A convex optimization perspective. Foundations Trends Machine Learn. 6(2–3):145–373.Crossref, Google Scholar
• [6] Bailey RA (2008) Design of Comparative Experiments, Cambridge Series in Statistical and Probabilistic Mathematics (Cambridge University Press, Cambridge, UK).Crossref, Google Scholar
• [7] Bilbao JM, Fernández JR, Jiménez N, López JJ (2008) A survey of bicooperative games. Chinchuluun A, Pardalos PM, Migdalas A, Pitsoulis L, eds. Pareto Optimality, Game Theory and Equilibria, Springer Optimization and Its Applications, vol. 17 (Springer, New York), 187–216.Crossref, Google Scholar
• [8] Bouchet A, Cunningham WH (1995) Delta-matroids, jump systems, and bisubmodular polyhedra. SIAM J. Discrete Math. 8(1):17–32.Crossref, Google Scholar
• [9] Burkard RE, Klinz B, Rudolf R (1996) Perspectives of Monge properties in optimization. Discrete Appl. Math. 70(2):95–161.Crossref, Google Scholar
• [10] Chakrabarty D, Goel G, Vazirani VV, Wang L, Yu C (2014) Submodularity helps in Nash and nonsymmetric bargaining games. SIAM J. Discrete Math. 28(1):99–115.Crossref, Google Scholar
• [11] Dai YH, Fletcher R (2006) New algorithms for singly linearly constrained quadratic programs subject to lower and upper bounds. Math. Programming 106(3):403–421.Crossref, Google Scholar
• [12] de Farias IR, Zhao M (2013) A polyhedral study of the semi-continuous knapsack problem. Math. Programming 142(1–2):169–203.Crossref, Google Scholar
• [13] Dunstan FDJ, Welsh DJA (1973) A greedy algorithm for solving a certain class of linear programmes. Math. Programming 5(1):338–353.Crossref, Google Scholar
• [14] Dutta B, Ray D (1989) A concept of egalitarianism under participation constraints. Econometrica 57(3):615–635.Crossref, Google Scholar
• [15] Eaton ML (1984) On group induced orderings, monotone functions, and convolution theorems. Tong YL, ed. Inequalities in Statistics and Probability, IMS Lecture Notes—Monographic Series, vol. 5 (Institute of Mathematical Statistics, Hayward, CA), 13–25.Crossref, Google Scholar
• [16] Edmonds J (2003) Submodular functions, matroids, and certain polyhedra. Jünger M, Reinelt G, Rinaldi G, eds. Combinatorial Optimization—Eureka, You Shrink! (Springer, Berlin), 11–26.Crossref, Google Scholar
• [17] Faigle U, Kern W, Peis B (2011) On greedy and submodular matrices. Marchetti-Spaccamela A, Segal M, eds. Theory and Practice of Algorithms in (Computer) Systems (Springer, Berlin), 116–126.Crossref, Google Scholar
• [18] Francis AR, Wynn HP (2014) Subgroup majorization. Linear Algebra Appl. 444:53–66.Crossref, Google Scholar
• [19] Frank A, Murota K (2020) Discrete decreasing minimization, part II: Views from discrete convex analysis. Preprint, submitted June 30, https://arxiv.org/abs/1808.08477.Google Scholar
• [20] Frank M, Wolfe P (1956) An algorithm for quadratic programming. Naval Res. Logist. Quart. 3(1–2):95–110.Crossref, Google Scholar
• [21] Fujishige S (1997) A min–max theorem for bisubmodular polyhedra. SIAM J. Discrete Math. 10(2):294–308.Crossref, Google Scholar
• [22] Fujishige S (2005) Submodular Functions and Optimization, 2nd ed. (Elsevier, Amsterdam).Google Scholar
• [23] Fujishige S, Tomizawa N (1983) A note on submodular functions on distributive lattices. J. Oper. Res. Soc. Japan 26(4):309–318.Google Scholar
• [24] Fujishige S, Tanigawa SI, Yoshida Y (2014) Generalized skew bisubmodularity: A characterization and a min–max theorem. Discrete Optim. 12:1–9.Crossref, Google Scholar
• [25] Fujishige S, Makino K, Takabatake T, Kashiwabara K (2004) Polybasic polyhedra: Structure of polyhedra with edge vectors of support size at most 2. Discrete Math 280(1):13–27.Crossref, Google Scholar
• [26] Gerards MET, Hurink JL, Hölzenspies PKF (2016) A survey of offline algorithms for energy minimization under deadline constraints. J. Scheduling 19(1):3–19.Crossref, Google Scholar
• [27] Goel A, Meyerson A (2006) Simultaneous optimization via approximate majorization for concave profits or convex costs. Algorithmica 44(4):301–323.Crossref, Google Scholar
• [28] Guo Y, Fang Y (2013) Electricity cost saving strategy in data centers by using energy storage. IEEE Trans. Parallel Distributed Systems 24(6):1149–1160.Crossref, Google Scholar
• [29] Hastie T, Tibshirani R, Friedman J (2009) The Elements of Statistical Learning, 2nd ed. (Springer, New York).Crossref, Google Scholar
• [30] Huber A, Kolmogorov V (2012) Toward minimizing k-submodular functions. Mahjoub AR, Markakis V, Milis I, Paschos VT, eds. Combinatorial Optimization (ISCO 2012), Lecture Notes in Computer Science, vol. 7422 (Springer, Berlin), 451–462.Crossref, Google Scholar
• [31] Ichiishi T (1981) Super-modularity: Applications to convex games and to the greedy algorithm for LP. J. Econom. Theory 25(2):283–286.Crossref, Google Scholar
• [32] Jaggi M (2013) Revisiting Frank-Wolfe: Projection-free sparse convex optimization. Dasgupta S, McAllester D, eds. Proc. 30th Internat. Conf. Machine Learn., vol. 28 (PMLR, New York), 427–435.Google Scholar
• [33] Joe H (1990) Majorization and divergence. J. Math Anal. Appl. 148(2):287–305.Crossref, Google Scholar
• [34] Jorswieck E, Boche H (2006) Majorization and matrix-monotone functions in wireless communications. Foundations Trends Comm. Inform. Theory 3(6):553–701.Crossref, Google Scholar
• [35] Mairal J, Jenatton R, Obozinski G, Bach F (2011) Convex and network flow optimization for structured sparsity. J. Machine Learn. Res. 12(81):2681–2720.Google Scholar
• [36] Marshall AW, Olkin I, Arnold BC (2011) Inequalities: Theory of Majorization and Its Applications, 2nd ed. (Springer, New York).Crossref, Google Scholar
• [37] Nakamura M (1988) A characterization of greedy sets: Universal polymatroids. Sci. Papers College Arts Sci. Univ. Tokyo 38(2):155–167.Google Scholar
• [38] Niezgoda M (2012) Cone orderings, group majorizations and similarly separable vectors. Linear Algebra Appl. 436(3):579–594.Crossref, Google Scholar
• [39] Palomar DP, Fonollosa JR (2005) Practical algorithms for a family of waterfilling solutions. IEEE Trans. Signal Processing 53(2):686–695.Crossref, Google Scholar
• [40] Patriksson M (2008) A survey on the continuous nonlinear resource allocation problem. Eur. J. Oper. Res. 185(1):1–46.Crossref, Google Scholar
• [41] Reijnders VMJJ, Gerards MET, Hurink JL (2022) A hybrid electricity pricing mechanism for joint system optimization and social acceptance within energy communities. Energy Rep. 8:13281–13292.Crossref, Google Scholar
• [42] Schoot Uiterkamp MHH, Gerards MET, Hurink JL (2022) On a reduction for a class of resource allocation problems. INFORMS J. Comput. 34(3):1387–1402.Link, Google Scholar
• [43] Schoot Uiterkamp MHH, van der Klauw T, Gerards MET, Hurink JL (2018) Offline and online scheduling of electric vehicle charging with a minimum charging threshold. 2018 IEEE Internat. Conf. Comm. Control Comput. Tech. Smart Grids (SmartGridComm) (IEEE, Piscataway, NJ).Google Scholar
• [44] Shams F, Bacci G, Luise M (2014) A survey on resource allocation techniques in OFDM(A) networks. Comput. Networks 65:129–150.Crossref, Google Scholar
• [45] Tamir A (1995) Least majorized elements and generalized polymatroids. Math Oper. Res. 20(3):583–589.Link, Google Scholar
• [46] van der Klauw T, Gerards MET, Hurink JL (2017) Resource allocation problems in decentralized energy management. OR Spectrum 39(3):749–773.Crossref, Google Scholar
• [47] Veinott AF (1971) Least d-majorized network flows with inventory and statistical applications. Management Sci. 17(9):547–567.Link, Google Scholar
• [48] Zhan P (2005) Polyhedra and optimization related to a weak absolute majorization ordering. J. Oper. Res. Soc. Japan 48(2):90–96.Google Scholar
• [49] Zurovac J, Brown R (2012) Orthogonal design: A powerful method for comparative effectiveness research with multiple interventions. Technical report, Mathematica Policy Research, Princeton, NJ.Google Scholar