An improved lower bound for approximating the minimum integral solution problem with preprocessing over \(\ell_\infty\) norm

DOI10.1007/s10878-013-9646-4zbMath1331.90064OpenAlexW1980968159MaRDI QIDQ498420

Jian-Xiong Wang, Wei Xiong, Maobin Tang, Lingxi Peng, Fufang Li, Songtao Wang, Wenbin Chen

Publication date: 28 September 2015

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-013-9646-4

zbMATH Keywords

computational complexityNP-hardnessPCPminimum integral solution problem

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Hardness of approximating the closest vector problem with pre-processing
• Approximate solution of NP optimization problems
• An improved lower bound for approximating minimum GCD multiplier in \(\ell _\infty \) norm (GCDM\(_\infty\))
• The hardness of approximate optima in lattices, codes, and systems of linear equations
• Approximating CVP to within almost-polynomial factors is NP-hard
• The inapproximability of lattice and coding problems with preprocessing
• Inapproximability results for the minimum integral solution problem with preprocessing over \(\ell_{\infty}\) norm
• Lattice problems and norm embeddings
• The hardness of decoding linear codes with preprocessing
• The Hardness of the Closest Vector Problem With Preprocessing Over$ell_infty$Norm
• Interactive proofs and the hardness of approximating cliques
• The hardness of the closest vector problem with preprocessing
• Efficient probabilistically checkable proofs and applications to approximations
• The hardness of solving subset sum with preprocessing

This page was built for publication: An improved lower bound for approximating the minimum integral solution problem with preprocessing over \(\ell_\infty\) norm