Questions

You drink coffee, amidst the swirl think of a problem, and you feel something must be known already. Here are two examples (refs, welcome).

• Suresh has an ongoing treatise on clustering. Say you have n points to put into k clusters with some objective function O_k (eg, sum over points of the distance to closest center). What I want to optimize is: O_k if k or fewer clusters, but O_k' (k/k') if k' > k clusters are used. Is this a well studied variation of clustering?
  
• This is a marriage of secretary type and stable matching type problems. Say there is a fixed set of women with their preference orders. Men arrive in some random order and go to each women who must accept or reject. Any way to resurrect some approximate notion of stable matching?

Disclaimer: I havent thought about these problems, and most likely, they will need more formulation.