{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,9,21]],"date-time":"2023-09-21T13:01:45Z","timestamp":1695301305872},"reference-count":13,"publisher":"EDP Sciences","issue":"5","license":[{"start":{"date-parts":[[2019,10,28]],"date-time":"2019-10-28T00:00:00Z","timestamp":1572220800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.edpsciences.org\/en\/authors\/copyright-and-licensing"}],"funder":[{"name":"JSPS Grant-in-Aid for Scientific  Research KAKENHI","award":["25280004"],"award-info":[{"award-number":["25280004"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"accepted":{"date-parts":[[2018,12,22]]},"published-print":{"date-parts":[[2019,11]]},"abstract":"<jats:p>The present note reveals the role of the concept of <jats:italic>greedy system of linear inequalities<\/jats:italic> played in connection with <jats:italic>lexicographically optimal solutions<\/jats:italic> on convex polyhedra and <jats:italic>discrete convexity<\/jats:italic>. The lexicographically optimal solutions on convex polyhedra represented by a greedy system of linear inequalities can be obtained by a <jats:italic>greedy procedure<\/jats:italic>, 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\u2013Motzkin 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:<jats:ext-link xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" ext-link-type=\"uri\" xlink:href=\"https:\/\/arxiv.org\/abs\/1806.00992v1\">1806.00992v1<\/jats:ext-link> (2018)], which can be explained by our present result. A characterization of integrally convex functions is also given.<\/jats:p>","DOI":"10.1051\/ro\/2019001","type":"journal-article","created":{"date-parts":[[2019,1,3]],"date-time":"2019-01-03T19:45:47Z","timestamp":1546544747000},"page":"1929-1935","source":"Crossref","is-referenced-by-count":2,"title":["Greedy systems of linear inequalities and lexicographically optimal solutions"],"prefix":"10.1051","volume":"53","author":[{"given":"Satoru","family":"Fujishige","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"250","published-online":{"date-parts":[[2019,10,28]]},"reference":[{"key":"R1","first-page":"293","volume":"74","author":"Ando","year":"1996","journal-title":"Math. Program. Ser. A"},{"key":"R2","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1016\/0012-365X(94)00246-F","volume":"148","author":"Ando","year":"1996","journal-title":"Discrete Math."},{"key":"R3","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1137\/S0895480191222926","volume":"8","author":"Bouchet","year":"1995","journal-title":"SIAM J. Discrete Math."},{"key":"R4","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1016\/0012-365X(88)90101-X","volume":"71","author":"Chandrasekaran","year":"1988","journal-title":"Discrete Math."},{"key":"R5","doi-asserted-by":"crossref","first-page":"338","DOI":"10.1007\/BF01580137","volume":"62","author":"Dunstan","year":"1973","journal-title":"Math. Program."},{"key":"R6","first-page":"3","volume":"53","author":"Favati","year":"1990","journal-title":"Ric. Oper."},{"key":"R7","unstructured":"Fujishige S., Submodular Functions and Optimization. Elsevier, North-Holland (1991)"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"Hirai H., Discrete convex functions on graphs and their algorithmic applications, edited by Fukunaga T. and Kawarabayashi K.. In: Combinatorial Optimization Graph Algorithms Springer, Singapore (2017) 67\u2013100.","DOI":"10.1007\/978-981-10-6147-9_4"},{"key":"R9","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1007\/s10107-008-0242-9","volume":"122","author":"McCormick","year":"2010","journal-title":"Math. Program. Ser. A"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"Murota K., Discrete Convex Analysis. SIAM, Philadelphia, PN (2003).","DOI":"10.1137\/1.9780898718508"},{"key":"R11","first-page":"151","volume":"1","author":"Murota","year":"2016","journal-title":"J. Mech. Inst. Des."},{"key":"R12","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1016\/S0166-218X(01)00222-0","volume":"115","author":"Murota","year":"2001","journal-title":"Discrete Appl. Math."},{"key":"R13","doi-asserted-by":"crossref","unstructured":"Murota K. and Tamura A., Integrality of subgradients and biconjugates of integrally convex functions. Preprint arXiv:1806.00992v1 (2018).","DOI":"10.1007\/s11590-019-01501-1"}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2019001\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,3,20]],"date-time":"2020-03-20T07:34:57Z","timestamp":1584689697000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2019001"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,10,28]]},"references-count":13,"journal-issue":{"issue":"5"},"alternative-id":["ro180301"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2019001","relation":{},"ISSN":["0399-0559","1290-3868"],"issn-type":[{"value":"0399-0559","type":"print"},{"value":"1290-3868","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,10,28]]}}}