EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

SEMI-ANALYTICAL APPROXIMATION OF THE SET PARTITION PROBLEM USING THE HOMOTOPY ANALYSIS METHOD

Patrick Linker, Cenap Ozel

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).

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →