کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10328701 | 684868 | 2005 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Data-independent neighborhood functions and strict local optima
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
The paper proves that data-independent neighborhood functions with the smooth property (all strict local optima are global optima) for maximum 3-satisfiability (MAX 3-SAT) must contain all possible solutions for large instances. Data-independent neighborhood functions with the smooth property for 0-1 knapsack are shown to have size with the same order of magnitude as the cardinality of the solution space. Data-independent neighborhood functions with the smooth property for traveling salesman problem (TSP) are shown to have exponential size. These results also hold for certain polynomially solvable sub-problems of MAX 3-SAT, 0-1 knapsack and TSP.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 146, Issue 3, 15 March 2005, Pages 233-243
Journal: Discrete Applied Mathematics - Volume 146, Issue 3, 15 March 2005, Pages 233-243
نویسندگان
Derek E. Armstrong, Sheldon H. Jacobson,