共查询到20条相似文献,搜索用时 31 毫秒
1.
Given a “black box” function to evaluate an unknown rational polynomial
f ? \mathbbQ[x]f \in {\mathbb{Q}}[x] at points modulo a prime p, we exhibit algorithms to compute the representation of the polynomial in the sparsest shifted power basis. That is, we determine
the sparsity $t \in {\mathbb{Z}}_{>0}$t \in {\mathbb{Z}}_{>0}, the shift
a ? \mathbbQ\alpha \in {\mathbb{Q}}, the exponents 0 £ e1 < e2 < ? < et{0 \leq e_{1} < e_{2} < \cdots < e_{t}}, and the coefficients
c1, ?, ct ? \mathbbQ \{0}c_{1}, \ldots , c_{t} \in {\mathbb{Q}} \setminus \{0\} such that
f(x) = c1(x-a)e1+c2(x-a)e2+ ?+ct(x-a)etf(x) = c_{1}(x-\alpha)^{e_{1}}+c_{2}(x-\alpha)^{e_{2}}+ \cdots +c_{t}(x-\alpha)^{e_{t}} 相似文献
2.
In classical constraint satisfaction, redundant modeling has been shown effective in increasing constraint propagation and
reducing search space for many problem instances. In this paper, we investigate, for the first time, how to benefit the same
from redundant modeling in weighted constraint satisfaction problems (WCSPs), a common soft constraint framework for modeling optimization and over-constrained problems. Our work focuses on
a popular and special class of problems, namely, permutation problems. First, we show how to automatically generate a redundant permutation WCSP model from an existing permutation WCSP using
generalized model induction. We then uncover why naively combining mutually redundant permutation WCSPs by posting channeling constraints as hard constraints
and relying on the standard node consistency (NC*) and arc consistency (AC*) algorithms would miss pruning opportunities, which are available even in a single model. Based on these observations,
we suggest two approaches to handle the combined WCSP models. In our first approach, we propose
m\text -NC\text c*m\text {-NC}_{\text c}^* and
m\text -AC\text c*m\text {-AC}_{\text c}^* and their associated algorithms for effectively enforcing node and arc consistencies in a combined model with m sub-models. The two notions are strictly stronger than NC* and AC* respectively. While the first approach specifically refines
NC* and AC* so as to apply to combined models, in our second approach, we propose a parameterized local consistency LB(m,Φ). The consistency can be instantiated with any local consistency Φ for single models and applied to a combined model with m sub-models. We also provide a simple algorithm to enforce LB(m,Φ). With the two suggested approaches, we demonstrate their applicabilities on several permutation problems in the experiments.
Prototype implementations of our proposed algorithms confirm that applying
2\text -NC\text c*, 2\text -AC\text c*2\text {-NC}_{\text c}^*,\;2\text {-AC}_{\text c}^*, and LB(2,Φ) on combined models allow far more constraint propagation than applying the state-of-the-art AC*, FDAC*, and
EDAC* algorithms on single models of hard benchmark problems. 相似文献
3.
Fast Algorithms for the Density Finding Problem 总被引:1,自引:0,他引:1
We study the problem of finding a specific density subsequence of a sequence arising from the analysis of biomolecular sequences.
Given a sequence A=(a
1,w
1),(a
2,w
2),…,(a
n
,w
n
) of n ordered pairs (a
i
,w
i
) of numbers a
i
and width w
i
>0 for each 1≤i≤n, two nonnegative numbers ℓ, u with ℓ≤u and a number δ, the Density Finding Problem is to find the consecutive subsequence A(i
*,j
*) over all O(n
2) consecutive subsequences A(i,j) with width constraint satisfying ℓ≤w(i,j)=∑
r=i
j
w
r
≤u such that its density
is closest to δ. The extensively studied Maximum-Density Segment Problem is a special case of the Density Finding Problem with δ=∞. We show that the Density Finding Problem has a lower bound Ω(nlog n) in the algebraic decision tree model of computation. We give an algorithm for the Density Finding Problem that runs in optimal O(nlog n) time and O(nlog n) space for the case when there is no upper bound on the width of the sequence, i.e., u=w(1,n). For the general case, we give an algorithm that runs in O(nlog 2
m) time and O(n+mlog m) space, where
and w
min=min
r=1
n
w
r
. As a byproduct, we give another O(n) time and space algorithm for the Maximum-Density Segment Problem.
Grants NSC95-2221-E-001-016-MY3, NSC-94-2422-H-001-0001, and NSC-95-2752-E-002-005-PAE, and by the Taiwan Information Security
Center (TWISC) under the Grants NSC NSC95-2218-E-001-001, NSC95-3114-P-001-002-Y, NSC94-3114-P-001-003-Y and NSC 94-3114-P-011-001. 相似文献
4.
Alexander A. Sherstov 《Computational Complexity》2010,19(1):135-150
We solve an open problem in communication complexity posed by Kushilevitz and Nisan (1997). Let R∈(f) and $D^\mu_\in
(f)$D^\mu_\in
(f) denote the randomized and μ-distributional communication complexities of f, respectively (∈ a small constant). Yao’s well-known minimax principle states that $R_{\in}(f) = max_\mu
\{D^\mu_\in(f)\}$R_{\in}(f) = max_\mu
\{D^\mu_\in(f)\}. Kushilevitz and Nisan (1997) ask whether this equality is approximately preserved if the maximum is taken over product distributions
only, rather than all distributions μ. We give a strong negative answer to this question. Specifically, we prove the existence
of a function f : {0, 1}n ×{0, 1}n ? {0, 1}f : \{0, 1\}^n \times \{0, 1\}^n \rightarrow \{0, 1\} for which maxμ product {Dm ? (f)} = Q(1) but R ? (f) = Q(n)\{D^\mu_\in (f)\} = \Theta(1) \,{\textrm but}\, R_{\in} (f) = \Theta(n). We also obtain an exponential separation between the statistical query dimension and signrank, solving a problem previously
posed by the author (2007). 相似文献
5.
Given an alphabet Σ={1,2,…,|Σ|} text string T∈Σ
n
and a pattern string P∈Σ
m
, for each i=1,2,…,n−m+1 define L
p
(i) as the p-norm distance when the pattern is aligned below the text and starts at position i of the text. The problem of pattern matching with L
p
distance is to compute L
p
(i) for every i=1,2,…,n−m+1. We discuss the problem for d=1,2,∞. First, in the case of L
1 matching (pattern matching with an L
1 distance) we show a reduction of the string matching with mismatches problem to the L
1 matching problem and we present an algorithm that approximates the L
1 matching up to a factor of 1+ε, which has an
O(\frac1e2nlogmlog|S|)O(\frac{1}{\varepsilon^{2}}n\log m\log|\Sigma|)
run time. Then, the L
2 matching problem (pattern matching with an L
2 distance) is solved with a simple O(nlog m) time algorithm. Finally, we provide an algorithm that approximates the L
∞ matching up to a factor of 1+ε with a run time of
O(\frac1enlogmlog|S|)O(\frac{1}{\varepsilon}n\log m\log|\Sigma|)
. We also generalize the problem of String Matching with mismatches to have weighted mismatches and present an O(nlog 4
m) algorithm that approximates the results of this problem up to a factor of O(log m) in the case that the weight function is a metric. 相似文献
6.
We study the classical approximate string matching problem, that is, given strings P and Q and an error threshold k, find all ending positions of substrings of Q whose edit distance to P is at most k. Let P and Q have lengths m and n, respectively. On a standard unit-cost word RAM with word size w≥log n we present an algorithm using time
|
设为首页 | 免责声明 | 关于勤云 | 加入收藏 |
Copyright©北京勤云科技发展有限公司 京ICP备09084417号-23 |