## New Hardness Results for Diophantine Approximation

Research Area: Year: Algorithm Engineering for Real-time Scheduling and Routing 2009 In Proceedings Diophantine approximation; NP-hardness F. Eisenbrand; T. Rothvoß 5687 Proceedings of the 12th Intl. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2009) Lecture Notes in Computer Science 98-110 978-3-642-03684-2 @conference{EisenbrandRothvossDDA09, author = "F. Eisenbrand and T. Rothvo{\ss}", 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.", booktitle = "Proceedings of the 12th Intl. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2009)", doi = "10.1007/978-3-642-03685-9", isbn = "978-3-642-03684-2", keywords = "Diophantine approximation; NP-hardness", pages = "98--110", publisher = "Springer", series = "Lecture Notes in Computer Science", title = "{N}ew {H}ardness {R}esults for {D}iophantine {A}pproximation", url = "http://cui.unige.ch/tcs/random-approx/2009/index.php", volume = "5687", year = "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. Online version [Bibtex]
[ Back ]