## New Hardness Results for Diophantine Approximation

Research Area: | Algorithm Engineering for Real-time Scheduling and Routing | Year: | 2009 | ||
---|---|---|---|---|---|

Type of Publication: | In Proceedings | Keywords: | Diophantine approximation; NP-hardness | ||

Authors: | F. Eisenbrand; T. Rothvoß | ||||

Volume: | 5687 | ||||

Book title: | Proceedings of the 12th Intl. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2009) | ||||

Series: | Lecture Notes in Computer Science | Pages: | 98-110 | ||

ISBN: | 978-3-642-03684-2 | ||||

BibTex: |
|||||

Abstract: | 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. |
||||

[Bibtex] |