SEMI-ANALYTICAL APPROXIMATION OF THE SET PARTITION PROBLEM USING THE HOMOTOPY ANALYSIS METHOD
Far East Journal of Mathematical Sciences (FJMS) · 06.08.2026 · 143 (9) · 3243-3259
DOI: 10.17654/0972087126178 ↗Kurz gefasst
Fachartikel in der Zeitschrift Far East Journal of Mathematical Sciences (FJMS), online erschienen am 06.08.2026. Verfasst von Patrick Linker und 1 weiteren Autor:innen. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
The Set Partition Problem (SPP) is a classical NP-hard combinatorial optimization problem with applications in scheduling, resource allocation, cryptography, and operations research. In this work, a semi-analytical framework based on the Homotopy Analysis Method (HAM) is developed for approximating solutions of the SPP. The discrete partitioning problem is first reformulated as a constrained continuous optimization problem using Lagrange multipliers. A homotopy is then constructed between an initial guess and the full nonlinear system, and a Padé $[1, 1]$ series representation is employed to obtain approximate analytical solutions. The resulting algebraic equations are solved up to second order in the homotopy parameter, and the explicit Taylor-series derivation of these equations is given, together with a discussion of the conditions under which the resulting linear system for the Padé coefficients becomes degenerate. A numerical example involving a six-element set is investigated, and the influence of the convergence-control parameter on a constraint-violation residual is analyzed statistically over multiple random initial guesses, using a statistically motivated outlier criterion. The results show that the residual varies non-monotonically with the convergence-control parameter, with no clearly defined convergence region, and that the rounded partition assignments obtained from the second-order Padé approximation fail to satisfy the exact partition condition for the tested samples. The study illustrates the potential and, in its present second-order form, the significant limitations of semi-analytical homotopy techniques when applied to NP-hard combinatorial optimization problems. Furthermore, it identifies higher-order approximations and pole-avoidance strategies as necessary directions for improvement.
Zitieren
APA
Linker, P., & Ozel, C. (2026). SEMI-ANALYTICAL APPROXIMATION OF THE SET PARTITION PROBLEM USING THE HOMOTOPY ANALYSIS METHOD. Far East Journal of Mathematical Sciences (FJMS), 143(9), 3243-3259. https://doi.org/10.17654/0972087126178
Vancouver
Linker P, Ozel C. SEMI-ANALYTICAL APPROXIMATION OF THE SET PARTITION PROBLEM USING THE HOMOTOPY ANALYSIS METHOD. Far East Journal of Mathematical Sciences (FJMS). 2026;143(9):3243-3259. doi:10.17654/0972087126178
BibTeX
@article{Linker2026,
author = {Linker, Patrick and Ozel, Cenap},
title = {SEMI-ANALYTICAL APPROXIMATION OF THE SET PARTITION PROBLEM USING THE HOMOTOPY ANALYSIS METHOD},
journal = {Far East Journal of Mathematical Sciences (FJMS)},
year = {2026},
volume = {143},
number = {9},
pages = {3243--3259},
doi = {10.17654/0972087126178}
}
EUVIMED