Knapsack median is a generalization of the classic k -median problem in which we replace the cardinality constraint with a knapsack constraint. It is currently known to be 32-approximable. We improve on the best known algorithms in several ways, including adding randomization and applying sparsification as a preprocessing step. The latter improvement produces the first LP for this problem with bounded integrality gap. The new algorithm obtains an approximation factor of 17.46. We also give a 3.05 approximation with small budget violation.

Dependent rounding is a useful technique for optimization problems with hard budget constraints. This framework naturally leads to negative correlation properties. However, what if an application naturally calls for dependent rounding on the one hand and desires positive correlation on the other? More generally, we develop algorithms that guarantee the known properties of dependent rounding but also have nearly bestpossible behavior—near-independence, which generalizes positive correlation—on “small” subsets of the variables. The recent breakthrough of Li and Svensson for the classical k -median problem has to handle positive correlation in certain dependent rounding settings, and does so implicitly. We improve upon Li-Svensson’s approximation ratio for k -median from 2.732 + ϵ to 2.675 + ϵ by developing an algorithm that improves upon various aspects of their work. Our dependent rounding approach helps us improve the dependence of the runtime on the parameter ϵ from Li-Svensson’s N O (1/ϵ 2 ) to N O ((1/ϵ)log(1/ϵ)) .

We study the k-level uncapacitated facility location problem (k-level UFL) in which clients need to be connected with paths crossing open facilities of k types (levels). In this paper we first propose an approximation algorithm that for any constant k, in polynomial time, delivers solutions of cost at most α k times OPT, where α k is an increasing function of k, with $\lim _{k\to \infty } \alpha _{k} = 3$ . Our algorithm rounds a fractional solution to an extended LP formulation of the problem. The rounding builds upon the technique of iteratively rounding fractional solutions on trees (Garg, Konjevod, and Ravi SODA’98) originally used for the group Steiner tree problem. We improve the approximation ratio for k-level UFL for all k ≥ 3, in particular we obtain the ratio equal 2.02, 2.14, and 2.24 for k = 3,4, and 5. Second, we give a simple interpretation of the randomization process (Li ICALP’2011) for 1-level UFL in terms of solving an auxiliary (factor revealing) LP. Armed with this simple view point, we exercise the randomization on our algorithm for the k-level UFL. We further improve the approximation ratio for all k ≥ 3, obtaining 1.97, 2.09, and 2.19 for k = 3,4, and 5. Third, we extend our algorithm to the k-level UFL with penalties (k-level UFLWP), in which the setting is the same as k-level UFL except that the planner has the option to pay a penalty instead of connecting chosen clients.

In the classical k-median problem the goal is to select a subset of at most k facilities in order to minimize the total cost of opened facilities and established connections between clients and opened facilities. We consider the capacitated version of the problem, where a single facility may only serve a limited number of clients. We construct approximation algorithms slightly violating the capacities based on rounding a fractional solution to the standard LP. It is well known that the standard LP (even in the case of uniform capacities) has unbounded integrality gap if we only allow violating capacities by a factor smaller than 2, or if we only allow violating the number of facilities by a factor smaller than 2. It is also known that violating capacities by a factor of 2 + ε is sufficient to obtain constant factor approximation of the connection cost in the case of uniform capacities. In this paper we substantially extend this result in the following two directions. On one hand, we obtain a 2+ε capacity violating algorithm to the more general k-facility location problem with uniform capacities, where opening facilities incurs a location specific opening cost. On the other hand, we show that violating capacities by a slightly bigger factor of 3 + ε is sufficient to obtain constant factor approximation of the connection cost also in the case of the non-uniform hard capacitated k-median problem. Our algorithms first use the clustering of Charikar et al. to partition the facilities into sets of total fractional opening at least 1 — 1/ℓ for some fixed ℓ. Then we exploit the technique of Levi, Shmoys, and Swamy developed for the capacitated facility location problem, which is to locally group the demand from clients to obtain a system of single node demand instances. Next, depending on the setting, we either work with stars of facilities (for non-uniform capacities), or we use a dedicated routing tree on the demand nodes (for non-uniform opening cost), to redistribute the demand that cannot be satisfied locally within the clusters.

Dependent rounding is a useful technique for optimization problems with hard budget constraints. This framework naturally leads to negative correlation properties. However, what if an application naturally calls for dependent rounding on the one hand, and desires positive correlation on the other? More generally, we develop algorithms that guarantee the known properties of dependent rounding, but also have nearly best-possible behavior – near-independence, which generalizes positive correlation – on “small” subsets of the variables. The recent breakthrough of Li & Svensson for the classical k-median problem has to handle positive correlation in certain dependent-rounding settings, and does so implicitly. We improve upon Li-Svensson's approximation ratio for k-median from 2.732 + ε to 2.611 + ε by developing an algorithm that improves upon various aspects of their work. Our dependent-rounding approach helps us improve the dependence of the runtime on the parameter ε from Li-Svensson's NO(1/ε2) to NO((1/ε)log (1/ε)).(An erratum has been attached to the previously published proceedings.).