Computer Science - Journal Articles
Permanent URI for this collection
Browse
Recent Submissions
Item Partial compilation of SAT using selective backbones(IOS Press, 2023-09) Balogh, Andrea; Escamocher, Guillaume; O'Sullivan, Barry; Science Foundation IrelandOur goal in this paper is to significantly decrease the compiled size of a given Boolean instance with a large representation, while preserving as much information about the instance as possible. We achieve this by assigning values to a subset of the variables in such a way that the resulting instance has a much smaller representation than the original one, and its number of solutions is almost as high as the starting one. We call the set of variable instantiations that we make the selective backbone of the solutions that we keep. Large selective backbones allow for smaller representations, but also eliminate more solutions. We compare different methods of computing the selective backbone that offer the best compromise.Item IoT-enabled water distribution systems - a comparative technological review(IEEE, 2022-09-20) Velayudhan, N. K.; Pradeep, Preeja; Rao, S. N.; Devidas, A. R.; Ramesh, M. V.; Department of Science and Technology, Ministry of Science and Technology, IndiaWater distribution systems are one of the critical infrastructures and major assets of the water utility in a nation. The infrastructure of the distribution systems consists of resources, treatment plants, reservoirs, distribution lines, and consumers. A sustainable water distribution network management has to take care of accessibility, quality, quantity, and reliability of water. As water is becoming a depleting resource for the coming decades, the regulation and accounting of the water in terms of the above four parameters is a critical task. There have been many efforts towards the establishment of a monitoring and controlling framework, capable of automating various stages of the water distribution processes. The current trending technologies such as Information and Communication Technologies (ICT), Internet of Things (IoT), and Artificial Intelligence (AI) have the potential to track this spatially varying network to collect, process, and analyze the water distribution network attributes and events. In this work, we investigate the role and scope of the IoT technologies in different stages of the water distribution systems. Our survey covers the state-of-the-art monitoring and control systems for the water distribution networks, and the status of IoT architectures for water distribution networks. We explore the existing water distribution systems, providing the necessary background information on the current status. This work also presents an IoT Architecture for Intelligent Water Networks - IoTA4IWNet, for real-time monitoring and control of water distribution networks. We believe that to build a robust water distribution network, these components need to be designed and implemented effectively.Item Regular pattern-free coloring(Elsevier, 2022-11-15) Escamocher, Guillaume; O'Sullivan, Barry; Science Foundation Ireland; European Regional Development FundWe study the graph coloring problem under two kinds of simultaneous restrictions. First we forbid some patterns to appear in the graph, where a pattern is a small subgraph. Second we only consider regular graphs, meaning that all nodes have the same degree. Having both types of constraints at once leads us to the discovery of new tractable classes for graph coloring. However, we also show that some classes of pattern-free graphs remain NP-Complete even after enforcing regularity. Based on the latter results, we provide several complementary ways to generate difficult graph coloring instances, relying on balancing the degree of the nodes and avoiding a particular subgraph. Our constructions are parameterizable, so characteristics of the instances like size (number of nodes) and density (number of edges) can be set to any value.Item Analyzing and improving stability of matrix factorization for recommender systems(Springer, 2022-01-27) D'Amico, Edoardo; Gabbolini, Giovanni; Bernardis, Cesare; Cremonesi, Paolo; Science Foundation Ireland; European Regional Development FundThanks to their flexibility and scalability, collaborative embedding-based models are widely employed for the top-N recommendation task. Their goal is to jointly represent users and items in a common low-dimensional embedding space where users are represented close to items for which they expressed a positive preference. The training procedure of these techniques is influenced by several sources of randomness, that can have a strong impact on the embeddings learned by the models. In this paper we analyze this impact on Matrix Factorization (MF). In particular, we focus on the effects of training the same model on the same data, but with different initial values for the latent representations of users and items. We perform several experiments employing three well known MF implementations over five datasets. We show that different random initializations lead the same MF technique to generate very different latent representations and recommendation lists. We refer to these inconsistencies as instability of representations and instability of recommendations, respectively. We report that stability of item representations is positively correlated to the accuracy of the model. We show that the stability issues affect also the items for which the recommender correctly predicts positive preferences. Moreover, we highlight that the effect is stronger for less popular items. To overcome these drawbacks, we present a generalization of MF called Nearest Neighbors Matrix Factorization (NNMF). The new framework learns the embedding of each user and item as a weighted linear combination of the representations of the respective nearest neighbors. This strategy has the effect to propagate the information about items and users also to their neighbors and allows the embeddings of users and items with few interactions to be supported by a higher amount of information. To empirically demonstrate the advantages of the new framework, we provide a detailed description of the NNMF variants of three common MF techniques. We show that NNMF models, compared to their MF counterparts, largely improve the stability of both representations and recommendations, obtain a higher and more stable accuracy performance, especially on long-tail items, and reach convergence in a fraction of epochs.Item A collection of constraint programming models for the three-dimensional stable matching problem with cyclic preferences(Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021-10-15) Cseh, Ágnes; Escamocher, Guillaume; Genç, Begüm; Quesada, Luis; Science Foundation Ireland; European Regional Development FundWe introduce five constraint models for the 3-dimensional stable matching problem with cyclic preferences and study their relative performances under diverse configurations. While several constraint models have been proposed for variants of the two-dimensional stable matching problem, we are the first to present constraint models for a higher number of dimensions. We show for all five models how to capture two different stability notions, namely weak and strong stability. Additionally, we translate some well-known fairness notions (i.e. sex-equal, minimum regret, egalitarian) into 3-dimensional matchings, and present how to capture them in each model. Our tests cover dozens of problem sizes and four different instance generation methods. We explore two levels of commitment in our models: one where we have an individual variable for each agent (individual commitment), and another one where the determination of a variable involves pairing the three agents at once (group commitment). Our experiments show that the suitability of the commitment depends on the type of stability we are dealing with. Our experiments not only led us to discover dependencies between the type of stability and the instance generation method, but also brought light to the role that learning and restarts can play in solving this kind of problems.