Computational approaches to a combinatorial optimization problem arising from text classification

Computational approaches to a combinatorial optimization problem arising from text classification

0.00 Avg rating0 Votes
Article ID: iaor20082772
Country: United Kingdom
Volume: 34
Issue: 7
Start Page Number: 1910
End Page Number: 1928
Publication Date: Jul 2007
Journal: Computers and Operations Research
Authors: ,
Keywords: lagrange multipliers, heuristics: local search, optimization: simulated annealing, combinatorial optimization
Abstract:

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 Accenting and Simulated Annealing.

Reviews

Required fields are marked *. Your email address will not be published.