کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
476274 699437 2007 19 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Computational approaches to a combinatorial optimization problem arising from text classification
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
Computational approaches to a combinatorial optimization problem arising from text classification
چکیده انگلیسی

We present a combinatorial optimization problem with a particular cost structure: a constrained set of elements must be chosen from a ground set and the ground set is partitioned into subsets corresponding to types of elements. The constraints concern the elements, whereas the solution cost does not depend on the elements but only on their types. The motivation of this study comes from text categorization but we believe that the same combinatorial structure may emerge in many different contexts. We prove that the problem is NP-hard. We give a 0–1 linear programming formulation and we report on computational experiences on very large instances using branch-and-bound algorithms based on two different Lagrangean relaxations and heuristic algorithms based on Threshold Accepting and Simulated Annealing.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Operations Research - Volume 34, Issue 7, July 2007, Pages 1910–1928
نویسندگان
, ,