Use Multilevel Graph Partitioning Scheme to solve traveling salesman problem

The traveling salesman problem is although looking very simple problem but it is an important combinatorial problem. In this thesis I have tried to find the shortest distance tour in which each city is visited exactly one time and return to the starting city. I have tried to solve traveling salesman problem using multilevel graph partitioning approach.Although traveling salesman problem itself very difficult as this problem is belong to the NP-Complete problems but I have tried my best to solve this problem using multilevel graph partitioning it also belong to the NP-Complete problems. I have solved this thesis by using the k-mean partitioning algorithm which divides the problem into multiple partitions and solving each partition separately and its solution is used to improve the overall tour by applying Lin Kernighan algorithm on it. Through all this I got optimal solution which proofs that solving traveling salesman problem through graph partition scheme is good for this NP-Problem and through this we can solved this intractable problem within few minutes.Keywords: Graph Partitioning Scheme, Traveling Salesman Problem.

From the road network database to a graph for localization purposes

The problems of finding best facility locations require complete and accurate road network with the corresponding population data in a specific area. However the data obtained in road network databases usually do not fit in this usage. In this paper we propose our procedure of converting the road network database to a road graph which could be used in localization problems. The road network data come from the National road data base in Sweden. The graph derived is cleaned, and reduced to a suitable level for localization problems. The population points are also processed in ordered to match with that graph. The reduction of the graph is done maintaining most of the accuracy for distance measures in the network.

Informal sanctions and conditional cooperation: : A natural experiment on voluntary contributions to a public good.

In a natural experiment, this paper studies the impact of an informal sanctioning mechanism on individuals’ voluntary contribution to a public good. Cross-country skiers’ actual cash contributions in two ski resorts, one with and one without an informal sanctioning system, are used. I find the contributing share to be higher in the informal sanctioning system (79 percent) than in the non-sanctioning system (36 percent). Previous studies in one-shot public good situations have found an increasing conditional contribution (CC) function, i.e. the relationship between expected average contributions of other group members and the individual’s own contribution. In contrast, the present results suggest that the CC-function in the non-sanctioning system is non-increasing at high perceived levels of others’ contribution. This relationship deserves further testing in lab.

Fitting conditional and simultaneous autoregressive spatial models in hglm

We present a new version (> 2.0) of the hglm package for fitting hierarchical generalized linear models (HGLMs) with spatially correlated random effects. CAR() and SAR() families for conditional and simultaneous autoregressive random effects were implemented. Eigen decomposition of the matrix describing the spatial structure (e.g., the neighborhood matrix) was used to transform the CAR/SAR random effects into an independent, but eteroscedastic, Gaussian random effect. A linear predictor is fitted for the random effect variance to estimate the parameters in the CAR and SAR models. This gives a computationally efficient algorithm for moderately sized problems.