Inapproximability results for the minimum integral solution problem with preprocessing over \(\ell_{\infty}\) norm

DOI10.1016/j.tcs.2013.01.028zbMath1281.68121OpenAlexW2021859828MaRDI QIDQ1951564

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

Publication date: 6 June 2013

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2013.01.028

zbMATH Keywords

computational complexityNP-hardnessPCPminimum integral solution problem

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (2)

Research on QoS service composition based on coevolutionary genetic algorithm ⋮ An improved lower bound for approximating the minimum integral solution problem with preprocessing over \(\ell_\infty\) norm

This page was built for publication: Inapproximability results for the minimum integral solution problem with preprocessing over \(\ell_{\infty}\) norm