New Hardness Results for Diophantine Approximation

DOI10.1007/978-3-642-03685-9_8zbMATH Open1254.68349OpenAlexW1852633567MaRDI QIDQ3638871FDOQ3638871

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

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

Mathematics Subject Classification ID

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

Cited In (7)

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

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)