学术报告： Bounding the Sum of Square Roots via Lattice Reduction

题目：Bounding the Sum of Square Roots via Lattice Reduction

报告人：Qi Cheng

时间：2012-07-03 (Tuesday) 10:00-11:00

地点：4303（会议室）

报告内容摘要：

Let k and n be positive integers. Define R(n, k) to be the minimum positive value of $e_1 \sqrt{s_1} + ... + e_k \sqrt{s_k} -t | $ where $s_1, s_2, · · · , s_k$ are positive integers no larger than n, t is an integer and $e_i \in {1, 0, −1}$ for all 1 ≤ i ≤ k. It is important in computational geometry to determine a good lower and upper bound of R(n, k). In this talk we will present an algorithm to find lower bounds based on lattice reduction algorithms. It produces lower bounds much better than the root separation technique does.