Deppert, Max A. ;
Jansen, Klaus ;
Klein, KimManuel
Fuzzy Simultaneous Congruences
Abstract
We introduce a very natural generalization of the wellknown 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 2stage 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 NPhard 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 realtime 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³).
BibTeX  Entry
@InProceedings{deppert_et_al:LIPIcs.MFCS.2021.39,
author = {Deppert, Max A. and Jansen, Klaus and Klein, KimManuel},
title = {{Fuzzy Simultaneous Congruences}},
booktitle = {46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
pages = {39:139:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772013},
ISSN = {18688969},
year = {2021},
volume = {202},
editor = {Bonchi, Filippo and Puglisi, Simon J.},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14479},
URN = {urn:nbn:de:0030drops144792},
doi = {10.4230/LIPIcs.MFCS.2021.39},
annote = {Keywords: Simultaneous congruences, Integer programming, Mixing Set, Realtime scheduling, Diophantine approximation}
}
18.08.2021
Keywords: 

Simultaneous congruences, Integer programming, Mixing Set, Realtime scheduling, Diophantine approximation 
Seminar: 

46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

Issue date: 

2021 
Date of publication: 

18.08.2021 