Page 10 - 第四届运筹青年论坛会议手册-0615

08 第四届中国运筹青年论坛 | 青年报告

The Seeding Algorithm for K-means Problem

and its Variants

李敏 山东师范大学

The k-means problem is a classic NP-hard problem in machine learning and computational geometry,

and its goal is to separate the given set into k clusters according to the minimal squared distance.

According to the different practical background, the k-means problem has many variants, such as k-

means problem with penalties, spherical k-means problem, functional k-means problem, and so on.

The k-means algorithm (also known as Lloyd's algorithm) is the most effective heuristic algorithm
to solve k-means problem, which is also one of the Top 10 algorithms in data mining. Although the

approximation algorithm cannot be analyzed directly in theory, but the Lloyd's algorithm can be

extended into an effective approximation algorithm based on the seeding algorithm. In this talk, we

will introduce how to use seeding algorithms to solve k-means problem and its variant problems.

Plateaux on Generalized Stirling Permutations and

Partial γ-positivity

林志聪 山东大学

We prove that the enumerative polynomials of generalized Stirling permutations by the statistics of

plateaux, descents and ascents are partial γ-positive. Specialization of our result to the Jacobi-Stirling

permutations confirms a recent partial γ-positivity conjecture due to Ma, Ma and Yeh. Our partial γ-

positivity expansion, as well as a combinatorial interpretation for the corresponding γ-coefficients,
are obtained via the machine of context-free grammars and a group action on generalized Stirling

permutations. Besides, we also provide an alternative approach to the partial γ-positivity from the

stability of certain multivariate polynomials.