We study a combinatorial optimization problem related to the automatic classification of texts. The problem consists of covering a given text using strings from a given set, where a cost is incurred for each type of string used. We give a 0-1 linear programming formulation and we report on computational experiences on very large instances using two different Lagrangean relaxations and heuristic algorithms based on simulated annealing and threshold accepting.
A combinatorial optimization problem arising from text classification / S. Bosio, G. Righini. - In: ELECTRONIC NOTES IN DISCRETE MATHEMATICS. - ISSN 1571-0653. - 13:(2003 Apr), pp. 22-25. ((Intervento presentato al 2. convegno Cologne-Twente Workshop on Graphs and Combinatorial Optimization tenutosi a Enschede, Netherlands nel 2003 [10.1016/S1571-0653(04)00429-9].
A combinatorial optimization problem arising from text classification
G. Righini
2003
Abstract
We study a combinatorial optimization problem related to the automatic classification of texts. The problem consists of covering a given text using strings from a given set, where a cost is incurred for each type of string used. We give a 0-1 linear programming formulation and we report on computational experiences on very large instances using two different Lagrangean relaxations and heuristic algorithms based on simulated annealing and threshold accepting.Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.