We consider the problem of constructing prefix-free codes in which a designated symbol, a
, can only appear at the end of codewords. We provide a linear-time algorithm to construct
-optimal codes ...with this property, meaning that their average length differs from the
by at most one. We obtain our results by uncovering a relation between our class of codes and the class of one-to-one codes. Additionally, we derive upper and lower bounds to the average length of optimal prefix-free codes with a space in terms of the source entropy.
A (k,n)-superimposed code is a well known and widely used combinatorial structure that can be represented by a t×n binary matrix such that for any k columns of the matrix and for any column c chosen ...among these k columns, there exists a row in correspondence of which column c has an entry equal to 1 and the remaining k−1 columns have entries equal to 0. Due to the many situations in which superimposed codes find applications, there is an abundant literature that studies the problem of constructing (k,n)-superimposed codes with a small number t of rows. Motivated by applications to conflict-free communication in multiple-access networks, group testing, and data security, we study the problem of constructing superimposed codes that have the additional constraints that the number of 1's in each column of the matrix is constant, and equal to an input parameter w. Our results improve on the known literature in the area. We also extend our findings to other important combinatorial structures, like selectors, generalized superimposed codes, and z-error correcting superimposed codes.
In this paper, we introduced novel characterizations of the classical concept of majorization in terms of upper triangular (resp., lower triangular) row-stochastic matrices, and in terms of sequences ...of linear transforms on vectors. We use our new characterizations of majorization to derive an improved entropy inequality.
Motivated by applications in sociology, economy and medicine, we study variants of the Target Set Selection problem, first proposed by Kempe, Kleinberg and Tardos. In our scenario one is given a ...graph G=(V,E), integer values t(v) for each vertex v (thresholds), and the objective is to determine a small set of vertices (target set) that activates a given number (or a given subset) of vertices of G within a prescribed number of rounds. The activation process in G proceeds as follows: initially, at round 0, all vertices in the target set are activated; subsequently at each round r⩾1 every vertex of G becomes activated if at least t(v) of its neighbors are already active by round r−1. It is known that the problem of finding a minimum cardinality Target Set that eventually activates the whole graph G is hard to approximate to a factor better than O(2log1−ϵ|V|). In this paper we give exact polynomial time algorithms to find minimum cardinality Target Sets in graphs of bounded clique-width, and exact linear time algorithms for trees.
We consider two graph optimization problems called vector domination and total vector domination. In vector domination one seeks a small subset S of vertices of a graph such that any vertex outside S ...has a prescribed number of neighbors in S. In total vector domination, the requirement is extended to all vertices of the graph. We prove that these problems (and several variants thereof) cannot be approximated to within a factor of clnn, where c is a suitable constant and n is the number of the vertices, unless P=NP. We also show that two natural greedy strategies have approximation factors lnΔ+O(1), where Δ is the maximum degree of the input graph. We also provide exact polynomial time algorithms for several classes of graphs. Our results extend, improve, and unify several results previously known in the literature.
List union-free families are basic combinatorial structures that appear in different application scenarios, most notably in one-bit compressed sensing. In this paper, we study algorithms for the ...construction of list union-free families and we provide bounds on the parameters of these families that substantially affect the complexity of the algorithms that utilize them.
Group testing refers to the situation in which one is given a set of objects ${\cal O}$, an unknown subset ${\cal P}\subseteq {\cal O}$, and the task of determining ${\cal P}$ by asking queries of ...the type "does ${\cal P}$ intersect $\cal Q$?," where $\cal Q$ is a subset of ${\cal O}$. Group testing is a basic search paradigm that occurs in a variety of situations such as quality control testing, searching in storage systems, multiple access communications, and data compression, among others. Group testing procedures have been recently applied in computational molecular biology, where they are used for screening libraries of clones with hybridization probes and sequencing by hybridization. Motivated by particular features of group testing algorithms used in biological screening, we study the efficiency of two-stage group testing procedures. Our main result is the first optimal two-stage algorithm that uses a number of tests of the same order as the information-theoretic lower bound on the problem. We also provide efficient algorithms for the case in which there is a Bernoulli probability distribution on the possible sets ${\cal P}$, and an optimal algorithm for the case in which the outcome of tests may be unreliable because of the presence of "inhibitory" items in ${\cal O}$. Our results depend on a combinatorial structure introduced in this paper. We believe that it will prove useful in other contexts, too.
We introduce a class of generalized superimposed codes that include several cases already studied in the literature. We give bounds on their size and algorithms for their construction.
•We introduce ...a generalization of superimposed codes that includes combinatorial structures already studied in the literature.•We give algorithms for their constructions.•We give bounds on their lengths (the relevant parameter in the application scenarios where superimposed codes are used).•We show that our results improve, on several respects, previously known results.
Given two discrete random variables <inline-formula> <tex-math notation="LaTeX">X </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">Y </tex-math></inline-formula>, with ...probability distributions <inline-formula> <tex-math notation="LaTeX">p=(p_{1}, \ldots , p_{n}) </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">q=(q_{1}, \ldots , q_{m}) </tex-math></inline-formula>, respectively, let us denote by <inline-formula> <tex-math notation="LaTeX">{\mathcal{ C}}(p, q) </tex-math></inline-formula> the set of all couplings of <inline-formula> <tex-math notation="LaTeX">p </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">q </tex-math></inline-formula>, that is, the set of all bivariate probability distributions that have <inline-formula> <tex-math notation="LaTeX">p </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">q </tex-math></inline-formula> as marginals. In this paper, we study the problem of finding a joint probability distribution in <inline-formula> <tex-math notation="LaTeX">{\mathcal{ C}}(p, q) </tex-math></inline-formula> of minimum entropy (equivalently, a coupling that maximizes the mutual information between <inline-formula> <tex-math notation="LaTeX">X </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">Y </tex-math></inline-formula>), and we discuss several situations where the need for this kind of optimization naturally arises. Since the optimization problem is known to be NP-hard, we give an efficient algorithm to find a joint probability distribution in <inline-formula> <tex-math notation="LaTeX">{\mathcal{ C}}(p, q) </tex-math></inline-formula> with entropy exceeding the minimum possible at most by 1 bit, thus providing an approximation algorithm with an additive gap of at most 1 bit. Leveraging on this algorithm, we extend our result to the problem of finding a minimum-entropy joint distribution of arbitrary <inline-formula> <tex-math notation="LaTeX">k\geq {2} </tex-math></inline-formula> discrete random variables <inline-formula> <tex-math notation="LaTeX">X_{1}, \ldots , X_{k} </tex-math></inline-formula>, consistent with the known <inline-formula> <tex-math notation="LaTeX">k </tex-math></inline-formula> marginal distributions of the individual random variables <inline-formula> <tex-math notation="LaTeX">X_{1}, \ldots , X_{k} </tex-math></inline-formula>. In this case, our algorithm has an additive gap of at most <inline-formula> <tex-math notation="LaTeX">\log k </tex-math></inline-formula> from optimum. We also discuss several related applications of our findings and extensions of our results to entropies different from the Shannon entropy.
We investigate the benefits of using multiple channels in wireless networks, under the full-duplex multi-packet reception model of communication. The main question we address is the following: Is a ...speedup linear in the number of channels available, for some interesting communication primitive? We provide a positive answer to this interrogative for the Information Exchange Problem, in which up to k arbitrary nodes have information they intend to share with the entire network. In particular, we give non-adaptive deterministic protocols for both the scenario in which the channels provide the transmitting stations with the feedback on whether their transmissions have been successful and for the scenario in which channels provide no such feedback. To this aim, we devise and exploit a new combinatorial structure that generalizes well known combinatorial tools, widely used in the area of data-exchange in multiple-access channels (i.e., strongly selective families, selectors, and related mathematical objects). For our new combinatorial structures we provide both existential results and randomized algorithms to generate them. We also prove non-existence results showing that our protocol for the model with feedback is optimal, whereas that for the no-feedback scenario uses a number of time slots that exceeds the lower bound by a logk factor. Leveraging on properties of error correcting codes, we show that for an infinite set of the relevant parameters n and k, one can construct our combinatorial structure for the no-feedback scenario in polynomial time and of minimum length.
PDF
