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.

5CN05 partitioning in an aqueous two-phase system: A new approach to the solubilization of hydrophobic drugs

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)

Generating unconstrained two-dimensional non-guillotine cutting patterns by a Recursive Partitioning Algorithm

In this study, a dynamic programming approach to deal with the unconstrained two-dimensional non-guillotine cutting problem is presented. The method extends the recently introduced recursive partitioning approach for the manufacturer's pallet loading problem. The approach involves two phases and uses bounds based on unconstrained two-staged and non-staged guillotine cutting. The method is able to find the optimal cutting pattern of a large number of pro blem instances of moderate sizes known in the literature and a counterexample for which the approach fails to find known optimal solutions was not found. For the instances that the required computer runtime is excessive, the approach is combined with simple heuristics to reduce its running time. Detailed numerical experiments show the reliability of the method. Journal of the Operational Research Society (2012) 63, 183-200. doi: 10.1057/jors.2011.6 Published online 17 August 2011

Clutch-size adjustments and skew models: effects on reproductive partitioning and group stability

Reproductive skew theory seeks to integrate social and ecological factors thought to influence the division of reproduction among group-living animals. However, most reproductive skew models only examine interactions between individuals of the same sex. Here, we suggest that females can influence group stability and conflict among males by modifying their clutch size and may do so if they benefit from the presence of subordinate male helpers or from reduced conflict. We develop 3 models, based on concessions-based, restraint, and tug-of-war models, in which female clutch size is variable and ask when females will increase their clutch size above that which would be optimal in the absence of male-male conflict. In concessions-based and restraint models, females should increase clutch size above their optima if the benefits of staying for subordinate males are relatively low. Relatedness between males has no effect on clutch size. When females do increase clutch size, the division of reproduction between males is not influenced by relatedness and does not differ between restraint and concessions-based models. Both of these predictions are in sharp contrast to previous models. In tug-of-war models, clutch size is strongly influenced by relatedness between males, with the largest clutches, but the fewest surviving offspring, produced when males are unrelated. These 3 models demonstrate the importance of considering third-party interests in the decisions of group-living organisms.

Postseptational chromosome partitioning in bacteria.

Mutations in the spoIIIE gene prevent proper partitioning of one chromosome into the developing prespore during sporulation but have no overt effect on partitioning in vegetatively dividing cells. However, the expression of spoIIIE in vegetative cells and the occurrence of genes closely related to spoIIIE in a range of nonsporulating eubacteria suggested a more general function for the protein. Here we show that SpoIIIE protein is needed for optimal chromosome partitioning in vegetative cells of Bacillus subtilis when the normal tight coordination between septation and nucleoid partitioning is perturbed or when septum positioning is altered. A functional SpoIIIE protein allows cells to recover from a state in which their chromosome has been trapped by a closing septum. By analogy to its function during sporulation, we suggest that SpoIIIE facilitates partitioning by actively translocating the chromosome out of the septum. In addition to enhancing the fidelity of nucleoid partitioning, SpoIIIE also seems to be required for maximal resistance to antibiotics that interfere with DNA metabolism. The results have important implications for our understanding of the functions of genes involved in the primary partitioning machinery in bacteria and of how septum placement is controlled.

Identifying optimal lipid raft characteristics required to promote nanoscale protein-protein interactions on the plasma membrane

The dynamic lateral segregation of signaling proteins into microdomains is proposed to facilitate signal transduction, but the constraints on microdomain size, mobility, and diffusion that might realize this function are undefined. Here we interrogate a stochastic spatial model of the plasma membrane to determine how microdomains affect protein dynamics. Taking lipid rafts as representative microdomains, we show that reduced protein mobility in rafts segregates dynamically partitioning proteins, but the equilibrium concentration is largely independent of raft size and mobility. Rafts weakly impede small-scale protein diffusion but more strongly impede long-range protein mobility. The long-range mobility of raft-partitioning and raft-excluded proteins, however, is reduced to a similar extent. Dynamic partitioning into rafts increases specific interprotein collision rates, but to maximize this critical, biologically relevant function, rafts must be small (diameter, 6 to 14 nm) and mobile. Intermolecular collisions can also be favored by the selective capture and exclusion of proteins by rafts, although this mechanism is generally less efficient than simple dynamic partitioning. Generalizing these results, we conclude that microdomains can readily operate as protein concentrators or isolators but there appear to be significant constraints on size and mobility if microdomains are also required to function as reaction chambers that facilitate nanoscale protein-protein interactions. These results may have significant implications for the many signaling cascades that are scaffolded or assembled in plasma membrane microdomains.

Robust H.264/AVC video transmission using data partitioning and unequal loss protection

In this work, we present an adaptive unequal loss protection (ULP) scheme for H264/AVC video transmission over lossy networks. This scheme combines erasure coding, H.264/AVC error resilience techniques and importance measures in video coding. The unequal importance of the video packets is identified in the group of pictures (GOP) and the H.264/AVC data partitioning levels. The presented method can adaptively assign unequal amount of forward error correction (FEC) parity across the video packets according to the network conditions, such as the available network bandwidth, packet loss rate and average packet burst loss length. A near optimal algorithm is developed to deal with the FEC assignment for optimization. The simulation results show that our scheme can effectively utilize network resources such as bandwidth, while improving the quality of the video transmission. In addition, the proposed ULP strategy ensures graceful degradation of the received video quality as the packet loss rate increases. © 2010 IEEE.