The k-means algorithm is a well-known method for partitioning n points that lie in the d-dimensional space into k clusters. Its main features are simplicity and speed in practice. Theoretically, however, the best known upper bound on its running time (i.e. O(n^{kd})) can be exponential in the number of points. Recently, Arthur and Vassilvitskii [3] showed a super-polynomial worst-case analysis, improving the best known lower bound from \Omega(n) to 2^{\Omega(\sqrt{n})} with a construction in d=\Omega(\sqrt{n}) dimensions. In [3] they also conjectured the existence of superpolynomial lower bounds for any d >= 2. Our contribution is twofold: we prove this conjecture and we improve the lower bound, by presenting a simple construction in the plane that leads to the exponential lower bound 2^{\Omega(n)}.

We will take a close look at the "Moss-Rabani framework", by studying their primal-dual algorithm for the prize collecting problem in node weighted steiner trees. Each node has a profit and a cost value. The prize-collecting problem calls for choosing a vertex set S, so as to minimize the total cost plus the penalty (loss of profit). This paper presents an O(log n) approximation which is an improvement from the previously known O(log^2 n) approximation by Guha, Moss, Naor and Schieber.

The budgeted maximum coverage problem is: given a collection S of sets with associated costs defined over a domain of weighted elements, and a budget L, find a subset of S' \subseteq S such that the total cost of sets in S' does not exceed L, and the total weight of elements covered by is maximized. This problem is NP-hard. For the special case of this problem, where each set has unit cost, a (1−1/e)-approximation is known. Yet, prior to this work, no approximation results were known for the general cost version. The contribution of this paper is a (1−1/e)-approximation algorithm for the budgeted maximum coverage problem. We also argue that this approximation factor is the best possible, unless NP \subseteq DTIME(n^(loglogn)).

We live in a "small world", where two arbitrary people are likely connected by a short chain of intermediate friends. With scant information about a target individual, people can successively forward a message along such a chain. Experimental studies have verified this property in real social networks, and theoretical models have been advanced to explain it. However, existing theoretical models have not been shown to capture behavior in real-world social networks. Here we introduce a richer model relating geography and social-network friendship, in which the probability of befriending a particular person is inversely proportional to the number of closer people. In a large social network, we show that one-third of the friendships are independent of geography and the remainder exhibit the proposed relationship. Further, we prove analytically that short chains can be discovered in every network exhibiting the relationship.

A few years ago Ageev and Sviridenko presented a simple deterministic procedure for rounding linear relaxations (IPCO 1999, ESA 2000) that they call pipage rounding. Pipage rounding and its randomized variants have been used to derive constant-factor approximation algorithms for a number of problems (see http://arxiv.org/abs/0909.4348 for very recent example due to Chekuri and Vondrak). Since I want to eventually read the Chekuri-Vondrak paper, I wanted to remind myself and the rest of you of pipage rounding.

Given an n-point set P in the unit square, its discrepancy with respect to an axes-parallel rectangle R (contained in the unit square) is the absolute value of n*area(R) - |P \cap R|. The discrepancy of P with respect to all rectangles is the maximum discrepancy with respect to any rectangle. In this talk we will discuss two classical constructions for n-point sets with low discrepancy -- the Van der Corput and Halton-Hammersley sets. The discussion will be based on Section 2.1 of Matousek's book "Geometric Discrepancy".

Given a natural number n, the discrepancy of an n-point set is lower bounded by inf_{all possible ways to putting n points within a unit rectangle} D(P, R_2), where D(P, R_2) is the discrepancy of P with respect to all rectangles. Define the L2-discrepancy for corners C_x as (\int \abs{D(P, C_x)}^2 dx)^{1/2}. We show that by using an auxiliary function, the L2-discrepancy for corners is lower bounded by the square root of log n in 2 dimension. And this implies that the discrepancy of an n-point set is lower bounded by the square root of log n. This lower bound result implies that D(n, R_2) is not bounded by a constant for all n (i.e. as n goes to infinity, the discrepancy of n-point set grows to infinity) (problem 1.1 in Matousek's book "Geometric Discrepancy"). The construction of the auxiliary function is Section 6.1 in Matousek's book

The dynamic programming algorithm of J. B. Saxe (SIAM J. Algebraic Discrete Methods (1980)) for the bandwidth minimization problem is improved. It is shown that, for all k > 1, BANDWIDTH(k) can be solved in O(nk) steps and simultaneous O( nk) space, where n is the number of vertices in the graph, and that each such problem is in NSPACE(logn). The same improved dynamic programming algorithm approach works to show that the MINCUT LINEAR ARRANGEMENT problem restricted to the fixed value k, denoted by MINCUT(k), is solvable in O(nk) steps and simultaneous O(nk) space and is in the class NSPACE(log n).