Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA O(n^8) X O(n^7) Linear Programming Model of the Traveling Salesman Problem
164
0
0.0
(
0
)
Added by
Moustapha Diaby
Publication date
2016
fields
Informatics Engineering
and research's language is
English
Authors
Moustapha Diaby
Ask ChatGPT about the research
No Arabic abstract
In this paper, we present a new linear programming (LP) formulation of the Traveling Salesman Problem (TSP). The proposed model has O(n^8) variables and O(n^7) constraints, where n is the number of cities. Our numerical experimentation shows that computational times for the proposed linear program are several orders of magnitude smaller than those for the existing model [3].
rate research
Read More
This paper has been withdrawn because Theorem 21 and Corollary 22 are in error; The modeling idea is OK, but it needs 9-dimensional variables instead of the 8-dimensional variables defined in notations 6.9. Examples of the correct model (with 9-index variables) are: (1) Diaby, M., Linear Programming Formulation of the Set Partitioning Problem, International Journal of Operational Research 8:4 (August 2010) pp. 399-427; (2) Diaby, M., Linear Programming Formulation of the Vertex Coloring Problem, International Journal of Mathematics in Operational Research 2:3 (May 2010) pp. 259-289; (3) Diaby, M., The Traveling Salesman Problem: A Linear Programming Formulation, WSEAS Transactions on Mathematics, 6:6 (June 2007) pp. 745-754.
Three related analyses of $phi^4$ theory with $O(N)$ symmetry are presented. In the first, we review the $O(N)$ model over the $p$-adic numbers and the discrete renormalization group transformations which can be understood as spin blocking in an ultrametric context. We demonstrate the existence of a Wilson-Fisher fixed point using an $epsilon$ expansion, and we show how to obtain leading order results for the anomalous dimensions of low dimension operators near the fixed point. Along the way, we note an important aspect of ultrametric field theories, which is a non-renormalization theorem for kinetic terms. In the second analysis, we employ large $N$ methods to establish formulas for anomalous dimensions which are valid equally for field theories over the $p$-adic numbers and field theories on $mathbb{R}^n$. Results for anomalous dimensions agree between the first and second analyses when they can be meaningfully compared. In the third analysis, we consider higher derivativ
We determine, for the first time, the scaling dimensions of a family of fixed-charge operators stemming from the critical $O(N)$ model in 4-$epsilon$ dimensions to the leading and next to leading order terms in the charge expansion but to all-orders in the coupling. We test our results to the maximum known order in perturbation theory while determining higher order terms.
In this paper, we present a new, graph-based modeling approach and a polynomial-sized linear programming (LP) formulation of the Boolean satisfiability problem (SAT). The approach is illustrated with a numerical example.
A new characterisation of Hamiltonian graphs using f-cutset matrix is proposed. A new exact polynomial time algorithm for the travelling salesman problem (TSP) based on this new characterisation is developed. We then define so called ordered weighted adjacency list for given weighted complete graph and proceed to the main result of the paper, namely, the exact algorithm based on utilisation of ordered weighted adjacency list and the simple properties that any path or circuit must satisfy. This algorithm performs checking of sub-lists, containing (p-1) entries (edge pairs) for paths and p entries (edge pairs) for circuits, chosen from ordered adjacency list in a well defined sequence to determine exactly the shortest Hamiltonian path and shortest Hamiltonian circuit in a weighted complete graph of p vertices. The procedure has intrinsic advantage of landing on the desired solution in quickest possible time and even in worst case in polynomial time. A new characterisation of shortest Hamiltonian tour for a weighted complete graph satisfying triangle inequality (i.e. for tours passing through every city on a realistic map of cities where cities can be taken as points on a Euclidean plane) is also proposed. Finally, we propose a classical algorithm for unstructured search and also three new quantum algorithms for unstructured search which exponentially speed up the searching ability in the unstructured database and discuss its effect on the NP-Complete problems.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
