BulDML at Institute of Mathematics and Informatics >
IMI Periodicals >
Serdica Journal of Computing >
2012 >
Volume 6 Number 4 >

Please use this identifier to cite or link to this item:

Title: A Variable Neighborhood Search Approach for Solving the Maximum Set Splitting Problem
Authors: Matic, Dragan
Keywords: Variable Neighborhood Search
Combinatorial Optimization
Maximum Set Splitting Problem
2-Coloring of the Hypergraph
Steiner Triple Systems
Issue Date: 2012
Publisher: Institute of Mathematics and Informatics Bulgarian Academy of Sciences
Citation: Serdica Journal of Computing, Vol. 6, No 4, (2012), 369p-384p
Abstract: This paper presents a Variable neighbourhood search (VNS) approach for solving the Maximum Set Splitting Problem (MSSP). The algorithm forms a system of neighborhoods based on changing the component for an increasing number of elements. An efficient local search procedure swaps the components of pairs of elements and yields a relatively short running time. Numerical experiments are performed on the instances known in the literature: minimum hitting set and Steiner triple systems. Computational results show that the proposed VNS achieves all optimal or best known solutions in short times. The experiments indicate that the VNS compares favorably with other methods previously used for solving the MSSP. ACM Computing Classification System (1998): I.2.8.
ISSN: 1312-6555
Appears in Collections:Volume 6 Number 4

Files in This Item:

File Description SizeFormat
sjc-vol6-num4-2012-p369-p384.pdf186.68 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.


Valid XHTML 1.0!   Creative Commons License