共查询到20条相似文献,搜索用时 31 毫秒
1.
Joshua N. Cooper Robert B. Ellis Andrew B. Kahng 《Journal of Combinatorial Theory, Series A》2002,100(2):232
An asymmetric binary covering code of length n and radius R is a subset
of the n-cube Qn such that every vector xQn can be obtained from some vector c
by changing at most R 1's of c to 0's, where R is as small as possible. K+(n,R) is defined as the smallest size of such a code. We show K+(n,R)Θ(2n/nR) for constant R, using an asymmetric sphere-covering bound and probabilistic methods. We show K+(n,n−
)=
+1 for constant coradius
iff n
(
+1)/2. These two results are extended to near-constant R and
, respectively. Various bounds on K+ are given in terms of the total number of 0's or 1's in a minimal code. The dimension of a minimal asymmetric linear binary code ([n,R]+-code) is determined to be min{0,n−R}. We conclude by discussing open problems and techniques to compute explicit values for K+, giving a table of best-known bounds. 相似文献
2.
Let n and k be positive integers. Let Cq be a cyclic group of order q. A cyclic difference packing (covering) array, or a CDPA(k, n; q) (CDCA(k, n; q)), is a k × n array (aij) with entries aij (0 ≤ i ≤ k−1, 0 ≤ j ≤ n−1) from Cq such that, for any two rows t and h (0 ≤ t < h ≤ k−1), every element of Cq occurs in the difference list
at most (at least) once. When q is even, then n ≤ q−1 if a CDPA(k, n; q) with k ≥ 3 exists, and n ≥ q+1 if a CDCA(k, n; q) with k ≥ 3 exists. It is proved that a CDCA(4, q+1; q) exists for any even positive integers, and so does a CDPA(4, q−1; q) or a CDPA(4, q−2; q). The result is established, for the most part, by means of a result on cyclic difference matrices with one hole, which is of interest in its own right. 相似文献
3.
On the way of generalizing recent results by Cock and the second author, it is shown that when the basis q is odd, BCH codes can be lengthened to obtain new codes with covering radius R=2. These constructions (together with a lengthening construction by the first author) give new infinite families of linear covering codes with codimension r=2k+1 (the case q=3, r=4k+1 was considered earlier). New code families with r=4k are also obtained. An updated table of upper bounds on the length function for linear codes with 24, R=2, and q=3,5 is given. 相似文献
4.
An updated table of K2,3(b,t;R)—the minimum cardinality of a code with b binary coordinates, t ternary coordinates, and covering radius R—is presented for b + t ≤ 13, R ≤ 3. The results include new explanations of short binary and ternary covering codes, several new constructions and codes, and a general lower bound for R = 1. © 2004 Wiley Periodicals, Inc. 相似文献
5.
The minimal cardinality of a q-ary code of length n and covering radius at most R is denoted by Kq(n, R); if we have the additional requirement that the minimum distance be at least d, it is denoted by Kq(n, R, d). Obviously, Kq(n, R, d) Kq(n, R). In this paper, we study instances for which Kq(n,1,2) > Kq(n, 1) and, in particular, determine K4(4,1,2)=28 > 24=K4(4,1).Supported in part by the Academy of Finland under grant 100500. 相似文献
6.
William D. Weakley 《组合设计杂志》2006,14(1):1-13
The minimum size of a binary covering code of length n and covering radius r is denoted by K(n,r), and codes of this length are called optimal. For j > 0 and n = 2j, it is known that K(n,1) = 2 · K(n?1,1) = 2n ? j. Say that two binary words of length n form a duo if the Hamming distance between them is 1 or 2. In this paper, it is shown that each optimal binary covering code of length n = 2j, j > 0, and covering radius 1 is the union of duos in just one way, and that the closed neighborhoods of the duos form a tiling of the set of binary words of length n. Methods of constructing such optimal codes from optimal covering codes of length n ? 1 (that is, perfect single‐error‐correcting codes) are discussed. The paper ends with the construction of an optimal covering code of length 16 that does not contain an extension of any optimal covering code of length 15. © 2005 Wiley Periodicals, Inc. J Combin Designs 相似文献
7.
We prove that there does not exist a [q4+q3−q2−3q−1, 5, q4−2q2−2q+1]q code over the finite field
for q≥ 5. Using this, we prove that there does not exist a [gq(5, d), 5, d]q code with q4 −2q2 −2q +1 ≤ d ≤ q4 −2q2 −q for q≥ 5, where gq(k,d) denotes the Griesmer bound.MSC 2000: 94B65, 94B05, 51E20, 05B25 相似文献
8.
We show that the covering radius R of an [n,k,d] code over Fq is bounded above by R n-n
q(k, d/q). We strengthen this bound when R d and find conditions under which equality holds.As applications of this and other bounds, we show that all binary linear codes of lengths up to 15, or codimension up to 9, are normal. We also establish the normality of most codes of length 16 and many of codimension 10. These results have applications in the construction of codes that attain t[n,k,/it>], the smallest covering radius of any binary linear [n,k].We also prove some new results on the amalgamated direct sum (ADS) construction of Graham and Sloane. We find new conditions assuring normality of the ADS; covering radius 1 less than previously guaranteed for ADS of codes with even norms; good covering codes as ADS without the hypothesis of normality, from concepts p- stable and s- stable; codes with best known covering radii as ADS of two, often cyclic, codes (thus retaining structure so as to be suitable for practical applications). 相似文献
9.
Carlos Mendes 《Discrete Applied Mathematics》2010,158(5):522-326
Given a prime power q, cq(n,R) denotes the minimum cardinality of a subset H in such that every word in this space differs in at most R coordinates from a multiple of a vector in H. In this work, two new classes of short coverings are established. As an application, a new optimal record-breaking result on the classical covering code is obtained by using short covering. We also reformulate the numbers cq(n,R) in terms of dominating set on graphs. Departing from this reformulation, the reactive tabu search (a variation of tabu search heuristics) is developed to obtain new upper bounds on cq(n,R). The algorithm is described and conclusions on the results are drawn; they identify the advantages of using the reactive mechanism for this problem. Tables of lower and upper bounds on cq(n,R), q=3,4, n≤7, and R≤3, are also presented. 相似文献
10.
The shortest possible length of a q-ary linear code of covering radius R and codimension r is called the length function and is denoted by ℓ
q
(r, R). Constructions of codes with covering radius 3 are here developed, which improve best known upper bounds on ℓ
q
(r, 3). General constructions are given and upper bounds on ℓ
q
(r, 3) for q = 3, 4, 5, 7 and r ≤ 24 are tabulated. 相似文献
11.
R 《Journal of Approximation Theory》1993,74(3)
In this paper, we determine the exact value of average n − K width
n(Wrpq(R), Lq(R)) of Sobolev-Wiener class Wrpq(R) in the metric Lq(R) for 1 > q ≥ p > ∞ and get the value of
n(Wrp(R), Lqp(R)) for the dual case. We also solve the optimal interpolation problems of Wrpq(R) in the metric Lq(R) and Wrp(R) in the metric Lqp(R) for 1 < q ≤ p < ∞. 相似文献
12.
The minimum size of a binary covering code of length n and covering radius r is denoted by K (n, r) and corresponding codes are called optimal. In this article a classification up to equivalence of all optimal covering codes having either length at most 8 or cardinality at most 4 is completed. Moreover, we prove that K (9, 2) = 16. © 2000 John Wiley & Sons, Inc. J Combin Designs 8: 391–401, 2000 相似文献
13.
O. N. Kosukhin 《Mathematical Notes》2005,77(5-6):794-808
As proved by Hilbert, it is, in principle, possible to construct an arbitrarily close approximation in the Hausdorff metric to an arbitrary closed Jordan curve Γ in the complex plane {z} by lemniscates generated by polynomials P(z). In the present paper, we obtain quantitative upper bounds for the least deviations H
n
(Γ) (in this metric) from the curve Γ of the lemniscates generated by polynomials of a given degree n in terms of the moduli of continuity of the conformal mapping of the exterior of Γ onto the exterior of the unit circle, of the mapping inverse to it, and of the Green function with a pole at infinity for the exterior of Γ. For the case in which the curve Γ is analytic, we prove that H
n
(Γ) = O(q
n
), 0 ≤ q = q(Γ) < 1, n → ∞.__________Translated from Matematicheskie Zametki, vol. 77, no. 6, 2005, pp. 861–876.Original Russian Text Copyright ©2005 by O. N. Kosukhin. 相似文献
14.
Greedily Finding a Dense Subgraph 总被引:3,自引:0,他引:3
Yuichi Asahiro Kazuo Iwama Hisao Tamaki Takeshi Tokuyama 《Journal of Algorithms in Cognition, Informatics and Logic》2000,34(2):203
Given an n-vertex graph with nonnegative edge weights and a positive integer k ≤ n, our goal is to find a k-vertex subgraph with the maximum weight. We study the following greedy algorithm for this problem: repeatedly remove a vertex with the minimum weighted-degree in the currently remaining graph, until exactly k vertices are left. We derive tight bounds on the worst case approximation ratio R of this greedy algorithm: (1/2 + n/2k)2 − O(n − 1/3) ≤ R ≤ (1/2 + n/2k)2 + O(1/n) for k in the range n/3 ≤ k ≤ n and 2(n/k − 1) − O(1/k) ≤ R ≤ 2(n/k − 1) + O(n/k2) for k < n/3. For k = n/2, for example, these bounds are 9/4 ± O(1/n), improving on naive lower and upper bounds of 2 and 4, respectively. The upper bound for general k compares well with currently the best (and much more complicated) approximation algorithm based on semidefinite programming. 相似文献
15.
Let K(n,r) denote the minimum cardinality of a binary covering code of length n and covering radius r. Constructions of covering codes give upper bounds on K(n,r). It is here shown how computer searches for covering codes can be sped up by requiring that the code has a given (not necessarily full) automorphism group. Tabu search is used to find orbits of words that lead to a covering. In particular, a code D found which proves K(13,1) 704, a new record. A direct construction of D given, and its full automorphism group is shown to be the general linear group GL(3,3). It is proved that D is a perfect dominating set (each word not in D is covered by exactly one word in D) and is a counterexample to the recent Uniformity Conjecture of Weichsel. 相似文献
16.
Let D = {B1, B2,…, Bb} be a finite family of k-subsets (called blocks ) of a v-set X(v) = {1, 2,…, v} (with elements called points ). Then D is a (v, k, t) covering design or covering if every t-subset of X(v) is contained in at least one block of D. The number of blocks, b, is the size of the covering, and the minimum size of the covering is called the covering number , denoted C(v, k, t). This article is concerned with new constructions of coverings. The constructions improve many upper bounds on the covering number C(v, k, t) © 1998 John Wiley & Sons, Inc. J Combin Designs 6:21–41, 1998 相似文献
17.
Let p and q be two permutations over {1, 2,…, n}. We denote by m(p, q) the number of integers i, 1 ≤ i ≤ n, such that p(i) = q(i). For each fixed permutation p, a query is a permutation q of the same size and the answer a(q) to this query is m(p, q). We investigate the problem of finding the minimum number of queries required to identify an unknown permutation p. A polynomial-time algorithm that identifies a permutation of size n by O(n · log2n) queries is presented. The lower bound of this problem is also considered. It is proved that the problem of determining the size of the search space created by a given set of queries and answers is #P-complete. Since this counting problem is essential for the analysis of the lower bound, a complete analysis of the lower bound appears infeasible. We conjecture, based on some preliminary analysis, that the lower bound is Ω(n · log2n). 相似文献
18.
Let D(G) be the minimum quantifier depth of a first order sentence Φ that defines a graph G up to isomorphism. Let D0(G) be the version of D(G) where we do not allow quantifier alternations in Φ. Define q0(n) to be the minimum of D0(G) over all graphs G of order n.We prove that for all n we have
log*n−log*log*n−2≤q0(n)≤log*n+22,