پیوندهای مفید
آمار
| تعداد نشریات | 33 |
| تعداد شمارهها | 870 |
| تعداد مقالات | 8,472 |
| تعداد مشاهده مقاله | 53,623,169 |
| تعداد دریافت فایل اصل مقاله | 9,719,804 |
An Enhanced Semidefinite Programming Relaxation for Minimum Sum-of-Squares Clustering via Transitivity Constraints | ||
| Computational Sciences and Engineering | ||
| مقالات آماده انتشار، پذیرفته شده، انتشار آنلاین از تاریخ 19 مرداد 1405 | ||
| نوع مقاله: Original Article | ||
| شناسه دیجیتال (DOI): 10.22124/cse.2026.33897.1195 | ||
| نویسندگان | ||
| SeyedehNegar Moussavi؛ Maziar Salahi* | ||
| University of Guilan | ||
| چکیده | ||
| Standard semidefinite programming (SDP) relaxations for the Minimum Sum-of-Squares Clustering problem often produce weak lower bounds. We tighten the relaxation by adding transitivity constraints that enforce the equivalence-relation structure of cluster assignments: if points i and j are together, and i and k are together, then j and k must be together as well. We prove that these constraints are valid inequalities for the original problem, and that the new relaxation dominates the standard one in bound quality. Numerical experiments on Ruspini, Iris, Wine, and synthetic datasets show that our model consistently outperforms both the standard SDP relaxation and a recent MILP formulation, with improvements reaching up to 49% on synthetic instances and over 20% on Wine. The gains are largest when clusters overlap or when the number of clusters or data size grows. This comes at a higher computational cost due to the O(n^3 ) additional constraints, but the trade-off is acceptable for moderate-scale problems. The proposed relaxation offers a practical way to strengthen SDP-based clustering by encoding logical assignment consistency directly within the convex framework. | ||
| کلیدواژهها | ||
| Clustering؛ SDP relaxation؛ MILP | ||
|
آمار تعداد مشاهده مقاله: 4 |
||