On discrete optimization with ordering

Resumen

This paper studies discrete optimization problems with ordering requirements. These problems are formulated on general discrete sets in which there exist an implicit ordering on their elements together with a cost function that evaluates each element of a given subset depending on its ordering relative to the remaining elements in the set. It is proven that ordered sequences over the original set dene an independence system. The simplest such ordering problem, that consists of nding the ordered sequence of maximum weight, and its restriction to sets of a xed cardinality are studied. Ordering problems on the intersection of two independence systems, being one of them that associated with the ordering, are also addressed, both with and without cardinality constraint. Finally, it is proven that the greedy algorithm optimally solves a particular important case, namely the Ordered Median Spanning Tree Problem, even if feasible solutions do not dene a matroid structure.