Search

A random intersection graph is constructed by assigning independently to each vertex a subset of a given set and drawing an edge between two vertices if and only if their respective subsets intersect. In this article a model is developed in which each vertex is given a random weight and vertices with larger weights are more likely to be assigned large subsets. The distribution of the degree of a given vertex is characterized and is shown to depend on the weight of the vertex. In particular, if the weight distribution is a power law, the degree distribution will be as well. Furthermore, an asymptotic expression for the clustering in the graph is derived. By tuning the parameters of the model, it is possible to generate a graph with arbitrary clustering, expected degree, andin the power-law casetail exponent. © 2009 Cambridge University Press.

In the last decades, there was a notable progress in solving the well-known Boolean satisfiability (Sat) problem, which can be witnessed by powerful Sat solvers. One of the reasons why these solvers are so fast are structural properties of instances that are utilized by the solver’s interna. This thesis deals with the well-studied structural property treewidth, which measures the closeness of an instance to being a tree. In fact, there are many problems parameterized by treewidth that are solvable in polynomial time in the instance size when parameterized by treewidth. In this work, we study advanced treewidth-based methods and tools for problems in knowledge representation and reasoning (KR). Thereby, we provide means to establish precise runtime results (upper bounds) for canonical problems relevant to KR. Then, we present a new type of problem reduction, which we call decomposition-guided (DG) that allows us to precisely monitor the treewidth when reducing from one problem to another problem. This new reduction type will be the basis for a long-open lower bound result for quantified Boolean formulas and allows us to design a new methodology for establishing runtime lower bounds for problems parameterized by treewidth. Finally, despite these lower bounds, we provide an efficient implementation of algorithms that adhere to treewidth. Our approach finds suitable abstractions of instances, which are subsequently refined in a recursive fashion, and it uses Sat solvers for solving subproblems. It turns out that our resulting solver is quite competitive for two canonical counting problems related to Sat. In den letzten Jahrzehnten konnte ein beachtlicher Fortschritt im Bereich der Aussagenlogik verzeichnet werden. Dieser äußerte sich dadurch, dass für das wichtigste Problem in diesem Bereich, genannt „Sat“, welches sich mit der Fragestellung befasst, ob eine gegebene aussagenlogische Formel erfüllbar ist oder nicht, überwältigend schnelle Computerprogramme („Solver“) entwickelt werden konnten. Interessanterweise liefern diese Solver eine beeindruckende Leistung, weil sie oft selbst Probleminstanzen mit mehreren Millionen von Variablen spielend leicht lösen können. Auf der anderen Seite jedoch glaubt man in der Wissenschaft weitgehend an die Exponentialzeithypothese (ETH), welche besagt, dass man im schlimmsten Fall für das Lösen einer Instanz in diesem Bereich exponentielle Laufzeit in der Anzahl der Variablen benötigt. Dieser vermeintliche Widerspruch ist noch immer nicht vollständig geklärt, denn wahrscheinlich gibt es viele ineinandergreifende Gründe für die Schnelligkeit aktueller Sat Solver. Einer dieser Gründe befasst sich weitgehend mit strukturellen Eigenschaften von Probleminstanzen, die wohl indirekt und intern von diesen Solvern ausgenützt werden. Diese Dissertation beschäftigt sich mit solchen strukturellen Eigenschaften, nämlich mit der sogenannten Baumweite. Die Baumweite ist sehr gut erforscht und versucht zu messen, wie groß der Abstand von Probleminstanzen zu Bäumen ist (Baumnähe). Allerdings ist dieser Parameter sehr generisch und bei Weitem nicht auf Problemstellungen der Aussagenlogik beschränkt. Tatsächlich gibt es viele weitere Probleme, die parametrisiert mit Baumweite in polynomieller Zeit gelöst werden können. Interessanterweise gibt es auch viele Probleme in der Wissensrepräsentation (KR), von denen man davon ausgeht, dass sie härter sind als das Problem Sat, die bei beschränkter Baumweite in polynomieller Zeit gelöst werden können. Ein prominentes Beispiel solcher Probleme ist das Problem QSat, welches sich für die Gültigkeit einer gegebenen quantifizierten, aussagenlogischen Formel (QBF), das sind aussagenlogische Formeln, wo gewisse Variablen existenziell bzw. universell quantifiziert werden können, befasst. Bemerkenswerterweise wird allerdings auch im Zusammenhang mit Baumweite, ähnlich zu Methoden der klassischen Komplexitätstheorie, die tatsächliche Komplexität (Härte) solcher Problemen quantifiziert, wo man die exakte Laufzeitabhängigkeit beim Problemlösen in der Baumweite (Stufe der Exponentialität) beschreibt. Diese Arbeit befasst sich mit fortgeschrittenen, Baumweite-basierenden Methoden und Werkzeugen für Probleme der Wissensrepräsentation und künstlichen Intelligenz (AI). Dabei präsentieren wir Methoden, um präzise Laufzeitresultate (obere Schranken) für prominente Fragmente der Antwortmengenprogrammierung (ASP), welche ein kanonisches Paradigma zum Lösen von Problemen der Wissensrepräsentation darstellt, zu erhalten. Unsere Resultate basieren auf dem Konzept der dynamischen Programmierung, die angeleitet durch eine sogenannte Baumzerlegung und ähnlich dem Prinzip „Teile-und-herrsche“ funktioniert. Solch eine Baumzerlegung ist eine konkrete, strukturelle Zerlegung einer Probleminstanz, die sich stark an der Baumweite orientiert. Des Weiteren präsentieren wir einen neuen Typ von Problemreduktion, den wir als „decomposition-guided (DG)“, also „zerlegungsangeleitet“, bezeichnen. Dieser Reduktionstyp erlaubt es, Baumweiteerhöhungen und -verringerungen während einer Problemreduktion von einem bestimmten Problem zu einem anderen Problem präzise zu untersuchen und zu kontrollieren. Zusätzlich ist dieser neue Reduktionstyp die Basis, um ein lange offen gebliebenes Resultat betreffend quantifizierter, aussagenlogischer Formeln zu zeigen. Tatsächlich sind wir damit in der Lage, präzise untere Schranken, unter der Annahme der Exponentialzeithypothese, für das Problem QSat bei beschränkter Baumweite zu zeigen. Genauer gesagt können wir mit diesem Konzept der DG Reduktionen zeigen, dass das Problem QSat, beschränkt auf Quantifizierungsrang ` und parametrisiert mit Baumweite k, im Allgemeinen nicht besser als in einer Laufzeit, die `-fach exponentiell in der Baumweite und polynomiell in der Instanzgröße ist1, lösen. Dieses Resultat hebt auf nicht-inkrementelle Weise ein bekanntes Ergebnis für Quantifizierungsrang 2 auf beliebige Quantifizierungsränge, allerdings impliziert es auch sehr viele weitere Konsequenzen. Das Resultat über die untere Schranke des Problems QSat erlaubt es, eine neue Methodologie zum Zeigen unterer Schranken einer Vielzahl von Problemen der Wissensrepräsentation und künstlichen Intelligenz, zu etablieren. In weiterer Konsequenz können wir damit auch zeigen, dass die oberen Schranken sowie die DG Reduktionen dieser Arbeit unter der Hypothese ETH „eng“ sind, d.h., sie können wahrscheinlich nicht mehr signifikant verbessert werden. Die Ergebnisse betreffend der unteren Schranken für QSat und die dazugehörige Methodologie konstituieren in gewisser Weise eine Hierarchie von über Baumweite parametrisierte Laufzeitklassen. Diese Laufzeitklassen können verwendet werden, um die Härte von Problemen für das Ausnützen von Baumweite zu quantifizieren und diese entsprechend ihrer Laufzeitabhängigkeit bezüglich Baumweite zu kategorisieren. Schlussendlich und trotz der genannten Resultate betreffend unterer Schranken sind wir im Stande, eine effiziente Implementierung von Algorithmen basierend auf dynamischer Programmierung, die entlang einer Baumzerlegung angeleitet wird, zur Verfügung zu stellen. Dabei funktioniert unser Ansatz dahingehend, indem er probiert, passende Abstraktionen von Instanzen zu finden, die dann im Endeffekt sukzessive und auf rekursive Art und Weise verfeinert und verbessert werden. Inspiriert durch die enorme Effizienz und Effektivität der Sat Solver, ist unsere Implementierung ein hybrider Ansatz, weil sie den starken Gebrauch von Sat Solvern zum Lösen diverser Subprobleme, die während der dynamischen Programmierung auftreten, pflegt. Dabei stellt sich heraus, dass der resultierende Solver unserer Implementierung im Bezug auf Effizienz beim Lösen von zwei kanonischen, Sat-verwandten Zählproblemen mit bestehenden Solvern locker mithalten kann. Tatsächlich sind wir im Stande, Instanzen, wo die oberen Schranken von Baumweite 260 übersteigen, zu lösen. Diese überraschende Beobachtung zeigt daher, dass Baumweite ein wichtiger Parameter sein könnte, der wohl in modernen Designs von Solvern berücksichtigt werden sollte.

The Inventory Routing Problem (IRP) involves the distribution of one or more products from a supplier to a set of clients over a discrete planning horizon. Each client has a known demand to be met in each period and can only hold a limited amount of stock. The product is shipped through a distribution network by one or more vehicles of limited capacity. The objective is to find replenishment decisions minimizing the sum of the storage and distribution costs. In this paper, we present IRP reformulations under the Maximum Level replenishment policy, derived from a single-period substructure. We define a generic family of valid inequalities, and then introduce two specific subclasses for which the separation problem of generating violated inequalities can be effectively solved. A basic Branch-and-Cut algorithm has been implemented to demonstrate the strength of the single-period reformulations. We present computational results for the benchmark instances with 50 clients and 3 periods and 30 clients and 6 periods. The online appendix is available at https://doi.org/10.1287/trsc.2016.0729 .

In this paper the initial analysis of NDT laboratory is presented by means of agent-based modelling. For the purpose of analysis, laboratory is taken into account as a complex system consisting of three agents ; equipment, personnel and specimens. Interaction between the agents is circular. In that sense, the agents are mutually interconnected in a way that one agent simultaneously interacts with others. According to the interactions specific for NDT laboratories, the response of total testing time is presented considering various number of laboratory personnel while each operator has different skills and ability. Agent personnel has to perform testing of specimens. Since the complexity of specimens is quite diverse the specimens are represented as an agent. Additionally, during the whole time sequence of testing a certain specimen, operator is using NDT equipment relevant for the testing method, while the particular time of usage of the equipment can be shorter than the whole testing time. Availability of the equipment is therefore another agent. The evaluated outcome is the total testing time. Presented results are obtained carrying out a simulation by means of multi-agent modelling and simulation tool named “ ENTORAMA” . Finally, the overall laboratory's performance is given in the respect of the number and structure of the laboratory personnel.

In this paper we have found an analytical formula for a copula that connects the numbers Ni of customers in the nodes of a Gordon and Newell queueing network. We have considered two cases: the first one is the case of the network with 2 nodes, and the second one is the case of the network with at least 3 nodes. The analytical formula for the second case has been found for the most general case (none of the constants from a list is equal to a given value), and the other particular cases have been obtained by limit.

Se propone y se desarrolla un procedimiento desde el paradigma de la complejidad que, partiendo de las características más generales que permiten identificar a las organizaciones turísticas como sistemas sociales humanos complejos, valora los impactos de la capacitación en la consecución de las metas organizacionales. El procedimiento se aborda desde la aplicación del modelo de valoración de los efectos olvidados en las relaciones de causalidad del sistema de acciones de capacitación, identificando a través de la matriz de relación incidencia-dependencia, la cohesión estructural de la estrategia de capacitación y los lazos de interacción entre las diferentes acciones expresadas en grafos. Finalmente, en las conclusiones, se destacan los valores del modelo propuesto y aplicado, como contribución al perfeccionamiento de las estrategias de capacitación. = A procedure is developed from the paradigm of the complexity, starting from their most general characteristics to identify tourism organizations as social human complex systems. This procedure values the impacts of the training in the achievement of the organizational goals. The model of forgotten effects to the causality relationships of the system of training actions and, by using the relationship matrix of incidence-dependence, the structural cohesion is identified in the training strategy. The interaction links among the different actions have been expressed by graphs. Finally, the conclusions bring out the values of the proposed and applied method as a contribution to the improvement of the training strategies.

A microeconomic, agent based framework to dynamic economics is formulated in a materialist approach. An axiomatic foundation of a non-equilibrium microeconomics is outlined. Economic activity is modelled as transformation and transport of commodities (materials) owned by the agents. Rate of transformations (production intensity), and the rate of transport (trade) are defined by the agents. Economic decision rules are derived from the observed economic behaviour. The non-linear equations are solved numerically for a model economy. Numerical solutions for simple model economies suggest that the some of the results of general equilibrium economics are consequences only of the equilibrium hypothesis. We show that perfect competition of selfish agents does not guarantee the stability of economic equilibrium, but cooperativity is needed, too.

This discussion paper resulted in a publication in the Mathematical Methods of Operations Research (2005). Volume 62, issue 3, pages 467-483. We develop a methodology for studying "large deviations type" questions. Our approach does not require that the large deviations principle holds, and is thus applicable to a larg class of systems. We study a system of queues with exponential servers, which share an arrival stream. Arrivals are routed to the (weighted) shortest queue. It is not known whether the large deviations principle holds for this system. Using the tools developed here we derive large deviations type estimates for the most likely behavior, the most likely path to overflow and the probability of overflow. The analysis applies to any finite number of queues. We show via a counterexample that this sytem may exhibit unexpected behavior.

In this paper, we propose a new original method to solve the production cost minimization problem with Cobb-Douglas production function by using the weighted arithmetic-geometric-mean inequality (weighted AM-GM inequality). Instead of using derivatives or the Lagrange multiplier method, the minimum costs and global minimizers in the case of the Cobb-Douglas production function are derived in the direct way. The result is first derived for the case of two inputs and then generalized for the problem with n inputs.

This paper presents a new method for calculating Gini coefficients from tabulations of the mean income of social classes. Income distribution data from before the Industrial Revolution usually come in the form of such tabulations, called social tables. Inequality indices generated from social tables are frequently calculated without adjusting for within-group income dispersion, leading to a systematic downward bias in the reporting of pre-industrial inequality. The correction method presented in this paper is applied to an existing collection of twenty-five social tables, from Rome in AD 1 to India in 1947. The corrections, using a variety of assumptions on within-group dispersion, lead to substantial increases in the Gini coefficients. Combining the inequality levels with data on GDP suggests a positive relationship between income inequality and economic growth. This supports earlier proposals, based on fewer data points, of a “super Kuznets curve” of increasing inequality over the entire pre-industrial period.

Over the past years a large number of regional growth theories have been developed and a number of models have been built in an effort to describe, explain and eventually predict regional development trends. However, until a few years ago, the large majority of those models assumed the existence of linear and thus regular, growth processes. Linear models are certainly able to generate unstable solutions, but the solutions of such models are restricted to certain regular standard types. Such models may provide approximate replications of short and medium, run changes, but they fail to interpret long-term developments characterized by structural shifts of an irregular nature. Furthermore, the study of regional growth through linear models is limited because it does not allow us to take into account a number of behavioural changes, opinion formation as well as economies and diseconomies of scale which are strongly characterized by non-linearities. This limitation has recently been overcome with the adoption of non-linear models which allow for a change in a system's dynamics generated by even small perturbations in structural forms. Structural instability entails the possible existence of significant qualitative changes in the behaviour of the system (i.e. in the state variables) closely connected with bifurcation and catastrophic phenomena that may occur if the parameter values (i.e. the control variable) reach critical values. The application of non-linear models has shown that the deterministic and well-behaved unique results achieved by the dynamic linear models are no longer guaranteed: interregional convergence determined by the traditional models collapses and opens the way to alternative possible trajectories and multiple equilibria. The non-linear models are thus able to simulate an endogenous series of complex phenomena which in the past could only be replicated by means of exogenous shocks introduced ad hoc. The present paper introduces a country's Image, a variable which expresses a country's state of development and its future prospects. Furthermore, the factors affecting this variable are defined and ways of measuring them are suggested. Finally, these factors are grouped into different ways leading to two alternative non-linear models for the generation of country's image. The two models are applied to the case of the European South and the values of the two sets of Images for those countries are compared and discussed. Keywords: Country's Image, Regional Development, Sustainable Development, Economic Factors, Social Factors, Environmental Factors, Cusp Catastrophe Model, Butterfly Catastrophe Model.

We study a general preferential attachment and Polya's urn model. At each step a new vertex is introduced, which can be connected to at most one existing vertex. If it is disconnected, it becomes a pioneer vertex. Given that it is not disconnected, it joins an existing pioneer vertex with probability proportional to a function of the degree of that vertex. This function is allowed to be vertex-dependent, and is called the reinforcement function. We prove that there can be at most three phases in this model, depending on the behavior of the reinforcement function. Consider the set whose elements are the vertices with cardinality tending a.s. to infinity. We prove that this set either is empty, or it has exactly one element, or it contains all the pioneer vertices. Moreover, we describe the phase transition in the case where the reinforcement function is the same for all vertices. Our results are general, and in particular we are not assuming monotonicity of the reinforcement function. Finally, consider the regime where exactly one vertex has a degree diverging to infinity. We give a lower bound for the probability that a given vertex ends up being the leading one, that is, its degree diverges to infinity. Our proofs rely on a generalization of the Rubin construction given for edge-reinforced random walks, and on a Brownian motion embedding., Comment: Published in at http://dx.doi.org/10.1214/12-AAP869 the Annals of Applied Probability (http://www.imstat.org/aap/) by the Institute of Mathematical Statistics (http://www.imstat.org)

The first objective of this contribution is to evaluate the performance of socially responsible investment (SRI) equity mutual funds in the main European countries with three different data envelopment analysis (DEA) models. Secondly, with a series of statistical tests we compare the performance of SRI and non SRI mutual funds in the various countries, to determine if SRI mutual funds have to sacrifice something in terms of financial performance; the results suggests that it is possible to invest in a socially responsible manner without giving up the financial reward. Thirdly, we compare the performance obtained by SRI mutual funds among different European countries.

The Conflict Analysis approach by Hipel and Fraser (1984) is well equipped to model repeated games. Players are assumed to posses a sequential reasoning that allows them to ( not necessarily correctly) anticipate the reaction of other players to their strategies. An individual's best response strategy is thus defined based on this projection, adding additional stability conditions to strategic choice and increasing the set of potential equilibria beyond pure Nash equilibria. Yet, the original Conflict Analysis approach lacks the ability to genuinely model dynamic repeated games, in which past play defines the condition for future interactions. This article will illustrate how the original model can be adapted to include endogenous individual preferences that are defined by the strategic choice of players during past play, allowing to model the reciprocal connection between preferential change and best response play in repeated games. A dummy game serves as an exemplar and helps to visualise the results obtained from this extension.

In the classical discrete-time mean-variance context, a method for portfolio optimisation using conditioning information was introduced in 2001 by Ferson and Siegel ([1]). The fact that there are many possible signals that could be used as conditioning information, and a number of empirical studies that suggest measurable relationships between signals and returns, causes this type of portfolio optimisation to be of practical as well as theoretical interest. Ferson and Siegel obtain analytical formulae for the basic unconstrained portfolio optimisation problem. We show how the same problem, in the presence of a riskfree asset and given a single conditioning information time series, may be expressed as a general constrained infinite-horizon optimal control problem which encompasses the results in [1] as a special case. Variants of the problem not amenable to closed-form solutions can then be solved using standard numerical optimal control techniques. We extend the standard finite-horizon optimal control sufficiency and necessity results of the Pontryagin Maximum Principle and the Mangasarian sufficiency theorem to the doubly-infinite horizon case required to cover our formulation in its greatest generality. As an application, we rephrase the previously unsolved constrained-weight variant of the problem in [1] using the optimal control framework and derive the specific necessary conditions applicable. Finally, we carry out simulations involving numerical solution of the resulting optimal control problem to assess the extent to which the use of conditioning information brings about practical improvements in the field of portfolio optimisation.

The globalisation is a complex phenomenon with many advantageous and disadvantageous consequences. In this paper we investigate the linkage between globalised market economy and the happiness through the ethical implications of the greatest happiness principle in a system approach. We also investigate the terms of the beneficial globalisation. Our proposition is that: the main condition of the good globalisation should be Bentham's principle: the greatest happiness for the greatest number and the United States Declaration of Independence's famous phrase pursuit of happiness. We face the following problem: the globalization assures - due to its Nature - the growth of Z, which is the marketed part of the globalization, but not the total happiness. The main question in political philosophy is: What do we need to do in order to live together well? In complex approach, based on the wealth increase law we take into account the parameters, which will be changed by the human decisions (i) as well as the long-term expectations, which are motivating the decisions themselves (ii). Factors (i) are the followings: material goods, money, parameters of human physiology (e.g. health), psychology (knowledge), sociology (e.g. friends, power). These quantities are measurable in principle, i.e. they can be mapped into the set of real numbers. The changes are exchanges between two agents or with the nature, and there is production/consumption inside the agent.

Este artículo analiza la competitividad de las capitales de distrito portuguesas desde un enfoque institucionalista. Primero revisa algunos trabajos académicos sobre el tema de la competitividad en sus diversos aspectos. Luego prueba la siguiente hip��tesis: “Las ciudades del interior de Portugal tienen dimensiones socio-económicas competitivas en el contexto nacional”. Para este trabajo se construyó un Índice de Competitividad de las Ciudades que indica que las regiones del interior tienen valores más competitivos en los aspectos de demografía, empleo y bienestar.

Identification in errors-in-variables regression models was recently extended to wide models classes by S. Schennach (Econometrica, 2007) (S) via use of generalized functions. In this paper the problems of non- and semi- parametric identification in such models are re-examined. Nonparametric identification holds under weaker assumptions than in (S); the proof here does not rely on decomposition of generalized functions into ordinary and singular parts, which may not hold. Conditions for continuity of the identification mapping are provided and a consistent nonparametric plug-in estimator for regression functions in the L₁ space constructed. Semiparametric identification via a finite set of moments is shown to hold for classes of functions that are explicitly characterized; unlike (S) existence of a moment generating function for the measurement

The research into the effectiveness of financial aid is gaining momentum lately. Some say it is ineffective, some say it could be effective, but all seem to agree that some of its aspects are currently unmapped. This article aims at showing a rather simplistic agent-based model that might hint at a possible useful approach of the issue. It will be shown, that the donor policies do influence stability, convergence and the path of economic growth.

For a long period of time a country’s development has been synonymous with its economic growth. Over the last years, however, economies and societies have been undergoing dramatic changes. These changes have led to the concept of sustainable development, which refers to the ability of our societies to meet the needs of the present without sacrificing the ability of future generations to meet their own needs. Measuring sustainable development means going beyond a purely economic description of human activities; requires integration of economic, social and environmental concerns. New techniques are required in order to benchmark performance, highlight leaders and laggards on various aspects of development and facilitate efforts to identify best practices. New tools have to be designed so as to make sustainability decision-making more objective, systematic and rigorous. The majority of those methodologies make use of a single indicator in order to measure separately the evolution of each component i.e. the economic, the social and the environmental. Our objective in the present paper is to: \ud - Outline the process of a country’s development taking into account all its three dimensions, economic, social and environmental.\ud - Present a model for quantifying its process of development encompassing all those dimensions.\ud - Apply the model to European South countries.\ud - Discuss the results.