2026-07-25T09:02:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14479 2024-03-06T10:54:07Z ddc:004 open_access

Fuzzy Simultaneous Congruences Deppert, Max A. Jansen, Klaus Klein, Kim-Manuel Simultaneous congruences Integer programming Mixing Set Real-time scheduling Diophantine approximation 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³). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Max A. Deppert and Klaus Jansen and Kim-Manuel Klein 2021 Is Part Of LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2021.39 urn:nbn:de:0030-drops-144792 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.39 eng https://creativecommons.org/licenses/by/4.0/legalcode