Two open problems in communication in edge-disjoint paths modes
Improved lower bounds on the approximability of the traveling salesman problem
A weighted HP model for protein folding with diagonal contacts
The HP model is one of the most popular discretized models for attacking the protein folding problem, , for the computational prediction of the tertiary structure of a protein from its amino acid sequence. It is based on the assumption that interactions between hydrophobic amino acids are the main force in the folding process. Therefore, it distinguishes between polar and hydrophobic amino acids only and tries to embed the amino acid sequence into a two- or three-dimensional grid lattice such...
Improved Lower Bounds on the Approximability of the Traveling Salesman Problem
This paper deals with lower bounds on the approximability of different subproblems of the Traveling Salesman Problem (TSP) which is known not to admit any polynomial time approximation algorithm in general (unless ). First of all, we present an improved lower bound for the Traveling Salesman Problem with Triangle Inequality, -TSP for short. Moreover our technique, an extension of the method of Engebretsen [11], also applies to the case of relaxed and sharpened triangle inequality, respectively,...
The Uniform Minimum-Ones 2SAT Problem and its Application to Haplotype Classification
Analyzing genomic data for finding those gene variations which are responsible for hereditary diseases is one of the great challenges in modern bioinformatics. In many living beings (including the human), every gene is present in two copies, inherited from the two parents, the so-called . In this paper, we propose a simple combinatorial model for classifying the set of haplotypes in a population according to their responsibility for a certain genetic disease. This model is based on the minimum-ones...
Page 1