Fuzzy Simultaneous Congruences

We introduce a very natural generalization of the well-known problem of simultaneous congruences. Instead of searching for a positive integer s that is specified by n fixed remainders modulo integer divisors a₁, …, a_n we consider remainder intervals R₁, …, R_n such that s is feasible if and only if s is congruent to r_i modulo a_i for some remainder r_i in interval R_i for all i. This problem is a special case of a 2-stage integer program with only two variables per constraint which is is closely related to directed Diophantine approximation as well as the mixing set problem. We give a hardness result showing that the problem is NP-hard in general. By investigating the case of harmonic divisors, i. e. a_{i+1}/a_i is an integer for all i < n, which was heavily studied for the mixing set problem as well, we also answer a recent algorithmic question from the field of real-time systems. We present an algorithm to decide the feasibility of an instance in time 𝒪(n²) and we show that if it exists even the smallest feasible solution can be computed in strongly polynomial time 𝒪(n³).

Authors

• Max A. Deppert
• Klaus Jansen
• Kim-Manuel Klein

Keywords

• Simultaneous congruences
• Integer programming
• Mixing Set
• Real-time scheduling
• Diophantine approximation