New Hardness Results for Diophantine Approximation

DOI10.1007/978-3-642-03685-9_8MaRDI QIDQ3638871zbMATHOpenAlexFDO

Authors Friedrich Eisenbrand, Thomas Rothvoß

Publication date 28 October 2009

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL http://cui.unige.ch/tcs/random-approx/2009/index.php

Mathematics Subject Classification ID

Randomized algorithms (68W20) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Recommendations

• scientific article; zbMATH DE number 1114048
• The hardness of approximate optima in lattices, codes, and systems of linear equations
• The Computational Complexity of Simultaneous Diophantine Approximation Problems
• Complexity of lattice problems. Non-approximability and limits of non-approximability
• Simultaneous diophantine approximation

Cited in

(7)

• About the Structure of the Integer Cone and Its Application to Bin Packing
• Hardness of approximating the minimum solutions of linear Diophantine equations
• The computational complexity of integer programming with alternations
• Mixing polyhedra with two non divisible coefficients
• An improved lower bound for approximating shortest integer relation in \(\ell _{\infty }\) norm \((SIR_{\infty })\)
• The Computational Complexity of Simultaneous Diophantine Approximation Problems
• The mixing set with divisible capacities: a simple approach

This page was built for publication: New Hardness Results for Diophantine Approximation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3638871)