An improved lower bound for approximating the Minimum Integral Solution Problem with Preprocessing over $$\ell _\infty $$ ℓ ∞ norm

Wenbin Chen (), Lingxi Peng, Jianxiong Wang, Fufang Li, Maobin Tang, Wei Xiong and Songtao Wang
Additional contact information
Wenbin Chen: Guangzhou University
Lingxi Peng: Guangzhou University
Jianxiong Wang: Guangzhou University
Fufang Li: Guangzhou University
Maobin Tang: Guangzhou University
Wei Xiong: Guangzhou University
Songtao Wang: South China Normal University

Journal of Combinatorial Optimization, 2015, vol. 30, issue 3, No 4, 447-455

Abstract: Abstract In this paper, we study the approximation complexity of the Minimum Integral Solution Problem with Preprocessing introduced by Alekhnovich et al. (FOCS, pp. 216–225, 2005). We show that the Minimum Integral Solution Problem with Preprocessing over $$\ell _\infty $$ ℓ ∞ norm ( $$\hbox {MISPP}_\infty $$ MISPP ∞ ) is NP-hard to approximate to within a factor of $$(\log n)^{1/2-\epsilon },$$ ( log n ) 1 / 2 - ϵ , unless $$\mathbf{NP}\subseteq \mathbf{DTIME}(2^{poly log(n)}).$$ NP ⊆ DTIME ( 2 p o l y l o g ( n ) ) . This improves on the best previous result. The best result so far gave $$\sqrt{2}-\epsilon $$ 2 - ϵ factor hardness for any $$\epsilon >0.$$ ϵ > 0 .

Keywords: Minimum Integral Solution Problem; Computational complexity; NP-hardness; PCP (search for similar items in EconPapers)
Date: 2015
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-013-9646-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:30:y:2015:i:3:d:10.1007_s10878-013-9646-4

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-013-9646-4

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().