840 research outputs found
New theoretical results on the Monotone Boolean Duality and the Monotone Boolean Dualization problems
No full textThis work presents a new decomposition for the Monotone Boolean Duality problem, which consists of checking whether two monotone Boolean functions f (described by its unique irredundant DNF) and g (described by its unique irredundant CNF) are equivalent. This coNP problem has several applications and relevance in many research areas (e.g., data mining and knowledge discovery, artificial intelligence, matroid theory, computational biology, and, last but not least, mathematical programming). Best-known algorithms run in quasi-polynomial time; no polynomial-time algorithm has been discovered yet, even if for many special classes these are known. The exact complexity of the general problem is still an open question. Based on both classical results by Berge (1989) and Fredman and Khachiyan (1996), and also on the concept of full covers used by Boros and Makino (2009) and Elbassioni (2008), we propose a new approach to decompose the problem and obtain new theoretical results. Our scheme offers a strong bound which, in the worst case only, has the same time complexity as Fredman and Khachiyan (1996). Anyway, it better highlights the inherent symmetry of the problem, lets us present another polynomial-space algorithm for the Monotone Boolean Dualization problem, and motivates further study on full covers. (c) 2024 Elsevier B.V. All rights are reserved, including those for text and data mining, AI training, and similar technologies
Listing the bonds of a graph in O ̃(n)–delay
No full textGiven a connected graph G = (V, E), with n := |V| vertices and m := |E| edges, a cut can be represented as a bipartition {S, S} of the vertices or as the set of those edges in E having one endpoint in S and the other in S, denoted by 8G(S, S). A cut is minimal, or also called bond, if and only if the two induced subgraphs obtained by removing the edges in the cut are both connected. When the bond separates two given vertices s and t, we talk about s, t-bond. In this work, we consider the problems of listing all the bonds and listing all the s, t-bonds in a graph. These fundamental problems find application in many research areas, such as, beyond graph theory, network reliability, bioinformatics, and chemistry. The state-of-the-art algorithm exploits binary partition to output each s, t-bond in O(m) per bond, being thus classified as an O(m)-delay algorithm. Here we present two new algorithms to address these problems. The first one implements a slightly different branching strategy than the state of the art, though achieving the same complexity. Anyway, we can improve it by relying on dynamic data structures and amortized analysis, obtaining an algorithm that outputs a new bond in O similar to(n). By assuming only the two bond-shores are output for every bond, this is the first outputlinear algorithm listing bonds. In case we commit to explicitly providing the entire edge-set of every bond, the delay becomes O similar to(n) + |8G(S, S)|. (c) 2024 Elsevier B.V. All rights reserved
Faster and better simple temporal problems
No full textIn this paper we give a structural characterization and ex- tend the tractability frontier of the Simple Temporal Problem (STP) by defining the class of the Extended Simple Temporal Problem (ESTP), which augments STP with strict inequal- ities and monotone Boolean formulae on inequations (i.e., formulae involving the operations of conjunction, disjunction and parenthesization). A polynomial-time algorithm is pro- vided to solve ESTP, faster than previous state-of-the-art al- gorithms for other extensions of STP that had been consid- ered in the literature, all encompassed by ESTP. We show the practical competitiveness of our approach through a proof-of- concept implementation and an experimental evaluation involving also state-of-the-art SMT solvers
An interdisciplinary experimental evaluation on the disjunctive temporal problem
No full textWe report on an extensive experimental evaluation on the Disjunctive Temporal Problem, where we adapted state-of-the-art Satisfiability Modulo Theories (SMT) encodings into the frameworks of Mixed Integer Linear Programming (MILP), (Circuit) Satisfiability (SAT), and Constraint Programming (CP). We considered 6 SMT solvers, 4 MILP solvers, 3 SAT solvers, and 3 CP solvers, broadly-recognized for their technologies. We compared all of them on several sets of benchmarks. As well as considering 2 random sets in the literature, we generated 3 new industrial and 3 new computationally-hard sets of benchmarks, which we make publicly available online. In particular, we analyzed 9885 instances, each processed on average about 33 times. Overall, SMT is confirmed to be the current best technology, but also MILP can perform very well, for instance on some random instances, on which it can be up to 2x faster than SMT. On a single machine, this experimental evaluation would have taken 598.97 days
Allegorie della scrittura. Mario De Leo. Raffaele Penna. Grazia Ribaudo
No full textcatalogo di una mostra collettiva dedicata all'interpretazione della scrittura da parte di tre artisti contemporane
A Two-Phase Approach to Evaluate and Optimize an Interlibrary Loan Service: The Case Study of Provincia di Brescia
No full textWeanalyzethecasestudyofProvinciadiBrescia,anItalianpublicbody managing libraries in the province of Brescia, in Northern Italy. The public body offers an interlibrary loan service organized as follows. Libraries are divided into established groups, each associated with a fixed route. According to a predetermined calendar, each library is visited by a courier a few times a week. The transportation of the items in the network is performed by an external logistics firm, selected through a reverse auction. To assess the current implementation of the service in terms of routing and transportation costs, we propose a two-phase approach based on machine learning and mixed-integer linear programming, and we evaluate it on the data of 2019. Then, we discuss its applicability in reality, and provide a few insights
Corrado Cagli. Transatlantic bridges, 1938-1947
No full textIn the 1930s the young Italian artist, Corrado Cagli was a rising star of the Scuola Romana, supported by the Fascist regime despite being both Jewish and a homosexual. Following the Racial Laws, he fled first to Paris, and then to the USA, where he remained until 1947. Raffaele Bedarida’s new book, Corrado Cagli – La pittura, l’esilio, l’America (1938-1947) Donzelli Editore, 2018 (soon to be translated into English by CPL Editions), focuses on Cagli’s American exile.
While examining Cagli in the context of the artistic and intellectual migration from Europe to the US, Bedarida provides valuable new insight into the specific plight of this Italian Jewish artist, once championed by Fascism and into the complexities of the use of art for cultural diplomacy.
The author combines biography, cultural history, and critical analysis in exploring a decisive period in the life and work of a painter whose complex personality and non-signature style, defy classifications. The book also provides thought-provoking and nuanced arguments on the ideologically based ostracism that Cagli encountered upon returning to Italy in the immediate aftermath of the war. Because of his past as a former regime-endorsed artist, his recent American success, his participation in the liberation of Europe from Nazi-Fascism with the American army, and Jewish exile, Cagli simply did not fit into any of the faction of Italy’s post-war heated cultural disputes.
Based on extensive original research and written with brio, Bedarida’s book is an essential contribution to a growing field of studies that examine how, by welcoming artist and intellectuals in flight from Nazi-Fascism, the United States had been given what Will Norman has called “custodianship for a civilization.
Proceedings of the LREC 2020 workshop on Resources and Techniques for User and Author Profiling in Abusive Language (ResT-UP 2020)
No full textThis volume documents the Proceedings of the 1st Workshop on Resources and Techniques for User and Author Profiling in Abusive Language (ResT-UP), held online on 12 May 2020 as part of the LREC 2020 conference (International Conference on Language Resources and Evaluation).
The workshop aimed at bringing together researchers and scholars working on author profiling and automatic detection of abusive language on the Web, e.g., cyberbullying or hate speech, with a twofold objective: improving the existing LRs, e.g., datasets, corpora, lexicons, and sharing ideas on stylometry techniques and features needed for profile information extraction and classification. ResT-UP targeted Profiling scholars and research groups, experts in Statistic and Stylistic Analysis of texts as well as computational linguists who investigate author profile and personality both in short texts (social media posts, blog texts and email) and in long texts (such as pamphlets, (fake) news and political documents). ReST-UP represented an opportunity to share profiling experiments with the scientific community and to show automatic detection techniques of abusive language on the Web. Despite the cancellation of LREC 2020 due to the COVID-19 international emergency, ResT-UP was organized online on Microsoft Teams on May 12th 2020 and the programme included three oral presentations and featured an invited talk by Paolo Rosso. ResT-UP was attended by about fifty representatives of academic and industrial organisations
Solemnidad de la civilidad
No full textIl fenomeno delle periferie e la forma della città. Riflessione preparatoria al progetto di riorganizzazione della periferia della città messicana di Santiago di Querétar
- …
