کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
418486 681674 2012 19 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A shortest path-based approach to the multileaf collimator sequencing problem
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
A shortest path-based approach to the multileaf collimator sequencing problem
چکیده انگلیسی

The multileaf collimator sequencing problem is an important component in effective cancer treatment delivery. The problem can be formulated as finding a decomposition of an integer matrix into a weighted sequence of binary matrices whose rows satisfy a consecutive ones property. Minimising the cardinality of the decomposition is an important objective and has been shown to be strongly NP-hard, even for a matrix restricted to a single column or row. We show that in this latter case it can be solved efficiently as a shortest path problem, giving a simple proof that the one-row problem is fixed-parameter tractable in the maximum intensity. We develop new linear and constraint programming models exploiting this result. Our approaches significantly improve the best known for the problem, bringing real-world sized problem instances within reach of exact algorithms.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 160, Issues 1–2, January 2012, Pages 81–99
نویسندگان
, , ,