An electromagnetism-like method for the maximum set splitting problem
DOI:
https://doi.org/10.2298/YJOR110704010KKeywords:
electromagnetism-like metaheuristic, combinatorial optimization, maximum set splitting problem, Steiner triple systemsAbstract
In this paper, an electromagnetism-like approach (EM) for solving the maximum set splitting problem (MSSP) is applied. Hybrid approach consisting of the movement based on the attraction-repulsion mechanisms combined with the proposed scaling technique directs EM to promising search regions. Fast implementation of the local search procedure additionally improves the efficiency of overall EM system. The performance of the proposed EM approach is evaluated on two classes of instances from the literature: minimum hitting set and Steiner triple systems. The results show, except in one case, that EM reaches optimal solutions up to 500 elements and 50000 subsets on minimum hitting set instances. It also reaches all optimal/best-known solutions for Steiner triple systems.References
Ali, M.M., Golalikhani, M., "An electromagnetism-like method for nonlinearly constrained global optimization", Computers & Mathematics with Applications, 60(8) (2010) 2279-2285.
Andersson, G., and Engebretsen, L., "Better approximation algorithms for set splitting and not-all-equal sat", Information Processing Letters, 65 (1998) 305-311.
Birbil, S.I., and Fang, S.C, "An electromagnetism-like mechanism for global optimization", Journal of Global Optimization, 25 (2003), 263-282.
Chen, J., and Lu, S., "Improved algorithm for weighted and unweighted set splitting problems", Lecture Notes in Computer Science, 4598 (2007) 573-547.
Chen, H., and Lu, S., "Improved parameterized set splitting algorithms: A probabilistic approach", Algorithmica, 54 (2009) 472-489.
Cutello, V., and Nicosia, G., "A clonal selection algorithm for coloring, hitting set and satisfiability problems", Lecture Notes in Computer Science, 3931 (2006) 324-337.
Dehne, F., Fellows, M. and Rosamond, F., "An FPT algorithm for set splitting", Lecture Notes in Computer Science, 2880 (2003) 180-191.
Dehne, F., Fellows, M., Rosamond, F., and Shaw, P., "Greedy localization, iterative compression, modeled crown reductions: New FPT techniques, and improved algorithm for set splitting, and a novel 2k kernelization of vertex cover", Lecture Notes in Computer Science, 162 (2004) 127-137.
Fulkerson, D. R., Nemhauser, G.L. and Trotter, L.E., "Two computationally difficult set covering problems that arise in computing the l-width of incidence matrices of Steiner triple systems", Mathematical Programming Study, 2 (1974) 72-81.
Garcia-Villoria, A., and Moreno R.P., "Solving the response time variability problem by means of the electromagnetism-like mechanism", International Journal of Production Research, 48(22) (2010) 6701-6714.
Garey, M., and Johnson, D., Computers and Intractability: A Guide to the Theory of NP Completeness, Freeman, San Francisco, 1979.
Guan, X., Dai, X., Li, J., "Revised electromagnetism-like mechanism for flow path design of unidirectional AGV systems", International Journal of Production Research, 49(2) (2011) 401-429.
Guruswami, V., "Inapproximability results for set splitting and satisfiability problems with no mixed clauses", Lecture Notes in Computer Science, 1913 (2000) 155-166.
Kartelj, A., "Electromagnetism metaheuristic algorithm for solving the strong minimum energy topology problem", submitted to Yugoslav Journal of Operations Research.
Larson, P.B., and Shelah, S., "The stationary set splitting game", Mathematical Logic Quarterly, 54(2) (2008) 187-193.
Lazović, B., Marić, M., Filipović, V., and Savić, A., "An integer linear programming formulation and genetic algorithm for the maximum set splitting problem", Publications de l'Institut Mathematique, in press.
Lokshtanov, D., and Saurabh, S., "Even faster algorithm for set splitting!", Proceedings of the International Workshop on Parameterized and Exact Computation - IWPEC 2009, 288-299.
Lu, S., “Randomized and deterministic parameterized algorithms and their applications in bioinformatics”, Ph. D. thesis, Texas A&M University, 2009.
Nederlof, J., and van Rooij, J.M.M., "Inclusion/exclusion branching for partial dominating set and set splitting", Lecture Notes in Computer Science, 6478 (2010) 204-215.
Tsai, C.Y., Hung, H.L., Lee S.H., "Electromagnetism-like method based blind multiuser detection for MC-CDMA interference suppression over multipath fading channel", Proceedings of the IEEE International Symposium on Computer Communication Control and Automation -3CA, 2010, 470-475.
Zhang, J., Ye, Y., and Han, Q., "Improved approximations for max set splitting and max NAE SAT", Discrete Applied Mathematics, 142 (2004) 133-149.
Downloads
Published
Issue
Section
License
Copyright (c) 2013 YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
