Title: The 1932 Paul Erdos' squares in a square problem & related questions

Welcome aboard. Our train of thought is about to take off. We are in Budapest, Hungary, rolled back 71 years. In 1932, the 19-year old Paul Erd?osed the following problem. Inscribe in a unit square r squares, which have no interior points in common. Denote by f(r) the maximum of the sum of side lengths of the r squares. (We allow side lengths of squares to be zero.) The problem is to evaluate the function f(r):

Open Problem 1. For every positive integer r find the value of f(r).

In fact, the above formulation came about later, when Paul and I renewed efforts to settle the problem. Originally Paul formulated the following more narrow but surprisingly difficult conjecture (that is only proven for k = 1). When Paul shared the conjecture with me in 1995, he offered a $50 price for its first proof or disproof.

Fifty Dollar Squares in a Square Conjecture (Paul Erd?1932). For any positive integer k

f(k^2 +1) = k

The conjecture is till open today, in the year 2000, waiting, as Paul Erd?sed to say, "for stronger arms, or, perhaps, brains" to be settled. But Paul and I reached a progress in a broader problem of describing the function f(r).

Title: Maintaining Time-Decaying Stream Aggregates

We formalize the problem of maintaining time-decaying aggregates and statistics of a data stream: the relative contribution of each data item to the aggregate is scaled down by a factor that depends on, and is non-decreasing with, elapsed time. Time-decaying aggregates are used in applications where the significance of data items decreases over time. We develop storage-efficient algorithms, and establish upper and lower bounds. Surprisingly, even though maintaining decayed aggregates have become a widely-used tool, our work seems to be the first both to explore it formally and to provide storage-efficient algorithms for important families of decay functions, including polynomial decay.

Joint work with Edith Cohen.

Title: Asymmetry in k-Center Variants

This presentation will explore three concepts: the k-center problem, some of its variants, and asymmetry. The k-center problem is a fundamental clustering problem, similar to the k-median problem. Variants of \(k\)-center may more accurately model real-life problems than the original formulation. Asymmetry is a significant impediment to approximation in many graph problems, such as k-center, facility location, k-median and the TSP.

We will demonstrate an O(log* n)-approximation algorithm for the asymmetric weighted k-center problem. Here, the vertices have weights and we are given a total budget for opening centers. We will briefly discuss the Inapproximabilty of the outlier and priority variants of the asymmetric k-center problem.