Consider the generalized min-sum set cover problem: we are given a universe of elements and a collection of subsets. Each subset S also has a requirement K(S). The goal is to output an ordering of the universe so that the total cover time of the sets is minimized, where the cover time of a set S is the earliest position in the order when K(S) elements from S have been output. We give a constant-factor approximation algorithm for this problem via rounding of a strengthened LP relaxation.

In this paper, we look at the 2-edge-connectivity generalization of the problems: (i) group Steiner tree (now we want to choose representatives from each group and 2-connect them to the root), (ii) connected facility location (the facilities need to be 2-edge-connected), (iii) buy-at-bulk (the demand pairs need 2-edge-disjoint paths), and (iv) k-MST (pick an arbitrary set of k vertices and 2-connect them). We show that tree embedding techniques can be used to simplify all these problems and obtain polylogarithmic approximations.

In this paper, we study scheduling problems with the added flexibility of not picking a small fraction of jobs. Formally, given a set of jobs (each with an associated profit) and an objective function (like maximum makespan, average completion time, or average flow time), the goal is to schedule a subset of jobs that achieve some target profit, while minimizing the objective function on those set of jobs.

Consider the following generalization of the online Steiner tree problem: each day, a new pair of vertices (s_i,t_i) arrive requiring k-edge-connectivity; the objective is to buy a set of edges to k-connect these vertices such that the total cost of the edges bought till date is competitive with the cost of the optimal offline solution feasible to the pairs that have arrived. We give an online algorithm with polylogarithmic competitiveness, by using recent results on embeddings into subtrees to get more structure on the cuts.