# New Hardness Results for Diophantine Approximation

Presented at: 12th Intl. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX '09), UC Berkeley, USA, August 21-23, 2009 Published in: 12th Intl. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX '09), p. 98--110 Series: Lecture Notes in Computer Science 5687 Berlin: Springer, 2009

We revisit simultaneous diophantine approximation, a classical problem from the geometry of numbers which has many applications in algorithms and complexity. The input of the decision version of this problem consists of a rational vector \alpha, an error bound \epsilon and a denominator bound N. One has to decide whether there exists an integer, called the denominator Q with 1 <= Q <= N such that the distance of each number Q*\alpha_i to its nearest integer is bounded by \epsilon. Lagarias has shown that this problem is NP-complete and optimization versions have been shown to be hard to approximate within a factor n^{c/ \log \log n} for some constant c > 0. We strengthen the existing hardness results and show that the optimization problem of finding the smallest denominator Q such that the distances of Q*\alpha_i to the nearest integer is bounded by \epsilon is hard to aproximate within a factor 2^n unless P=NP. We then outline two further applications of this strengthening: We show that a directed version of Diophantine approximation is also hard to approximate. Furthermore we prove that the mixing set problem with arbitrary capacities is NP-hard. This solves an open problem raised by Conforti, Di Summa and Wolsey.

Keywords: Diophantine approximation ; NP-hardness Reference DISOPT-CONF-2009-005doi:10.1007/978-3-642-03685-9View record in Web of Science

Author: Eisenbrand, Friedrich; Rothvoß, Thomas

Source: https://infoscience.epfl.ch/record/138777?ln=en