Name
Abstract | ||
|---|---|---|
In this paper we study the suitability of the Metropolis Algorithm and its generalization for solving the shortest lattice vector problem (SVP). SVP has numerous applications spanning from robotics to computational number theory, viz., polynomial factorization. At the same time, SVP is a notoriously hard problem. Not only it is NP-hard, there is not even any polynomial approximation known for the problem that runs in polynomial time. What one normally uses is the LLL algorithm which, although a polynomial time algorithm, may give solutions which are an exponential factor away from the optimum. In this paper, we have defined an appropriate search space for the problem which we use for implementation of the Metropolis algorithm. We have defined a suitable neighbourhood structure which makes the diameter of the space polynomially bounded, and we ensure that each search point has only polynomially many neighbours. We can use this search space formulation for some other classes of evolutionary algorithms, e.g., for genetic and go-with-the-winner algorithms. We have implemented the Metropolis algorithm and Hasting's generalization of Metropolis algorithm for the SVP. Our results are quite encouraging in all instances when compared with LLL algorithm. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1109/HIS.2011.6122146 | HIS |
Keywords | Field | DocType |
np-hard,evolutionary algorithm,neighbourhood structure,search space,search space formulation,lll,go-with-the-winner algorithm,robotics,polynomial approximation,svp,polynomial time algorithm,polynomial factorization,genetic algorithm,genetic algorithms,metropolis algorithm,algorithm theory,hasting's generalization,shortest lattice vector problem,computational number theory,vectors,genetics,hybrid intelligent system,lattices,polynomials,information and communication technology,approximation algorithms,polynomial time | Approximation algorithm,Mathematical optimization,Evolutionary algorithm,Polynomial,Time complexity,Factorization of polynomials,Computational number theory,Genetic algorithm,Mathematics,Bounded function | Conference |
ISBN | Citations | PageRank |
978-1-4577-2151-9 | 1 | 0.37 |
References | Authors | |
3 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Shenoy K. B. Ajitha | 1 | 1 | 0.37 |
| Somenath Biswas | 2 | 111 | 11.34 |
| Piyush P. Kurur | 3 | 88 | 9.41 |