Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAn Improved Linear Programming Bound on the Average Distance of a Binary Code
172
0
0.0
(
0
)
Added by
Lei Yu
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Ahlswede and Katona (1977) posed the following isodiametric problem in Hamming spaces: For every $n$ and $1le Mle2^{n}$, determine the minimum average Hamming distance of binary codes with length $n$ and size $M$. Fu, Wei, and Yeung (2001) used linear programming duality to derive a lower bound on the minimum average distance. However, their linear programming approach was not completely exploited. In this paper, we improve Fu-Wei-Yeungs bound by finding a better feasible solution to their dual program. For fixed $0<ale1/2$ and for $M=leftlceil a2^{n}rightrceil $, our feasible solution attains the asymptotically optimal value of Fu-Wei-Yeungs dual program as $ntoinfty$. Hence for $0<ale1/2$, all possible asymptotic bounds that can be derived by Fu-Wei-Yeungs linear program have been characterized. Furthermore, noting that the average distance of a code is closely related to weights of Fourier coefficients of a Boolean function, we also apply the linear programming technique to prove bounds on Fourier weights of a Boolean function of various degrees.
rate research
Read More
$H_q(n,d)$ is defined as the graph with vertex set ${mathbb Z}_q^n$ and where two vertices are adjacent if their Hamming distance is at least $d$. The chromatic number of these graphs is presented for various sets of parameters $(q,n,d)$. For the $4$-colorings of the graphs $H_2(n,n-1)$ a notion of robustness is introduced. It is based on the tolerance of swapping colors along an edge without destroying properness of the coloring. An explicit description of the maximally robust $4$-colorings of $H_2(n,n-1)$ is presented.
The determination of the weight distribution of linear codes has been a fascinating problem since the very beginning of coding theory. There has been a lot of research on weight enumerators of special cases, such as self-dual codes and codes with small Singletons defect. We propose a new set of linear relations that must be satisfied by the coefficients of the weight distribution. From these relations we are able to derive known identities (in an easier way) for interesting cases, such as extremal codes, Hermitian codes, MDS and NMDS codes. Moreover, we are able to present for the first time the weight distribution of AMDS codes. We also discuss the link between our results and the Pless equations.
We show that every cubic bridgeless graph with n vertices has at least 3n/4-10 perfect matchings. This is the first bound that differs by more than a constant from the maximal dimension of the perfect matching polytope.
For a graph $G= (V,E)$, a double Roman dominating function (DRDF) is a function $f : V to {0,1,2,3}$ having the property that if $f (v) = 0$, then vertex $v$ must have at least two neighbors assigned $2$ under $f$ or {at least} one neighbor $u$ with $f (u) = 3$, and if $f (v) = 1$, then vertex $v$ must have at least one neighbor $u$ with $f (u) ge 2$. In this paper, we consider the double Roman domination problem, which is an optimization problem of finding the DRDF $f$ such that $sum_{vin V} f (v)$ is minimum. We propose {five integer linear programming (ILP) formulations and one mixed integer linear programming formulation with polynomial number of constraints for this problem. Some additional valid inequalities and bounds are also proposed for some of these formulations.} Further, we prove that {the first four models indeed solve the double Roman domination problem, and the last two models} are equivalent to the others regardless of the variable relaxation or usage of a smaller number of constraints and variables. Additionally, we use one ILP formulation to give an $H(2(Delta+1))$-approximation algorithm. All proposed formulations and approximation algorithm are evaluated on randomly generated graphs to compare the performance.
Let $mathcal{H}$ be a $t$-regular hypergraph on $n$ vertices and $m$ edges. Let $M$ be the $m times n$ incidence matrix of $mathcal{H}$ and let us denote $lambda =max_{v perp overline{1},|v| = 1}|Mv|$. We show that the discrepancy of $mathcal{H}$ is $O(sqrt{t} + lambda)$. As a corollary, this gives us that for every $t$, the discrepancy of a random $t$-regular hypergraph with $n$ vertices and $m geq n$ edges is almost surely $O(sqrt{t})$ as $n$ grows. The proof also gives a polynomial time algorithm that takes a hypergraph as input and outputs a coloring with the above guarantee.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
