Ugo Vaccaro
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Ugo Vaccaro has a total of 28 co-authors. Here are the top co-authors by number of shared publications:
- Luisa Gargano
University of Salerno
10 shared publications - Adele Anna Rescigno
University of Salerno
9 shared publications - Roberto Bruno
Department of Computer Science, University of Salerno, Fisciano, Italy
7 shared publications - Ferdinando Cicalese
Department of Computer Science, University of Verona, Verona, Italy
6 shared publications - Gennaro Cordasco
University of Salerno
4 shared publications Luisa Gargano
Dipartimento di Informatica, Università di Salerno, Fisciano, Italy
4 shared publications
Latest Publications
- Open Access
- 31 July 2026
- Published by Springer Nature in Soft Computing
- Vol. 30 (8) , 5371-5383
An information theoretic treatment of Yager’s probability distribution negation
In the seminal paper (Yager 2015), Yager defined the negation of a probability distribution $$\textbf{p}=(p_1,\dots ,p_n)$$ , as the distribution $$\overline{\textbf{p}} = (\overline{p}_1,\dots ,\overline{p}_n)$$ , where $$\overline{p}_i = ({1-p_i})/({n-1}),$$ for $$ i=1, \ldots , n.$$ In this paper, we present a comprehensive information-theoretic analysis of Yager’s negation and its generalizations. Using tools from information theory and majorization theory, we unify, extend, and strengthen a number of previously known properties of Yager’s negation within a common framework. Overall, our results offer strong theoretical justification for Yager’s negation as the most natural and principled definition of probability distribution negation under various information theoretic criteria.- 31 July 2026
- Published by Springer Nature in Soft Computing
- Vol. 30 (8) , 5371-5383
Open AccessAn information theoretic treatment of Yager’s probability distribution negation
In the seminal paper (Yager 2015), Yager defined the negation of a probability distribution $$\textbf{p}=(p_1,\dots ,p_n)$$ , as the distribution $$\overline{\textbf{p}} = (\overline{p}_1,\dots ,\overline{p}_n)$$ , where $$\overline{p}_i = ({1-p_i})/({n-1}),$$ for $$ i=1, \ldots , n.$$ In this paper, we present a comprehensive information-theoretic analysis of Yager’s negation and its generalizations. Using tools from information theory and majorization theory, we unify, extend, and strengthen a number of previously known properties of Yager’s negation within a common framework. Overall, our results offer strong theoretical justification for Yager’s negation as the most natural and principled definition of probability distribution negation under various information theoretic criteria. - 31 March 2026
- Published by Elsevier in Information Processing Letters
- Vol. 194
Optimal average-case binary search with outcome-dependent costs
- 31 March 2026
- Published by Elsevier in Information Processing Letters
- Vol. 194
Optimal average-case binary search with outcome-dependent costs
- 15 December 2025
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 72 (2) , 832-843
NP-Hardness and Approximation Algorithms for Constrained Entropy Maximization
Given a random variable X that takes values in a finite set $\mathcal {X} = \{x_{1}, \ldots, x_{n}\}$ , and a positive number R, we consider the problem of finding a deterministic function $f: \mathcal {X} \to \mathcal {Y}$ that maximizes the entropy $H(f(X))$ , while satisfying the constraint $H(f(X)) \leq R$ . This problem occurs in several contexts, including lossy compression with logarithmic loss and the well-known Deterministic Information Bottleneck problem. We prove the NP-hardness of finding the optimal solution to the above maximization problem. On the positive side, we design approximation algorithms that achieve improved approximation factors compared to existing methods in the literature.
- 15 December 2025
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 72 (2) , 832-843
NP-Hardness and Approximation Algorithms for Constrained Entropy Maximization
Given a random variable X that takes values in a finite set $\mathcal {X} = \{x_{1}, \ldots, x_{n}\}$ , and a positive number R, we consider the problem of finding a deterministic function $f: \mathcal {X} \to \mathcal {Y}$ that maximizes the entropy $H(f(X))$ , while satisfying the constraint $H(f(X)) \leq R$ . This problem occurs in several contexts, including lossy compression with logarithmic loss and the well-known Deterministic Information Bottleneck problem. We prove the NP-hardness of finding the optimal solution to the above maximization problem. On the positive side, we design approximation algorithms that achieve improved approximation factors compared to existing methods in the literature.
- Open Access
Old and New Results on Alphabetic Codes
This comprehensive survey examines the field of alphabetic codes, tracing their development from the 1960s to the present day. We explore classical alphabetic codes and their variants, analyzing their properties and the underlying mathematical and algorithmic principles. The paper covers the fundamental relationship between alphabetic codes and comparison-based search procedures and their applications in data compression, routing, and testing. We review optimal alphabetic code construction algorithms, necessary and sufficient conditions for their existence, and upper bounds on the average code length of optimal alphabetic codes. The survey also discusses variations and generalizations of the classical problem of constructing minimum average length alphabetic codes. By elucidating both classical results and recent findings, this paper aims to serve as a valuable resource for researchers and students, concluding with promising future research directions in this still-active field.
Open AccessOld and New Results on Alphabetic Codes
This comprehensive survey examines the field of alphabetic codes, tracing their development from the 1960s to the present day. We explore classical alphabetic codes and their variants, analyzing their properties and the underlying mathematical and algorithmic principles. The paper covers the fundamental relationship between alphabetic codes and comparison-based search procedures and their applications in data compression, routing, and testing. We review optimal alphabetic code construction algorithms, necessary and sufficient conditions for their existence, and upper bounds on the average code length of optimal alphabetic codes. The survey also discusses variations and generalizations of the classical problem of constructing minimum average length alphabetic codes. By elucidating both classical results and recent findings, this paper aims to serve as a valuable resource for researchers and students, concluding with promising future research directions in this still-active field.
- Open Access
Exact and Heuristic Solution Approaches for the Cluster Deletion Problem on General Graphs
A cluster graph is a disjoint union of cliques, obtained by clustering the nodes of a given network and then removing the edges between nodes assigned to different clusters. The Cluster Deletion problem asks for the smallest subset of edges to be removed from a network in order to produce a cluster graph, which is equivalent to determining the largest subset of edges to be preserved. The problem finds application in many fields, including computational biology, bioinformatics, and wireless sensor networks, and it is known to be ‐hard on general graphs. In this work, we formulate the problem as an integer linear program, and we devise a heuristic approach based on edge contraction operations. We test the proposed approaches on both artificial instances and benchmark biological networks.
Open AccessExact and Heuristic Solution Approaches for the Cluster Deletion Problem on General Graphs
A cluster graph is a disjoint union of cliques, obtained by clustering the nodes of a given network and then removing the edges between nodes assigned to different clusters. The Cluster Deletion problem asks for the smallest subset of edges to be removed from a network in order to produce a cluster graph, which is equivalent to determining the largest subset of edges to be preserved. The problem finds application in many fields, including computational biology, bioinformatics, and wireless sensor networks, and it is known to be ‐hard on general graphs. In this work, we formulate the problem as an integer linear program, and we devise a heuristic approach based on edge contraction operations. We test the proposed approaches on both artificial instances and benchmark biological networks.
- 13 September 2024
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 360, 181-187
An efficient algorithm for group testing with runlength constraints
- 13 September 2024
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 360, 181-187
An efficient algorithm for group testing with runlength constraints
- Open Access
An Efficient Algorithm for Group Testing with Runlength Constraints
In this paper, we provide an efficient algorithm to construct almost optimal $(k,n,d)$-superimposed codes with runlength constraints. A $(k,n,d)$-superimposed code of length $t$ is a $t \times n$ binary matrix such that any two 1's in each column are separated by a run of at least $d$ 0's, and such that for any column $\mathbf{c}$ and any other $k-1$ columns, there exists a row where $\mathbf{c}$ has $1$ and all the remaining $k-1$ columns have $0$. These combinatorial structures were introduced by Agarwal et al. [1], in the context of Non-Adaptive Group Testing algorithms with runlength constraints. By using Moser and Tardos' constructive version of the Lovász Local Lemma, we provide an efficient randomized Las Vegas algorithm of complexity $Θ(t n^2)$ for the construction of $(k,n,d)$-superimposed codes of length $t=O(dk\log n +k^2\log n)$. We also show that the length of our codes is shorter, for $n$ sufficiently large, than that of the codes whose existence was proved in [1].Open AccessAn Efficient Algorithm for Group Testing with Runlength Constraints
In this paper, we provide an efficient algorithm to construct almost optimal $(k,n,d)$-superimposed codes with runlength constraints. A $(k,n,d)$-superimposed code of length $t$ is a $t \times n$ binary matrix such that any two 1's in each column are separated by a run of at least $d$ 0's, and such that for any column $\mathbf{c}$ and any other $k-1$ columns, there exists a row where $\mathbf{c}$ has $1$ and all the remaining $k-1$ columns have $0$. These combinatorial structures were introduced by Agarwal et al. [1], in the context of Non-Adaptive Group Testing algorithms with runlength constraints. By using Moser and Tardos' constructive version of the Lovász Local Lemma, we provide an efficient randomized Las Vegas algorithm of complexity $Θ(t n^2)$ for the construction of $(k,n,d)$-superimposed codes of length $t=O(dk\log n +k^2\log n)$. We also show that the length of our codes is shorter, for $n$ sufficiently large, than that of the codes whose existence was proved in [1]. - 15 July 2024
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 70 (10) , 6974-6988
Bounds and Algorithms for Alphabetic Codes and Binary Search Trees
Alphabetic codes and binary search trees are combinatorial structures that abstract search procedures in ordered sets endowed with probability distributions. In this paper, we design new linear-time algorithms to construct alphabetic codes, and we show that the obtained codes are not too far from being optimal. Moreover, we exploit our results on alphabetic codes to provide new bounds on the average cost of optimal binary search trees. Our results improve on the best-known bounds on the average cost of optimal binary search trees present in the literature.
- 15 July 2024
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 70 (10) , 6974-6988
Bounds and Algorithms for Alphabetic Codes and Binary Search Trees
Alphabetic codes and binary search trees are combinatorial structures that abstract search procedures in ordered sets endowed with probability distributions. In this paper, we design new linear-time algorithms to construct alphabetic codes, and we show that the obtained codes are not too far from being optimal. Moreover, we exploit our results on alphabetic codes to provide new bounds on the average cost of optimal binary search trees. Our results improve on the best-known bounds on the average cost of optimal binary search trees present in the literature.
- Open Access
A Note on Equivalent Conditions for Majorization
In this paper, we introduce 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 used our new characterizations of majorization to derive an improved entropy inequality.
Open AccessA Note on Equivalent Conditions for Majorization
In this paper, we introduce 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 used our new characterizations of majorization to derive an improved entropy inequality.