1,721,000 research outputs found
A new combinatorial branch-and-bound algorithm for the Knapsack Problem with Conflicts
No full textWe study the Knapsack Problem with Conflicts, a generalization of the Knapsack Problem in which a set of conflicts specifies pairs of items which cannot be simultaneously selected. In this work, we propose a novel combinatorial branch-and-bound algorithm for this problem based on an n-ary branching scheme. Our algorithm effectively combines different procedures for pruning the branch-and-bound nodes based on different relaxations of the Knapsack Problem with Conflicts. Its main elements of novelty are: (i) the adoption of the branching-and-pruned set branching scheme which, while extensively used in the maximum-clique literature, was never successfully employed for solving the Knapsack Problem with Conflicts; (ii) the adoption of the Multiple-Choice Knapsack Problem for the derivation of upper bounds used for pruning the branch-and-bound tree nodes; and (iii) the design of a new upper bound for the latter problem which can be computed very efficiently. Key to our algorithm is its high pruning potential and the low computational effort that it requires to process each branch-and-bound node. An extensive set of experiments carried out on the benchmark instances typically used in the literature shows that, for edge densities ranging from 0.1 to 0.9, our algorithm is faster by up to two orders of magnitude than the state-of-the-art method and by up to several orders of magnitude than a state-of-the-art mixed-integer linear programming solver.</p
CliSAT: A new exact algorithm for hard maximum clique problems
No full textGiven a graph, the maximum clique problem (MCP) asks for determining a complete subgraph with the largest possible number of vertices. We propose a new exact algorithm, called CliSAT, to solve the MCP to proven optimality. This problem is of fundamental importance in graph theory and combinatorial optimization due to its practical relevance for a wide range of applications. The newly developed exact approach is a combinatorial branch-and-bound algorithm that exploits the state-of-the-art branching scheme enhanced by two new bounding techniques with the goal of reducing the branching tree. The first one is based on graph colouring procedures and partial maximum satisfiability problems arising in the branching scheme. The second one is a filtering phase based on constraint programming and domain propagation techniques. CliSAT is designed for structured MCP instances which are computationally difficult to solve since they are dense and contain many interconnected large cliques. Extensive experiments on hard benchmark instances, as well as new hard instances arising from different applications, show that CliSAT outperforms the state-of-the-art MCP algorithms, in some cases by several orders of magnitude.This publication is part of the R&D project “Cognitive Personal Assistance for Social Environments (ACOGES)”, reference PID2020-113096RB-I00, funded by MCIN/AEI/10.13039/501100011033.Peer reviewe
Revisiting the Dickensian echo of the HBO TV series The Wire
Full text linkThis article analyzes the alleged Dickensian echo of the highly-acclaimed HBO TV series The Wire. Charles Dickens is probably the literary author to whom the series has most frequently been likened. This correspondence is scrutinized here, as it seems to have been built upon impressionistic references, rather than on methodical intertextual analyses of both the series and the Victorian author. The analysis is intended to throw new light on the Dickensian ambience of The Wire, which seems to be different than previous critical appreciations of the series have suggested
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
A new branch-and-bound algorithm for the maximum edge-weighted clique problem
No full textWe study the maximum edge-weighted clique problem, a problem related to the maximum (vertex-weighted) clique problem which asks for finding a complete subgraph (i.e., a clique) of maximum total weight on its edges. The problem appears in a wide range of applications, including bioinformatics, material science, computer vision, robotics, and many more. In this work, we propose a new combinatorial branch-and-bound algorithm for the problem which relies on a novel bounding procedure capable of pruning a very large amount of nodes of the branch-and-bound tree. Extensive computational experiments on random and structured graphs, encompassing standard benchmarks used in the literature as well as recently introduced real-world large-scale graphs, show that our new algorithm outperforms the state-of-the-art by several orders of magnitude on many instances
Variations on the Author
Full text link“Variations on the Author” discusses two of Eduardo Coutinho’s recent films (Um Dia na Vida, from 2010, and Últimas Conversas, posthumously released in 2015) and their contribution to the general question of documentary authorship. The director’s filmography is characterized by a consistent yet self-effacing form of authorial self-inscription: Coutinho often features as an interviewer that rather than express opinions propels discourses; an interviewer that is good at listening. This mode of self-inscription characterizes him as an author who is not expressive but who is nonetheless markedly present on the screen. In Um Dia na Vida, however, Coutinho is completely absent form the image, while Últimas Conversas, on the contrary, includes a confessional prologue that moves the director from the margins to the center of his films. This article examines the ways in which these works stand out in the filmography of a director who offers new insights into the notion of cinematic authorship
Appropriate Similarity Measures for Author Cocitation Analysis
Full text linkWe provide a number of new insights into the methodological discussion about author cocitation analysis. We first argue that the use of the Pearson correlation for measuring the similarity between authors’ cocitation profiles is not very satisfactory. We then discuss what kind of similarity measures may be used as an alternative to the Pearson correlation. We consider three similarity measures in particular. One is the well-known cosine. The other two similarity measures have not been used before in the bibliometric literature. Finally, we show by means of an example that our findings have a high practical relevance.information science;Pearson correlation;cosine;similarity measure;author cocitation analysis
CLiC and Corpus Literary Translation Studies: An Analysis of Suspensions in One Spanish Translation of Charles Dickens’s Hard Times
Full text linkIn this article, corpus tools are used to analyse suspensions in Charles Dickens’s Hard Timesand their translation into Spanish. Suspensions are interruptions of a character’s words by the narrator, and are a characteristic feature of Dickens’s style. In this article, I analyse the consequences of not suspending these narratorial interruptions in the target text, in order to demonstrate the importance of preserving them when translating Dickens’s works into another language. The analysis has been carried out using the CLiC tool (Corpus Linguistics in Cheshire), which allows for the systematic retrieval of suspensions from literary texts. The Spanish translation under analysis is Lázaro Ros’s (Ros, 1992), in which a systematic rearrange-ment of the original suspensions has been detected. This analysis aims to demonstrate the potential of new software tools in literary translation studies, thus contributing another ex-ample to the always evolving field of corpus literary translation studies.In this article, corpus tools are used to analyse suspensions in Charles Dickens’s Hard Timesand their translation into Spanish. Suspensions are interruptions of a character’s words by the narrator, and are a characteristic feature of Dickens’s style. In this article, I analyse the consequences of not suspending these narratorial interruptions in the target text, in order to demonstrate the importance of preserving them when translating Dickens’s works into another language. The analysis has been carried out using the CLiC tool (Corpus Linguistics in Cheshire), which allows for the systematic retrieval of suspensions from literary texts. The Spanish translation under analysis is Lázaro Ros’s (Ros, 1992), in which a systematic rearrange-ment of the original suspensions has been detected. This analysis aims to demonstrate the potential of new software tools in literary translation studies, thus contributing another ex-ample to the always evolving field of corpus literary translation studies
El Pickwick de Galdós : Estudio traductológico de los verbos de habla a través de una aproximación computacional
Full text linkEn este artículo se analizan los verbos de habla en Pickwick Papers, de Charles Dickens, y su traducción al español en la versión de Benito Pérez Galdós. Para ello se ha utilizado un enfoque de corpus, que permite rescatar de forma sistemática estos verbos de la novela original. Los resultados obtenidos revelan una disposición muy concreta de este elemento, que contribuye a uno de los aspectos por los que el novelista victoriano goza de más reconocimiento en términos de caracterización: las hablas exageradas de sus personajes. Este valor caracterizador, sin embargo, no se conserva en la versión de Galdós. De hecho, como se podrá comprobar, su traducción contiene omisiones de texto, un uso demasiado extendido del verbo dijo e incluso algunas imprecisiones que anulan el valor estilístico de este elemento. La traducción de Galdós será cotejada con la de José María Valverde, quien también tradujo el Pickwick, de tal suerte que pueda demostrarse el grado en que los traductores pasan por alto la función caracterizadora de este elemento en el proceso de traducción.In this paper, speech verbs in Charles Dickens’s Pickwick Papers and their translation into Spanish by Benito Pérez Galdós are analyzed.To this end, a computer-assisted methodology which allows a systematic retrieval of speech verbs from the original novel has been used. The results pinpoint key choices contributing to one of Dickens’s best known features in terms of characterization: his characters’s exaggerated ways of speaking. This characterizing role, however, is not preserved in Galdós’s translation. In fact, this version contains text omissions, an over-use of the Spanish verb dijo and even some translation inaccuracies, which neglect the characterizing value of this element. Galdós’s version will be compared to Jose María Valverde’s translation of the same novel in order to gauge whether and to what extent translators overlook this stylistic trait when rendering speech verbs in Spanish
- …
