Optimization Online


Greedy Systems of Linear Inequalities and Lexicographically Optimal Solutions

Satoru Fujishige (fujishig***at***kurims.kyoto-u.ac.jp)

Abstract: 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 K. Murota and A. 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 P. Favati and F. Tardella (K. Murota and A. Tamura: Integrality of subgradients and biconjugates of integrally convex functions. arXiv:1806.00992v1 [math.CO] 4 June 2018; revised, 7 September 2018), which can also be explained by our present result.

Keywords: Greedy system, lexicographic optimality, discrete convexity

Category 1: Combinatorial Optimization

Citation: RAIRO-OR https://doi.org/10.1051/ro/2019001

Download: [PDF]

Entry Submitted: 09/25/2018
Entry Accepted: 09/27/2018
Entry Last Modified: 05/19/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society