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.

Small-Scale Farmers Land Use and Socioeconomic Situation in the Mount Elgon District in Northwestern Kenya : A Minor Field Study - Combined Field Mapping and Interview

This Minor Field Study was carried out during November and December in 2011 in the Mount Elgon District in Western Kenya. The objective was to examine nine small-scale farming household´s land use and socioeconomic situation when they have joined a non-governmental organization (NGO) project, which specifically targets small-scale farming households to improve land use system and socioeconomic situation by the extension of soil and water conservation measures. The survey has worked along three integral examinations methods which are mapping and processing data using GIS, semi structured interviews and literature studies.   This study has adopted a theoretical approach referred to as political ecology, in which landesque capital is a central concept. The result shows that all farmers, except one, have issues with land degradation. However, the extent of the problem and also implemented sustainable soil and water conservation measures were diverse among the farmers. The main causes of this can both be linked to how the farmers themselves utilized their farmland and how impacts from the climate change have modified the terms of the farmers working conditions. These factors have consequently resulted in impacts on the informants’ socioeconomic conditions. Furthermore it was also registered that social and economic elements, in some cases, were the causes of how the farmers manage their farmland. The farmer who had no significant problem with soil erosion had invested in trees and opportunities to irrigate the farmland. In addition, it was also recorded that certain farmers had invested in particular soil and water conservation measures without any significant result. This was probably due to the time span these land measures cover before they start to generate revenue.  The outcome of this study has traced how global, national and local elements exist in a context when it comes to the conditions of the farmers´ land use and their socioeconomic situation. The farmers atMt.Elgon are thereby a component of a wider context when they are both contributory to their socioeconomic situation, mainly due to their land management, and also exposed to core-periphery relationships on which the farmers themselves have no influence.