4 papers · 1 filter
Decreasing Minimization on Base-Polyhedra: Relation Between Discrete and Continuous Cases
András Frank, Kazuo Murota
This paper is concerned with the relationship between the discrete and the continuous decreasing minimization problem on base-polyhedra. The continuous version (under the name of l…
A Discrete Convex Min-Max Formula for Box-TDI Polyhedra
András Frank, Kazuo Murota
A min-max formula is proved for the minimum of an integer-valued separable discrete convex function where the minimum is taken over the set of integral elements of a box total dual…
Discrete Decreasing Minimization, Part II: Views from Discrete Convex Analysis
András Frank, Kazuo Murota
We continue to consider the discrete decreasing minimization problem on an integral base-polyhedron treated in Part I. The problem is to find a lexicographically minimal integral v…
Discrete Decreasing Minimization, Part I: Base-polyhedra with Applications in Network Optimization
András Frank, Kazuo Murota
Borradaile et al. (2017) investigated orientations of an undirected graph in which the sequence of in-degrees of the nodes is lexicographically minimal, which we call decreasingly…