Explore the vast range of titles available.

We consider the capacitated k -center problem. In this problem we are given a finite set of locations in a metric space and each location has an associated non-negative integer capacity. The goal is to choose (open) k locations (called centers) and assign each location to an open center to minimize the maximum, over all locations, of the distance of the location to its assigned center. The number of locations assigned to a center cannot exceed the center’s capacity. The uncapacitated k -center problem has a simple tight 2 -approximation from the 80’s. In contrast, the first constant factor approximation for the capacitated problem was obtained only recently by Cygan, Hajiaghayi and Khuller who gave an intricate LP-rounding algorithm that achieves an approximation guarantee in the hundreds. In this paper we give a simple algorithm with a clean analysis and prove an approximation guarantee of 9 . It uses the standard LP relaxation and comes close to settling the integrality gap (after necessary preprocessing), which is narrowed down to either 7 , 8 or 9 . The algorithm proceeds by first reducing to special tree instances , and then uses our best-possible algorithm to solve such instances. Our concept of tree instances is versatile and applies to natural variants of the capacitated k -center problem for which we also obtain improved algorithms. Finally, we give evidence to show that more powerful preprocessing could lead to better algorithms, by giving an approximation algorithm that beats the integrality gap for instances where all non-zero capacities are the same.

We consider the capacitated ...-center problem. In this problem we are given a finite set of locations in a metric space and each location has an associated non-negative integer capacity. The goal is to choose (open) ... locations (called centers) and assign each location to an open center to minimize the maximum, over all locations, of the distance of the location to its assigned center. The number of locations assigned to a center cannot exceed the center's capacity. The uncapacitated ...-center problem has a simple tight ...-approximation from the 80's. In contrast, the first constant factor approximation for the capacitated problem was obtained only recently by Cygan, Hajiaghayi and Khuller who gave an intricate LP-rounding algorithm that achieves an approximation guarantee in the hundreds. In this paper we give a simple algorithm with a clean analysis and prove an approximation guarantee of ... It uses the standard LP relaxation and comes close to settling the integrality gap (after necessary preprocessing), which is narrowed down to either ... or ... The algorithm proceeds by first reducing to special tree instances, and then uses our best-possible algorithm to solve such instances. Our concept of tree instances is versatile and applies to natural variants of the capacitated ...-center problem for which we also obtain improved algorithms. Finally, we give evidence to show that more powerful preprocessing could lead to better algorithms, by giving an approximation algorithm that beats the integrality gap for instances where all non-zero capacities are the same.

We consider the problem of scheduling a set of jobs on a system that offers certain resource, wherein the amount of resource offered varies over time. For each job, the input specifies a set of possible scheduling instances, where each instance is given by starting time, ending time, profit and resource requirement. A feasible solution selects a subset of job instances such that at any timeslot, the total requirement by the chosen instances does not exceed the resource available at that timeslot, and at most one instance is chosen for each job. The above problem falls under the well-studied framework of unsplittable flow problem on line. The generalized notion of scheduling possibilities captures the standard setting concerned with release times and deadlines. We present improved algorithms based on the primal–dual paradigm, where the improvements are in terms of approximation ratio, running time and simplicity.

We consider clustering in the perturbation resilience model that has been studied since the work of Bilu and Linial [ICS, 2010] and Awasthi, Blum and Sheffet [Inf. Proc. Lett., 2012]. A clustering instance \\(I\\) is said to be \\(\\alpha\\)-perturbation resilient if the optimal solution does not change when the pairwise distances are modified by a factor of \\(\\alpha\\) and the perturbed distances satisfy the metric property --- this is the metric perturbation resilience property introduced in Angelidakis et. al. [STOC, 2010] and a weaker requirement than prior models. We make two high-level contributions. 1) We show that the natural LP relaxation of \\(k\\)-center and asymmetric \\(k\\)-center is integral for \\(2\\)-perturbation resilient instances. We belive that demonstrating the goodness of standard LP relaxations complements existing results that are based on combinatorial algorithms designed for the perturbation model. 2) We define a simple new model of perturbation resilience for clustering with \\emph{outliers}. Using this model we show that the unified MST and dynamic programming based algorithm proposed by Angelidakis et. al. [STOC, 2010] exactly solves the clustering with outliers problem for several common center based objectives (like \\(k\\)-center, \\(k\\)-means, \\(k\\)-median) when the instances is \\(2\\)-perturbation resilient. We further show that a natural LP relxation is integral for \\(2\\)-perturbation resilient instances of \\kcenter with outliers.

We consider the problem of maximizing a nonnegative submodular set function \\(f:2^{\\mathcal{N}} \\rightarrow \\mathbb{R}^+\\) subject to a \\(p\\)-matchoid constraint in the single-pass streaming setting. Previous work in this context has considered streaming algorithms for modular functions and monotone submodular functions. The main result is for submodular functions that are {\\em non-monotone}. We describe deterministic and randomized algorithms that obtain a \\(\\Omega(\\frac{1}{p})\\)-approximation using \\(O(k \\log k)\\)-space, where \\(k\\) is an upper bound on the cardinality of the desired set. The model assumes value oracle access to \\(f\\) and membership oracles for the matroids defining the \\(p\\)-matchoid constraint.

We consider a natural generalization of the Partial Vertex Cover problem. Here an instance consists of a graph G = (V,E), a positive cost function c: V-> Z^{+}, a partition \\(P_1,..., P_r\\) of the edge set \\(E\\), and a parameter \\(k_i\\) for each partition \\(P_i\\). The goal is to find a minimum cost set of vertices which cover at least \\(k_i\\) edges from the partition \\(P_i\\). We call this the Partition Vertex Cover problem. In this paper, we give matching upper and lower bound on the approximability of this problem. Our algorithm is based on a novel LP relaxation for this problem. This LP relaxation is obtained by adding knapsack cover inequalities to a natural LP relaxation of the problem. We show that this LP has integrality gap of \\(O(log r)\\), where \\(r\\) is the number of sets in the partition of the edge set. We also extend our result to more general settings.

Hepatolithiasis (HL), an uncommon disease among Indians, occurs due to a complex interplay of various structural and functional factors. We retrospectively evaluated the clinical and histopathological spectrum of HL (N = 19) with immunohistochemical evaluation for biliary apomucins and canalicular transporter proteins, both crucial for lithogenesis. Nineteen surgically resected cases were included. Histopathology was systematically evaluated. Immunohistochemistry for apomucins (MUC1, MUC2, MUC4, MUC5AC, and MUC6) and canalicular transporter proteins (BSEP and MDR3) was applied to all cases. The median age was 51 years with female preponderance (F:M = 1.4:1). The stone was cholesterol-rich in 71.4% and pigmented in 28.6% (n = 14). Histopathology showed variable large bile-duct thickening due to fibrosis and inflammation with peribiliary gland hyperplasia. Structural causes (Caroli disease, choledochal cyst, and post-surgical complication) were noted in 15.8% of cases (secondary HL). Expression of gel-forming apomucin MUC1, MUC2, and MUC5AC was seen in either bile duct epithelia or peribiliary glands in 84.2%, 10.5%, and 84.2% cases respectively. Loss of canalicular expression of MDR3 was noted in 42.1% of cases while BSEP was retained in all. Primary HL in the north Indian population can be associated with the loss of MDR3 expression (with retained BSEP) and/ or a shift in the phenotype of biliary apomucins to gel-forming apomucins. The former factor alters the bile acid/ phospholipid ratio while the latter parameter promulgates crystallization. In conjunction, these factors are responsible for the dominantly cholesterol-rich stones in the index population.