کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
6853046 1436975 2018 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The complexity landscape of decompositional parameters for ILP
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر هوش مصنوعی
پیش نمایش صفحه اول مقاله
The complexity landscape of decompositional parameters for ILP
چکیده انگلیسی
In particular, we show that ILP is fixed-parameter tractable when parameterized by the treedepth of the constraint matrix and the maximum absolute value of any coefficient occurring in the ILP instance. Together with matching hardness results for the more general parameter treewidth, we give an overview of the complexity of ILP w.r.t. decompositional parameters defined on the constraint matrix.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Artificial Intelligence - Volume 257, April 2018, Pages 61-71
نویسندگان
, ,