Q1 [open] Main question (k=2, uniform sparsest cut phi(S) = w(S, S-bar)/(|S| |S-bar|)): under the (c, epsilon) property for the sparsest cut objective, i.e. assuming that all c-approximations to the sparsest cut objective are epsilon-close to the target clustering, can one find a clustering that is O(epsilon)-close to the target, even though no c-approximation to sparsest cut is known? 'Given that best know
Q2 [open] 'Other interesting objectives to consider in this framework are the balanced cut objective [1]': obtain (c,epsilon)-approximation-stability results (O(epsilon)-close clustering under the assumption that all c-approximations are epsilon-close to the target) for the balanced cut objective.
Q3 [open] 'Other interesting objectives to consider in this framework are ... the bicriteria objective of [7]' (Kannan, Vempala, Vetta, 'On clusterings: good, bad and spectral', JACM 2004): obtain (c,epsilon)-approximation-stability results for the KVV bicriteria (conductance / inter-cluster weight) clustering objective.