The present note reveals the role of the concept of greedy system of linear inequalities played in connection with lexicographically optimal solutions on convex polyhedra and discrete convexity. The lexicographically optimal solutions on convex polyhedra represented by a greedy system of linear inequalities can be obtained by a greedy procedure, a special form of which is the greedy algorithm of J. Edmonds for polymatroids. We also examine when the lexicographically optimal solutions become integral. By means of the Fourier–Motzkin elimination Murota and Tamura have recently shown the existence of integral points in a polyhedron arising as a subdifferential of an integer-valued, integrally convex function due to Favati and Tardella [Murota and Tamura, Integrality of subgradients and biconjugates of integrally convex functions. Preprint arXiv:1806.00992v1 (2018)], which can be explained by our present result. A characterization of integrally convex functions is also given.
Accepté le :
DOI : 10.1051/ro/2019001
Keywords: Greedy system, lexicographic optimality, discrete convexity, integrally convex functions
Fujishige, Satoru 1
@article{RO_2019__53_5_1929_0,
author = {Fujishige, Satoru},
title = {Greedy systems of linear inequalities and lexicographically optimal solutions},
journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
pages = {1929--1935},
year = {2019},
publisher = {EDP Sciences},
volume = {53},
number = {5},
doi = {10.1051/ro/2019001},
mrnumber = {4023844},
zbl = {1430.90398},
language = {en},
url = {https://www.numdam.org/articles/10.1051/ro/2019001/}
}
TY - JOUR AU - Fujishige, Satoru TI - Greedy systems of linear inequalities and lexicographically optimal solutions JO - RAIRO - Operations Research - Recherche Opérationnelle PY - 2019 SP - 1929 EP - 1935 VL - 53 IS - 5 PB - EDP Sciences UR - https://www.numdam.org/articles/10.1051/ro/2019001/ DO - 10.1051/ro/2019001 LA - en ID - RO_2019__53_5_1929_0 ER -
%0 Journal Article %A Fujishige, Satoru %T Greedy systems of linear inequalities and lexicographically optimal solutions %J RAIRO - Operations Research - Recherche Opérationnelle %D 2019 %P 1929-1935 %V 53 %N 5 %I EDP Sciences %U https://www.numdam.org/articles/10.1051/ro/2019001/ %R 10.1051/ro/2019001 %G en %F RO_2019__53_5_1929_0
Fujishige, Satoru. Greedy systems of linear inequalities and lexicographically optimal solutions. RAIRO - Operations Research - Recherche Opérationnelle, Tome 53 (2019) no. 5, pp. 1929-1935. doi: 10.1051/ro/2019001
and , On structures of bisubmodular polyhedra. Math. Program. Ser. A 74 (1996) 293–317. | MR | Zbl | DOI
, and , A characterization of bisubmodular functions. Discrete Math. 148 (1996) 299–303. | MR | Zbl | DOI
and , Delta-matroids, jump systems, and bisubmodular polyhedra. SIAM J. Discrete Math. 8 (1995) 17–32. | MR | Zbl | DOI
and , Pseudomatroids. Discrete Math. 71 (1988) 205–217. | MR | Zbl | DOI
and , A greedy algorithm for solving a certain class of linear programmes. Math. Program. 62 (1973) 338–353. | MR | Zbl | DOI
and , Convexity in nonlinear integer programming. Ric. Oper. 53 (1990) 3–44.
, Submodular Functions and Optimization. Elsevier, North-Holland (1991) | MR | Zbl
, Discrete convex functions on graphs and their algorithmic applications, edited by and . In: Combinatorial Optimization Graph Algorithms Springer, Singapore (2017) 67–100. | MR | DOI
and , Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization. Math. Program. Ser. A 122 (2010) 87–120. | MR | Zbl | DOI
, Discrete Convex Analysis. SIAM, Philadelphia, PN (2003). | MR | Zbl | DOI
, Discrete convex analysis: a tool for economics and game theory. J. Mech. Inst. Des. 1 (2016) 151–273.
, , Relationship of M-/L-convex functions with discrete convex functions by Miller and by Favati-Tardella. Discrete Appl. Math. 115 (2001) 151–176. | MR | Zbl | DOI
and , Integrality of subgradients and biconjugates of integrally convex functions. Preprint arXiv:1806.00992v1 (2018). | MR
Cité par Sources :
