אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

K-median is the problem where we wish to open k facilities so as to minimize the average distance each client has to its closest opened facility. The lack of progress on this central problem compared to facility location (a close relative) is partly due to the difficulty of handling the hard constraint that at most k facilities are allowed to be opened.

In this talk we shall see that we can relax this constraint into a soft constraint with a "violation-dependent" increase in the runtime. This gives a novel point of view for addressing k-median that allows us to give an algorithm that achieves an approximation guarantee of 1+sqrt(3) improving upon the decade-old ratio of 3.

This is joint work with Shi Li.