An improved lower bound for approximating the minimum integral solution problem with preprocessing over \(\ell_\infty\) norm
From MaRDI portal
Publication:498420
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
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
