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
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
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 .
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 .