On balanced CSPs with high treewidth

Tractable cases of the binary CSP are mainly divided in two classes: constraint language restrictions and constraint graph restrictions. To better understand and identify the hardest binary CSPs, in this work we propose methods to increase their hardness by increasing the balance of both the constraint language and the constraint graph. The balance of a constraint is increased by maximizing the number of domain elements with the same number of occurrences. The balance of the graph is defined using the classical definition from graph the- ory. In this sense we present two graph models; a first graph model that increases the balance of a graph maximizing the number of vertices with the same degree, and a second one that additionally increases the girth of the graph, because a high girth implies a high treewidth, an important parameter for binary CSPs hardness. Our results show that our more balanced graph models and constraints result in harder instances when compared to typical random binary CSP instances, by several orders of magnitude. Also we detect, at least for sparse constraint graphs, a higher treewidth for our graph models.

Scheduling an European basketball competition. An application of graph theory

The object of this project is to schedule a ctitious European basketball competition with many teams situated a long distances. The schedule must be fair, feasible and economical, which means that the total distance trav- eled by every team must be the minimal possible. First, we de ne the sport competition terminology and study di erent competition systems, focusing on the NBA and the Euroleague systems. Then we de ne concepts of graph theory and spherical distance that will be needed. Next we propose a com- petition system, explaining where will be allocated the teams and how will be the scheduling. Then there is a description of the programs that have been implemented, and, nally, the complete schedule is displayed, and some possible improvements are mentioned.

Testing Cayley graph densities

We present a computer-assisted analysis of combinatorial properties of the Cayley graphs of certain finitely generated groups: Given a group with a finite set of generators, we study the density of the corresponding Cayley graph, that is, the least upper bound for the average vertex degree (= number of adjacent edges) of any finite subgraph. It is known that an m-generated group is amenable if and only if the density of the corresponding Cayley graph equals to 2m. We test amenable and non-amenable groups, and also groups for which amenability is unknown. In the latter class we focus on Richard Thompson’s group F.

Diophantine approximation on projective varieties I: algebraic distance and metric Bézout theorem

"Vegeu el resum a l'inici del document del fitxer adjunt."

Scheduled service versus personal transportation: the role of distance

This paper analyzes both theoretically and empirically the relationship between distance and frequency of scheduled transportation services. We study the interaction between a monopoly firm providing high-speed scheduled service and personal trans- portation (i.e., car). Most interestingly, the carrier chooses to increase frequency of service on longer routes when competing with personal transportation because provid- ing a higher frequency (at extra cost) it can also charge higher fares that can boost its profits. However, when driving is not a relevant option, frequency of service de- creases for longer flights consistently with prior studies. An empirical application of our analysis to the European airline industry con?rms the predictions of our theoretical model.

Scheduled Service Versus Personal Transportation: The Role of Distance

This paper presents a theoretical and empirical analysis of the relationship be- tween frequency of scheduled transportation services and their substitutability with personal transportation (using distance as a proxy). We study the interaction between a monopoly firm providing a high-speed scheduled service and private transportation (i.e., car). Interestingly, the carrier chooses to increase the frequency of service on longer routes when competing with personal transportation because by providing higher frequency (at extra cost) it can also charge higher fares which can boost its profits. However, in line with the results of earlier studies, frequency decreases for longer flights when driving is not a viable option. An empirical application of our analysis to the European airline industry confirms the predictions of our theoretical model. Keywords: short-haul routes; long-haul routes; flight frequency; distance JEL Classification Numbers: L13; L2; L93

Theoretical aspects of graph models for MANETs

We survey the main theoretical aspects of models for Mobile Ad Hoc Networks (MANETs). We present theoretical characterizations of mobile network structural properties, different dynamic graph models of MANETs, and finally we give detailed summaries of a few selected articles. In particular, we focus on articles dealing with connectivity of mobile networks, and on articles which show that mobility can be used to propagate information between nodes of the network while at the same time maintaining small transmission distances, and thus saving energy.

Clustering or scattering: the underlying reason for regulating distance among retail outlets

Concerns on the clustering of retail industries and professional services in main streets had traditionally been the public interest rationale for supporting distance regulations. Although many geographic restrictions have been suppressed, deregulation has hinged mostly upon the theory results on the natural tendency of outlets to differentiate spatially. Empirical evidence has so far offered mixed results. Using the case of deregulation of pharmacy establishment in a region of Spain, we empirically show how pharmacy locations scatter, and that there is not rationale for distance regulation apart from the underlying private interest of very few incumbents.

A linear optimization technique for graph pebbling

Graph pebbling is a network model for studying whether or not a given supply of discrete pebbles can satisfy a given demand via pebbling moves. A pebbling move across an edge of a graph takes two pebbles from one endpoint and places one pebble at the other endpoint; the other pebble is lost in transit as a toll. It has been shown that deciding whether a supply can meet a demand on a graph is NP-complete. The pebbling number of a graph is the smallest t such that every supply of t pebbles can satisfy every demand of one pebble. Deciding if the pebbling number is at most k is NP 2 -complete. In this paper we develop a tool, called theWeight Function Lemma, for computing upper bounds and sometimes exact values for pebbling numbers with the assistance of linear optimization. With this tool we are able to calculate the pebbling numbers of much larger graphs than in previous algorithms, and much more quickly as well. We also obtain results for many families of graphs, in many cases by hand, with much simpler and remarkably shorter proofs than given in previously existing arguments (certificates typically of size at most the number of vertices times the maximum degree), especially for highly symmetric graphs. Here we apply theWeight Function Lemma to several specific graphs, including the Petersen, Lemke, 4th weak Bruhat, Lemke squared, and two random graphs, as well as to a number of infinite families of graphs, such as trees, cycles, graph powers of cycles, cubes, and some generalized Petersen and Coxeter graphs. This partly answers a question of Pachter, et al., by computing the pebbling exponent of cycles to within an asymptotically small range. It is conceivable that this method yields an approximation algorithm for graph pebbling.

Local Distance-Based Generalized Linear Models using the dbstats package for R

This paper introduces local distance-based generalized linear models. These models extend (weighted) distance-based linear models firstly with the generalized linear model concept, then by localizing. Distances between individuals are the only predictor information needed to fit these models. Therefore they are applicable to mixed (qualitative and quantitative) explanatory variables or when the regressor is of functional type. Models can be fitted and analysed with the R package dbstats, which implements several distancebased prediction methods.

E-MOVE project : a case of successfulcooperation of European academic librariesof distance teaching universities

El Library and Learning Support Working Group (LLSWG) és una xarxa europea de professionals de biblioteca i de la informació i educadors dins de l'Associació Europea d'Universitats d'Ensenyament (EADTU). EADTU és l'organització que representa tant les universitats obertes i d'ensenyament a distància com els consorcis nacionals d'institucions d'ensenyament superior actius en els camps d'educació de distància i e-learning. El 2005 l'Associació Europea d'Universitats d'Ensenyament de Distància (EADTU) presentava a la Comissió Europea una proposta de projecte sobre Mobilitat Virtual anomenada E-MOVE. El projecte incloïa, entre d'altres, un paquet de treball referent a biblioteca i suport a l'aprenentatge al context de mobilitat virtual. Aquest fou desenvolupat pel LLSWG de l'EADTU.

Adaptive intelligent agent approach to guide the web navigation on the PLAN-G distance learning platform

Hypermedia systems based on the Web for open distance education are becoming increasinglypopular as tools for user-driven access learning information. Adaptive hypermedia is a new direction in research within the area of user-adaptive systems, to increase its functionality by making it personalized [Eklu 961. This paper sketches a general agents architecture to include navigationaladaptability and user-friendly processes which would guide and accompany the student during hislher learning on the PLAN-G hypermedia system (New Generation Telematics Platform to Support Open and Distance Learning), with the aid of computer networks and specifically WWW technology [Marz 98-1] [Marz 98-2]. The PLAN-G actual prototype is successfully used with some informatics courses (the current version has no agents yet). The propased multi-agent system, contains two different types of adaptive autonomous software agents: Personal Digital Agents {Interface), to interacl directly with the student when necessary; and Information Agents (Intermediaries), to filtrate and discover information to learn and to adapt navigation space to a specific student

Clustering algorithms for anti-money laundering using graph theory and social network analysis

HEMOLIA (a project under European community’s 7th framework programme) is a new generation Anti-Money Laundering (AML) intelligent multi-agent alert and investigation system which in addition to the traditional financial data makes extensive use of modern society’s huge telecom data source, thereby opening up a new dimension of capabilities to all Money Laundering fighters (FIUs, LEAs) and Financial Institutes (Banks, Insurance Companies, etc.). This Master-Thesis project is done at AIA, one of the partners for the HEMOLIA project in Barcelona. The objective of this thesis is to find the clusters in a network drawn by using the financial data. An extensive literature survey has been carried out and several standard algorithms related to networks have been studied and implemented. The clustering problem is a NP-hard problem and several algorithms like K-Means and Hierarchical clustering are being implemented for studying several problems relating to sociology, evolution, anthropology etc. However, these algorithms have certain drawbacks which make them very difficult to implement. The thesis suggests (a) a possible improvement to the K-Means algorithm, (b) a novel approach to the clustering problem using the Genetic Algorithms and (c) a new algorithm for finding the cluster of a node using the Genetic Algorithm.

Chaos and order in the contemporary city. The impact of urban spatial structure on population density and commuting distance in Barcelona, 1986-2001.

One of the criticisms leveled at the model of dispersed city found all over the world is its unarticulated, random, and undifferentiated nature. To check this idea in the Barcelona Metropolitan Region, we estimated the impact of the urban spatial structure (CBD, subcenters and transportation infrastructures) over the population density and commuting distance. The results are unfavorable to the hypothesis of the increasing destructuring of cities given that the explanatory capacity of both functions improves over time, both when other control variables are not included and when they are included.