کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4950860 | 1441035 | 2017 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Arboral satisfaction: Recognition and LP approximation
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
We study two basic problems about arboral satisfaction. First, we develop two nontrivial algorithms to test whether a given point set is arborally satisfied. In 2D, both of our algorithms run in O(nlogâ¡n) time, and one of them achieves O(n) runtime if the points are presorted; we also show a matching Ω(nlogâ¡n) lower bound in the algebraic decision tree model. In d dimensions, our algorithm runs in O(dnlogâ¡n+nlogdâ1â¡n) time. Second, we study a natural integer linear programming formulation of finding the minimum-size arborally satisfied superset of a given 2D point set, which is equivalent to finding offline dynamically optimal binary search trees. Unfortunately, we conclude that the linear programming relaxation has large integrality gap, making it unlikely to find an approximation algorithm via this approach.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Processing Letters - Volume 127, November 2017, Pages 1-5
Journal: Information Processing Letters - Volume 127, November 2017, Pages 1-5
نویسندگان
Erik D. Demaine, Varun Ganesan, Vladislav Kontsevoi, Qipeng Liu, Quanquan Liu, Fermi Ma, Ofir Nachum, Aaron Sidford, Erik Waingarten, Daniel Ziegler,