论文标题
模糊的同时赋予一致性
Fuzzy Simultaneous Congruences
论文作者
论文摘要
我们介绍了众所周知的同时一致性问题的非常自然的概括。 Instead of searching for a positive integer $s$ that is specified by $n$ fixed remainders modulo integer divisors $a_1,\dots,a_n$ we consider remainder intervals $R_1,\dots,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所有$ i $ $ r_i $。 这个问题是一个2阶段整数程序的特殊情况，每个约束只有两个变量，这与有向的二磷酸近似以及混合集问题密切相关。我们给出了硬度结果，表明问题通常是NP-HARD。 通过调查谐波除数的案例，即$ a_ {i+1}/a_i $是所有$ i <n $的整数，这也对混合集问题进行了大量研究，我们还回答了实时系统中最近的算法问题。我们提出了一种算法来确定实例$ \ MATHCAL {O}（n^2）$的可行性，并且我们表明，如果它存在，即使是最小的可行解决方案也可以在强烈多项式时间$ \ MATHCAL {O}（O}（O}（o}（n^3））中。
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_1,\dots,a_n$ we consider remainder intervals $R_1,\dots,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 $\mathcal{O}(n^2)$ and we show that if it exists even the smallest feasible solution can be computed in strongly polynomial time $\mathcal{O}(n^3)$.
