Convex dynamics: unavoidable difficulties in bounding some greedy algorithms.

Abstract

A greedy algorithm for scheduling and digital printing with inputs in a convex polytope, and vertices of this polytope as successive outputs, has recently been proven to be bounded for any convex polytope in any dimension. This boundedness property follows readily from the existence of some invariant region for a dynamical system equivalent to the algorithm, which is what one proves. While the proof, and some constructions of invariant regions that can be made to depend on a single parameter, are reasonably simple for convex polygons in the plane, the proof of boundedness gets quite complicated in dimension three and above. We show here that such complexity is somehow justified by proving that the most natural generalization of the construction that works for polygons does not work in any dimension above two, even if we allow for as many parameters as there are faces. We first prove that some polytopes in dimension greater than two admit no invariant region to which they are combinatorially equivalent. We then modify these examples to get polytopes such that no invariant region can be obtained by pushing out the borders of the half spaces that intersect to form the polytope. We also show that another mechanism prevents some simplices (the simplest polytopes in any dimension) from admitting invariant regions to which they would be similar. By contrast in dimension two, one can always get an invariant region by pushing these borders far enough in some correlated way; for instance, pushing all borders by the same distance builds an invariant region for any polygon if the push is at a distance big enough for that polygon. To motivate the examples that we provide, we discuss briefly the bifurcations of polyhedra associated with pushing half spaces in parallel to themselves. In dimension three, the elementary codimension one bifurcation resembles the unfolding of the elementary degenerate singularity for codimension one foliations on surfaces. As the subject of this paper is new for the communities most interested in Chaos, we take some care in describing various links of our problem to classical issues (in particular linked to Diophantine approximation) as well as to various technological or commercial issues, exemplified, respectively, by digital printing and a problem in scheduling.