logo móvil
Contáctanos

Algoritmos de tamizado demostrable más rápidos para el problema del vector más corto y el problema del vector más cercano en retículos en norma

Autores: Mukhopadhyay, Priyanka

Idioma: Inglés

Editor: MDPI

Año: 2021

Descargar PDF

Acceso abierto

Artículo científico
2021

Algoritmos de tamizado demostrable más rápidos para el problema del vector más corto y el problema del vector más cercano en retículos en norma


Categoría

Ingeniería y Tecnología

Subcategoría

Ingeniería de Software

Palabras clave

Algoritmos de tamizado demostrables
Problema del Vector Más Corto
Problema del Vector Más Cercano
Retículos
Procedimiento de tamizado lineal
Procedimiento de tamizado mixto

Licencia

CC BY-SA – Atribución – Compartir Igual

Consultas: 29

Citaciones: Sin citaciones


Descripción
En este trabajo, presentamos algoritmos de tamizado demostrables para el Problema del Vector más Corto (SVP) y el Problema del Vector más Cercano (CVP) en retículos en la norma (). El tiempo de ejecución que obtenemos es mejor que los algoritmos de tamizado demostrables existentes. Presentamos un nuevo procedimiento de tamizado lineal que funciona para todas las normas (). La idea principal es dividir el espacio en hipercubos de manera que cada vector pueda ser mapeado eficientemente a una subregión. Logramos una complejidad temporal de , que es mucho menor que la complejidad del mejor algoritmo anterior. También introducimos un procedimiento de tamizado mixto, donde un punto es mapeado a un hipercubo dentro de una bola y luego se realiza un tamizado cuadrático dentro de cada hipercubo. Esto mejora el tiempo de ejecución, especialmente en la norma, donde logramos una complejidad temporal de , mientras que el algoritmo de Lista de Cumpleaños del Tamizado tiene un tiempo de ejecución de . Adoptamos nuestras técnicas de tamizado para algoritmos de aproximación para SVP y CVP en la norma () y mostramos que nuestro algoritmo tiene un tiempo de ejecución de , mientras que los algoritmos anteriores tienen una complejidad temporal de .

Otros recursos que podrían interesarte

Temas Virtualpro