^{1}

### Abstract

We discuss the greedy algorithm for approximating a sequence of inputs in a family of polytopes lying in affine spaces by an output sequence made of vertices of the respective polytopes. More precisely, we consider here the case when the greed of the algorithm is dictated by the Euclidean norms of the successive cumulative errors. This algorithm can be interpreted as a time-dependent dynamical system in the vector space, where the errors live, or as a time-dependent dynamical system in an affine space containing copies of all the original polytopes. This affine space contains the inputs, as well as the inputs modified by adding the respective former errors; it is the evolution of these modified inputs that the dynamical system in affine space describes. Scheduling problems with many polytopes arise naturally, for instance, when the inputs are from a single polytope , but one imposes the constraint that whenever the input belongs to a codimension face, the output has to be in the same codimension face (as when scheduling drivers among participants of a carpool). It has been previously shown that the error is bounded in the case of a single polytope by proving the existence of an arbitrary large convex invariant region for the dynamics in affine space: A region that is simultaneously invariant for several polytopes, each considered separately, was also constructed. It was then shown that there cannot be an invariant region in affine space in the general case of a family of polytopes. Here we prove the existence of an arbitrary large convex invariant set for the dynamics in the vector space in the case when the sizes of the polytopes in the family are bounded and the set of all the outgoing normals to all the faces of all the polytopes is finite. It was also previously known that starting from zero as the initial error set, the error set could not be saturated in finitely many steps in some cases with several polytopes: Contradicting a former conjecture, we show that the same happens for some single quadrilaterals and for a single pentagon with an axial symmetry. The disproof of that conjecture is the new piece of information that leads us to expect, and then to verify, as we recount here, that the proof that the errors are bounded in the general case could be a small step beyond the proof of the same statement for the single polytope case.

I thank Marco Martens and the referee for very valuable help in improving the manuscript. The amount of advice that was provided is undoubtedly worth the time spent waiting for it, and is indeed worth coauthorship on his paper.

I. INTRODUCTION A. Setting the stage B. Applications and roots of the problem C. The dynamical systems point of view D. Limitations of the invariant regions approach E. Formulation of the new result 1. An apparent contradiction 2. What can one expect? 3. Former instances of the general bounds? 4. Why is it good to have large bounds? 5. Formulation II. PROOF OF THE MAIN RESULT III. GETTING TO THE MINIMAL ERROR SET: EXAMPLES IN DIMENSION 2

### Key Topics

- Polytopes
- 147.0
- Set theory
- 16.0
- Diffusion
- 5.0
- Algebraic number theory
- 3.0
- Gold
- 1.0

Data & Media loading...

Article metrics loading...

Full text loading...

Commenting has been disabled for this content