Popular matchings with variable item copies

We consider the problem of matching people to items, where each person ranks a subset of items in an order of preference, possibly involving ties. There are several notions of optimality about how to best match a person to an item; in particular, popularity is a natural and appealing notion of optimality. A matching M* is popular if there is no matching M such that the number of people who prefer M to M* exceeds the number who prefer M* to M. However, popular matchings do not always provide an answer to the problem of determining an optimal matching since there are simple instances that do not admit popular matchings. This motivates the following extension of the popular matchings problem: Given a graph G = (A U 3, E) where A is the set of people and 2 is the set of items, and a list < c(1),...., c(vertical bar B vertical bar)> denoting upper bounds on the number of copies of each item, does there exist < x(1),...., x(vertical bar B vertical bar)> such that for each i, having x(i) copies of the i-th item, where 1 <= xi <= c(i), enables the resulting graph to admit a popular matching? In this paper we show that the above problem is NP-hard. We show that the problem is NP-hard even when each c(i) is 1 or 2. We show a polynomial time algorithm for a variant of the above problem where the total increase in copies is bounded by an integer k. (C) 2011 Elsevier B.V. All rights reserved.

A unified view of the Apriori-based algorithms for frequent episode discovery

Frequent episode discovery framework is a popular framework in temporal data mining with many applications. Over the years, many different notions of frequencies of episodes have been proposed along with different algorithms for episode discovery. In this paper, we present a unified view of all the apriori-based discoverymethods for serial episodes under these different notions of frequencies. Specifically, we present a unified view of the various frequency counting algorithms. We propose a generic counting algorithm such that all current algorithms are special cases of it. This unified view allows one to gain insights into different frequencies, and we present quantitative relationships among different frequencies.Our unified view also helps in obtaining correctness proofs for various counting algorithms as we show here. It also aids in understanding and obtaining the anti-monotonicity properties satisfied by the various frequencies, the properties exploited by the candidate generation step of any apriori-based method. We also point out how our unified view of counting helps to consider generalization of the algorithm to count episodes with general partial orders.

Voltage stability : some reflections on Q-V characteristics of loads

Considering voltage stability as a static viability problem, this paper takes a particular concern of Q-V characteristics and reflects on certain notions that do not seem to have been explicitly mentioned or derived in the existing documented literature. The equations of Q-V characteristics are rederived in exactness, some salient points on the curve are discovered and analysed. The results of the analysis are illustrated through a case study

A unified view of the apriori-based algorithms for frequent episode discovery

Frequent episode discovery framework is a popular framework in temporal data mining with many applications. Over the years, many different notions of frequencies of episodes have been proposed along with different algorithms for episode discovery. In this paper, we present a unified view of all the apriori-based discovery methods for serial episodes under these different notions of frequencies. Specifically, we present a unified view of the various frequency counting algorithms. We propose a generic counting algorithm such that all current algorithms are special cases of it. This unified view allows one to gain insights into different frequencies, and we present quantitative relationships among different frequencies. Our unified view also helps in obtaining correctness proofs for various counting algorithms as we show here. It also aids in understanding and obtaining the anti-monotonicity properties satisfied by the various frequencies, the properties exploited by the candidate generation step of any apriori-based method. We also point out how our unified view of counting helps to consider generalization of the algorithm to count episodes with general partial orders.

Pricing credit derivatives

The financial crisis set off by the default of Lehman Brothers in 2008 leading to disastrous consequences for the global economy has focused attention on regulation and pricing issues related to credit derivatives. Credit risk refers to the potential losses that can arise due to the changes in the credit quality of financial instruments. These changes could be due to changes in the ratings, market price (spread) or default on contractual obligations. Credit derivatives are financial instruments designed to mitigate the adverse impact that may arise due to credit risks. However, they also allow the investors to take up purely speculative positions. In this article we provide a succinct introduction to the notions of credit risk, the credit derivatives market and describe some of the important credit derivative products. There are two approaches to pricing credit derivatives, namely the structural and the reduced form or intensity-based models. A crucial aspect of the modelling that we touch upon briefly in this article is the problem of calibration of these models. We hope to convey through this article the challenges that are inherent in credit risk modelling, the elegant mathematics and concepts that underlie some of the models and the importance of understanding the limitations of the models.

Exploiting coherence for the simultaneous discovery of latent facets and associated sentiments

Facet-based sentiment analysis involves discovering the latent facets, sentiments and their associations. Traditional facet-based sentiment analysis algorithms typically perform the various tasks in sequence, and fail to take advantage of the mutual reinforcement of the tasks. Additionally,inferring sentiment levels typically requires domain knowledge or human intervention. In this paper, we propose aseries of probabilistic models that jointly discover latent facets and sentiment topics, and also order the sentiment topics with respect to a multi-point scale, in a language and domain independent manner. This is achieved by simultaneously capturing both short-range syntactic structure and long range semantic dependencies between the sentiment and facet words. The models further incorporate coherence in reviews, where reviewers dwell on one facet or sentiment level before moving on, for more accurate facet and sentiment discovery. For reviews which are supplemented with ratings, our models automatically order the latent sentiment topics, without requiring seed-words or domain-knowledge. To the best of our knowledge, our work is the first attempt to combine the notions of syntactic and semantic dependencies in the domain of review mining. Further, the concept of facet and sentiment coherence has not been explored earlier either. Extensive experimental results on real world review data show that the proposed models outperform various state of the art baselines for facet-based sentiment analysis.

IceCube: efficient targeted mining in data cubes

We address the problem of mining targeted association rules over multidimensional market-basket data. Here, each transaction has, in addition to the set of purchased items, ancillary dimension attributes associated with it. Based on these dimensions, transactions can be visualized as distributed over cells of an n-dimensional cube. In this framework, a targeted association rule is of the form {X -> Y} R, where R is a convex region in the cube and X. Y is a traditional association rule within region R. We first describe the TOARM algorithm, based on classical techniques, for identifying targeted association rules. Then, we discuss the concepts of bottom-up aggregation and cubing, leading to the CellUnion technique. This approach is further extended, using notions of cube-count interleaving and credit-based pruning, to derive the IceCube algorithm. Our experiments demonstrate that IceCube consistently provides the best execution time performance, especially for large and complex data cubes.

Quantum entropic ambiguities: Ethylene

In a quantum system, there may be many density matrices associated with a state on an algebra of observables. For each density matrix, one can compute its entropy. These are, in general, different. Therefore, one reaches the remarkable possibility that there may be many entropies for a given state R. Sorkin (private communication)]. This ambiguity in entropy can often be traced to a gauge symmetry emergent from the nontrivial topological character of the configuration space of the underlying system. It can also happen in finite-dimensional matrix models. In the present work, we discuss this entropy ambiguity and its consequences for an ethylene molecule. This is a very simple and well-known system, where these notions can be put to tests. Of particular interest in this discussion is the fact that the change of the density matrix with the corresponding entropy increase drives the system towards the maximally disordered state with maximum entropy, where Boltzman's formula applies. Besides its intrinsic conceptual interest, the simplicity of this model can serve as an introduction to a similar discussion of systems such as colored monopoles and the breaking of color symmetry.

Wireless bidirectional relaying and Latin squares

The design of modulation schemes for the physical layer network-coded two way relaying scenario is considered with the protocol which employs two phases: Multiple access (MA) Phase and Broadcast (BC) Phase. It was observed by Koike-Akino et al. that adaptively changing the network coding map used at the relay according to the channel conditions greatly reduces the impact of multiple access interference which occurs at the relay during the MA Phase and all these network coding maps should satisfy a requirement called the exclusive law. We show that every network coding map that satisfies the exclusive law is representable by a Latin Square and conversely, and this relationship can be used to get the network coding maps satisfying the exclusive law. Using the structural properties of the Latin Squares for a given set of parameters, the problem of finding all the required maps is reduced to finding a small set of maps for M-PSK constellations. This is achieved using the notions of isotopic and transposed Latin Squares. Furthermore, the channel conditions for which the bit-wise XOR will perform well is analytically obtained which holds for all values of M (for M any power of 2). We illustrate these results for the case where both the end users use QPSK constellation.

From Selective-ID to Full-ID IBS without Random Oracles

Since its induction, the selective-identity (sID) model for identity-based cryptosystems and its relationship with various other notions of security has been extensively studied. As a result, it is a general consensus that the sID model is much weaker than the full-identity (ID) model. In this paper, we study the sID model for the particular case of identity-based signatures (IBS). The main focus is on the problem of constructing an ID-secure IBS given an sID-secure IBS without using random oracles-the so-called standard model-and with reasonable security degradation. We accomplish this by devising a generic construction which uses as black-box: i) a chameleon hash function and ii) a weakly-secure public-key signature. We argue that the resulting IBS is ID-secure but with a tightness gap of O(q(s)), where q(s) is the upper bound on the number of signature queries that the adversary is allowed to make. To the best of our knowledge, this is the first attempt at such a generic construction.

Arcipreste de Talavera, parte I : las paremias en el esquema de los pecados capitales

Integran este número de la revista ponencias presentadas en Studia Hispanica Medievalia VIII: Actas de las IX Jornadas Internacionales de Literatura Española Medieval, 2008, y de Homenaje al Quinto Centenario de Amadis de Gaula.

El espacio memorial de los/as desaparecidos/as : algunas perspectivas epistemológicas

Resumen: La pregunta que guía este trabajo está referida a la posibilidad de extraer algunas perspectivas epistemológicas de la producción de un espacio memorial. Su tema está relacionado con los modos de reelaboración del trauma social. El tiempo histórico al que se refiere es el de la última dictadura cívico-militar (marzo 1976-diciembre 1983). El recorrido de este aporte tiene tres partes. En la primera, se consideran las nociones de cuerpo y narración; la segunda presenta esbozos de respuestas a la pregunta planteada y la tercera, está referida brevemente a dos mujeres europeas y cristianas: Alice Domon (Francia, 1937- Argentina, 1977) y Elisabeth Käsemann (Alemania, 1947- Argentina 1977). Ambas vivieron en América Latina y pueden ser consideradas verdaderos espacios humanitarios de paz.

La relación entre imputación y responsabilidad

Resumen: El autor analiza los conceptos de imputación y responsabilidad penales, y las realidades jurídicas y antrópicas a las que dichas nociones se refieren desde dos perspectivas principales: una, teórica, y otra, la historia del pensamiento. La investigación está precedida por una breve introducción semántica. El marco teórico es una concepción realista del derecho, subalternada a la antropología (psicología) filosófica, y más específicamente, al concepto del hombre como persona.

Benjamín de Tudela y los motivos del viaje : la educación del judío y el encuentro con la propia identidad a través del otro

Resumen: El presente trabajo aborda un tema concreto: el motivo u objeto con que el maestro y erudito español Benjamín de Tudela (1130-1173) abandona momentáneamente su país, España, para realizar un viaje de más de diez años por el Mediterráneo, el Asia Menor, el Medio Oriente y, aunque es menos probable, el Lejano Oriente. El corpus a considerar es su Libro de viajes (1160-1173), uno de los más completos y didácticos cuadernos de bitácora de la literatura occidental. Esta obra, que ha tenido grandes incidencias en la educación judía de siglos posteriores, es considerada hasta hoy como uno de los primeros documentos demográficos de las comunidades judías de la diáspora. Una vez identificados los motivos que impulsaron un periplo de tal calibre, procederé a analizar básicamente dos. Por un lado, la misión didáctica que él mismo se ha atribuido en consonancia con el precepto que ordena la transmisión intergeneracional de la fe y sus valores. Por otro lado, infiero un motivo que califico como de origen divino o sobrenatural, y que comparo con el viaje de Abraham desde Ur de Caldea hasta la Tierra Prometida. Para desarrollar este punto parto de un fragmento de la Biblia denominado en la tradición judía Lej lejá (Génesis XII:1-XVII:27), del que tomo los dos versículos iniciales, y aplico un análisis hecho por la licenciada y rabina Silvina Chemen con motivo del diálogo interreligioso.

La luz del intelecto agente en los principios de la razón práctica según San Alberto Magno

Resumen: La Antigone de Sófocles y el Corpus Hippocraticum delinean ya los rasgos propios del derecho natural. La ética de Aristóteles, luego, ofrece una primera noción explícita del derecho natural, que San Alberto Magno comenta en Super ethica. Sin embargo, en De inventione de Cicerón el teólogo alemán encuentra su definición de derecho natural: “lo que cierta fuerza innata introdujo”. En De bono V q. 1 San Alberto determina los alcances de esta definición y completa una presentación acabada de la noción de derecho natural. También advierte San Alberto que el hombre, con respecto a la ciencia del intelecto práctico, se encuentra doblemente en potencia. Primero, está en potencia de conocer los principios primeros de esta ciencia y, segundo, una vez conocidos éstos, se encuentra en potencia de inferir a partir de ellos las conclusiones de la ciencia práctica. Poseídas estas conclusiones, finalmente, el hombre está en potencia de aplicarlas en la acción práctica. Intrigado por el modo en que los primeros principios son conocidos, San Alberto advierte que el conocimiento de las nociones correspondientes a estos principios sólo accidentalmente debe ser atribuido al descubrimiento o determinación de los nombres con los que llamamos a estos principios. En verdad, es necesaria la intervención de la luz del intelecto agente para llevar al acto el conocimiento de los principios. En este punto el discurso de San Alberto retorna a la definición ciceroniana: aquella fuerza innata que introduce el derecho natural no es otra que la luz del intelecto agente.