[Forum SIS] seminario 26 maggio Dott. Jianyi Lin

[Dip. Scienze Statistiche - Mi]

DEPARTMENT OF STATISTICAL SCIENCES

Università Cattolica del Sacro Cuore, Milan

Seminar

Wednesday, May 26, at 11.30 a.m.

Jianyi Lin

Università Cattolica del Sacro Cuore



Computational complexity and exact algorithms for size-constrained clustering problems



Abstract

Classical clustering analysis in geometric ambient space can benefit from a-priori background information in the form of problem constraints, such as cluster size constraints introduced for avoiding unbalanced clusterings and hence improving solution's quality. I will present the problem of finding a partition of a given set of n points of the d-dimensional real space into k clusters such that the lp-norm induced distance of all points from their cluster centroid is globally minimized and each cluster has a prescribed cardinality. Such general problem is as computationally intractable as its unconstrained counterpart, the k-Means problem, which was shown to be NP-hard for a general parameter k by S. Dasgupta in 2008 only, although the corresponding heuristic is widespread since the '50s. Computational hardness results will be presented for certain variants of the size-constrained geometrical clustering, while in the polynomial time and space tractable cases some globally optimal exact algorithms based on computational and algebraic geometry techniques will be illustrated.

________________________________________________________________________________
Microsoft Teams meeting
Join on your computer or mobile app
Click here to join the meeting<https://eur03.safelinks.protection.outlook.com/ap/t-59584e83/?url=https%3A%2F%2Fteams.microsoft.com%2Fl%2Fmeetup-join%2F19%253ameeting_YTU4NDM1NTYtMzI1MS00NTU0LWEzZGYtMWQ3OTVjMjZlY2Y4%2540thread.v2%2F0%3Fcontext%3D%257b%2522Tid%2522%253a%2522b94f7d74-81ff-44a9-b588-6682acc85779%2522%252c%2522Oid%2522%253a%25220c084bb4-4916-4250-aaa9-caeb923cf81d%2522%257d&data=04%7C01%7Cdip.scienzestatistiche%40unicatt.it%7Ce8705142b3f9477942ac08d90a44b291%7Cb94f7d7481ff44a9b5886682acc85779%7C0%7C0%7C637552112437402344%7CUnknown%7CTWFpbGZsb3d8eyJWIjoiMC4wLjAwMDAiLCJQIjoiV2luMzIiLCJBTiI6Ik1haWwiLCJXVCI6Mn0%3D%7C1000&sdata=SpGs4ccTt1MNkew80wP9yRiLGwJzZVyIYqJfhTQOZYQ%3D&reserved=0>


Barbara Villa
Funzione Ricerca
Dipartimento di Scienze statistiche
Edificio Lanzone, 18
Dip.scienzestatistiche at unicatt.it<mailto:Dip.scienzestatistiche at unicatt.it>
Tel. +39 02 7234 2647
http://dipartimenti.unicatt.it/scienze_statistiche


Università Cattolica del Sacro Cuore
Largo Gemelli 1, 20123 Milano
www.unicatt.it<http://www.unicatt.it/>

[cid:image001.png at 01D6E2BB.8947BCB0]


 Please don't print this e-mail unless you really need to



[http://static.unicatt.it/ext-portale/FirmaOutlook.jpg]<http://www.unicatt.it/>
[http://static.unicatt.it/ext-portale/5xmille-firma-mail-scritta.jpg]

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.stat.unipg.it/pipermail/sis/attachments/20210519/fb1bf3a1/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image001.png
Type: image/png
Size: 5741 bytes
Desc: image001.png
URL: <http://www.stat.unipg.it/pipermail/sis/attachments/20210519/fb1bf3a1/attachment.png>