15 Search Results for "Chakrabarty, Deeparnab"


Document
Fault-tolerant k-Supplier with Outliers

Authors: Deeparnab Chakrabarty, Luc Cote, and Ankita Sarkar

Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)


Abstract
We present approximation algorithms for the Fault-tolerant k-Supplier with Outliers (FkSO) problem. This is a common generalization of two known problems - k-Supplier with Outliers, and Fault-tolerant k-Supplier - each of which generalize the well-known k-Supplier problem. In the k-Supplier problem the goal is to serve n clients C, by opening k facilities from a set of possible facilities F; the objective function is the farthest that any client must travel to access an open facility. In FkSO, each client v has a fault-tolerance 𝓁_v, and now desires 𝓁_v facilities to serve it; so each client v’s contribution to the objective function is now its distance to the 𝓁_v^th closest open facility. Furthermore, we are allowed to choose m clients that we will serve, and only those clients contribute to the objective function, while the remaining n-m are considered outliers. Our main result is a (4t-1)-approximation for the FkSO problem, where t is the number of distinct values of 𝓁_v that appear in the instance. At t = 1, i.e. in the case where the 𝓁_v’s are uniformly some 𝓁, this yields a 3-approximation, improving upon the 11-approximation given for the uniform case by Inamdar and Varadarajan [2020], who also introduced the problem. Our result for the uniform case matches tight 3-approximations that exist for k-Supplier, k-Supplier with Outliers, and Fault-tolerant k-Supplier. Our key technical contribution is an application of the round-or-cut schema to FkSO. Guided by an LP relaxation, we reduce to a simpler optimization problem, which we can solve to obtain distance bounds for the "round" step, and valid inequalities for the "cut" step. By varying how we reduce to the simpler problem, we get varying distance bounds - we include a variant that gives a (2^t + 1)-approximation, which is better for t ∈ {2,3}. In addition, for t = 1, we give a more straightforward application of round-or-cut, yielding a 3-approximation that is much simpler than our general algorithm.

Cite as

Deeparnab Chakrabarty, Luc Cote, and Ankita Sarkar. Fault-tolerant k-Supplier with Outliers. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 23:1-23:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{chakrabarty_et_al:LIPIcs.STACS.2024.23,
  author =	{Chakrabarty, Deeparnab and Cote, Luc and Sarkar, Ankita},
  title =	{{Fault-tolerant k-Supplier with Outliers}},
  booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
  pages =	{23:1--23:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-311-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{289},
  editor =	{Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.23},
  URN =		{urn:nbn:de:0030-drops-197336},
  doi =		{10.4230/LIPIcs.STACS.2024.23},
  annote =	{Keywords: Clustering, approximation algorithms, round-or-cut}
}
Document
Approximation Algorithms for Continuous Clustering and Facility Location Problems

Authors: Deeparnab Chakrabarty, Maryam Negahbani, and Ankita Sarkar

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)


Abstract
In this paper, we consider center-based clustering problems where C, the set of points to be clustered, lies in a metric space (X,d), and the set X of candidate centers is potentially infinite-sized. We call such problems continuous clustering problems to differentiate them from the discrete clustering problems where the set of candidate centers is explicitly given. It is known that for many objectives, when one restricts the set of centers to C itself and applies an α_dis-approximation algorithm for the discrete version, one obtains a β ⋅ α_{dis}-approximation algorithm for the continuous version via the triangle inequality property of the distance function. Here β depends on the objective, and for many objectives such as k-median, β = 2, while for some others such as k-means, β = 4. The motivating question in this paper is whether this gap of factor β between continuous and discrete problems is inherent, or can one design better algorithms for continuous clustering than simply reducing to the discrete case as mentioned above? In a recent SODA 2021 paper, Cohen-Addad, Karthik, and Lee prove a factor-2 and a factor-4 hardness, respectively, for the continuous versions of the k-median and k-means problems, even when the number of cluster centers is a constant. The discrete problem for a constant number of centers is easily solvable exactly using enumeration, and therefore, in certain regimes, the "β-factor loss" seems unavoidable. In this paper, we describe a technique based on the round-or-cut framework to approach continuous clustering problems. We show that, for the continuous versions of some clustering problems, we can design approximation algorithms attaining a better factor than the β-factor blow-up mentioned above. In particular, we do so for: the uncapacitated facility location problem with uniform facility opening costs (λ-UFL); the k-means problem; the individually fair k-median problem; and the k-center with outliers problem. Notably, for λ-UFL, where β = 2 and the discrete version is NP-hard to approximate within a factor of 1.27, we describe a 2.32-approximation for the continuous version, and indeed 2.32 < 2 × 1.27. Also, for k-means, where β = 4 and the best known approximation factor for the discrete version is 9, we obtain a 32-approximation for the continuous version, which is better than 4 × 9 = 36. The main challenge one faces is that most algorithms for the discrete clustering problems, including the state of the art solutions, depend on Linear Program (LP) relaxations that become infinite-sized in the continuous version. To overcome this, we design new linear program relaxations for the continuous clustering problems which, although having exponentially many constraints, are amenable to the round-or-cut framework.

Cite as

Deeparnab Chakrabarty, Maryam Negahbani, and Ankita Sarkar. Approximation Algorithms for Continuous Clustering and Facility Location Problems. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 33:1-33:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{chakrabarty_et_al:LIPIcs.ESA.2022.33,
  author =	{Chakrabarty, Deeparnab and Negahbani, Maryam and Sarkar, Ankita},
  title =	{{Approximation Algorithms for Continuous Clustering and Facility Location Problems}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{33:1--33:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.33},
  URN =		{urn:nbn:de:0030-drops-169710},
  doi =		{10.4230/LIPIcs.ESA.2022.33},
  annote =	{Keywords: Approximation Algorithms, Clustering, Facility Location, Fairness, Outliers}
}
Document
Graph Connectivity and Single Element Recovery via Linear and OR Queries

Authors: Sepehr Assadi, Deeparnab Chakrabarty, and Sanjeev Khanna

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)


Abstract
We study the problem of finding a spanning forest in an undirected, n-vertex multi-graph under two basic query models. One are Linear queries which are linear measurements on the incidence vector induced by the edges; the other are the weaker OR queries which only reveal whether a given subset of plausible edges is empty or not. At the heart of our study lies a fundamental problem which we call the single element recovery problem: given a non-negative vector x ∈ ℝ^{N}_{≥ 0}, the objective is to return a single element x_j > 0 from the support. Queries can be made in rounds, and our goals is to understand the trade-offs between the query complexity and the rounds of adaptivity needed to solve these problems, for both deterministic and randomized algorithms. These questions have connections and ramifications to multiple areas such as sketching, streaming, graph reconstruction, and compressed sensing. Our main results are as follows: - For the single element recovery problem, it is easy to obtain a deterministic, r-round algorithm which makes (N^{1/r}-1)-queries per-round. We prove that this is tight: any r-round deterministic algorithm must make ≥ (N^{1/r} - 1) Linear queries in some round. In contrast, a 1-round O(polylog)-query randomized algorithm is known to exist. - We design a deterministic O(r)-round, Õ(n^{1+1/r})-OR query algorithm for graph connectivity. We complement this with an Ω̃(n^{1 + 1/r})-lower bound for any r-round deterministic algorithm in the OR-model. - We design a randomized, 2-round algorithm for the graph connectivity problem which makes Õ(n)-OR queries. In contrast, we prove that any 1-round algorithm (possibly randomized) requires Ω̃(n²)-OR queries. A randomized, 1-round algorithm making Õ(n)-Linear queries is already known. All our algorithms, in fact, work with more natural graph query models which are special cases of the above, and have been extensively studied in the literature. These are Cross queries (cut-queries) and BIS (bipartite independent set) queries.

Cite as

Sepehr Assadi, Deeparnab Chakrabarty, and Sanjeev Khanna. Graph Connectivity and Single Element Recovery via Linear and OR Queries. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 7:1-7:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{assadi_et_al:LIPIcs.ESA.2021.7,
  author =	{Assadi, Sepehr and Chakrabarty, Deeparnab and Khanna, Sanjeev},
  title =	{{Graph Connectivity and Single Element Recovery via Linear and OR Queries}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{7:1--7:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.7},
  URN =		{urn:nbn:de:0030-drops-145880},
  doi =		{10.4230/LIPIcs.ESA.2021.7},
  annote =	{Keywords: Query Models, Graph Connectivity, Group Testing, Duality}
}
Document
Track A: Algorithms, Complexity and Games
Revisiting Priority k-Center: Fairness and Outliers

Authors: Tanvi Bajpai, Deeparnab Chakrabarty, Chandra Chekuri, and Maryam Negahbani

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)


Abstract
In the Priority k-Center problem, the input consists of a metric space (X,d), an integer k and for each point v ∈ X a priority radius r(v). The goal is to choose k-centers S ⊆ X to minimize max_{v ∈ X} 1/(r(v)) d(v,S). If all r(v)’s were uniform, one obtains the classical k-center problem. Plesník [Ján Plesník, 1987] introduced this problem and gave a 2-approximation algorithm matching the best possible algorithm for vanilla k-center. We show how the Priority k-Center problem is related to two different notions of fair clustering [Harris et al., 2019; Christopher Jung et al., 2020]. Motivated by these developments we revisit the problem and, in our main technical contribution, develop a framework that yields constant factor approximation algorithms for Priority k-Center with outliers. Our framework extends to generalizations of Priority k-Center to matroid and knapsack constraints, and as a corollary, also yields algorithms with fairness guarantees in the lottery model of Harris et al.

Cite as

Tanvi Bajpai, Deeparnab Chakrabarty, Chandra Chekuri, and Maryam Negahbani. Revisiting Priority k-Center: Fairness and Outliers. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 21:1-21:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{bajpai_et_al:LIPIcs.ICALP.2021.21,
  author =	{Bajpai, Tanvi and Chakrabarty, Deeparnab and Chekuri, Chandra and Negahbani, Maryam},
  title =	{{Revisiting Priority k-Center: Fairness and Outliers}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{21:1--21:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.21},
  URN =		{urn:nbn:de:0030-drops-140909},
  doi =		{10.4230/LIPIcs.ICALP.2021.21},
  annote =	{Keywords: Fairness, Clustering, Approximation, Outliers}
}
Document
Track A: Algorithms, Complexity and Games
Minimum-Norm Load Balancing Is (Almost) as Easy as Minimizing Makespan

Authors: Sharat Ibrahimpur and Chaitanya Swamy

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)


Abstract
We consider the minimum-norm load-balancing (MinNormLB) problem, wherein there are n jobs, each of which needs to be assigned to one of m machines, and we are given the processing times {p_{ij}} of the jobs on the machines. We also have a monotone, symmetric norm f:ℝ^m → ℝ_{≥ 0}. We seek an assignment σ of jobs to machines that minimizes the f-norm of the induced load vector load->_σ ∈ ℝ_{≥ 0}^m, where load_σ(i) = ∑_{j:σ(j) = i}p_{ij}. This problem was introduced by [Deeparnab Chakrabarty and Chaitanya Swamy, 2019], and the current-best result for MinNormLB is a (4+ε)-approximation [Deeparnab Chakrabarty and Chaitanya Swamy, 2019]. In the stochastic version of MinNormLB, the job processing times are given by nonnegative random variables X_{ij}, and jobs are independent; the goal is to find an assignment σ that minimizes the expected f-norm of the induced random load vector. We obtain results that (essentially) match the best-known guarantees for deterministic makespan minimization (MinNormLB with 𝓁_∞ norm). For MinNormLB, we obtain a (2+ε)-approximation for unrelated machines, and a PTAS for identical machines. For stochastic MinNormLB, we consider the setting where the X_{ij}s are Poisson random variables, denoted PoisNormLB. Our main result here is a novel and powerful reduction showing that, for any machine environment (e.g., unrelated/identical machines), any α-approximation algorithm for MinNormLB in that machine environment yields a randomized α(1+ε)-approximation for PoisNormLB in that machine environment. Combining this with our results for MinNormLB, we immediately obtain a (2+ε)-approximation for PoisNormLB on unrelated machines, and a PTAS for PoisNormLB on identical machines. The latter result substantially generalizes a PTAS for makespan minimization with Poisson jobs obtained recently by [Anindya De et al., 2020].

Cite as

Sharat Ibrahimpur and Chaitanya Swamy. Minimum-Norm Load Balancing Is (Almost) as Easy as Minimizing Makespan. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 81:1-81:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{ibrahimpur_et_al:LIPIcs.ICALP.2021.81,
  author =	{Ibrahimpur, Sharat and Swamy, Chaitanya},
  title =	{{Minimum-Norm Load Balancing Is (Almost) as Easy as Minimizing Makespan}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{81:1--81:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.81},
  URN =		{urn:nbn:de:0030-drops-141504},
  doi =		{10.4230/LIPIcs.ICALP.2021.81},
  annote =	{Keywords: Approximation algorithms, Load balancing, Minimum-norm optimization, LP rounding}
}
Document
Track A: Algorithms, Complexity and Games
Graph Coloring via Degeneracy in Streaming and Other Space-Conscious Models

Authors: Suman K. Bera, Amit Chakrabarti, and Prantar Ghosh

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)


Abstract
We study the problem of coloring a given graph using a small number of colors in several well-established models of computation for big data. These include the data streaming model, the general graph query model, the massively parallel communication (MPC) model, and the CONGESTED-CLIQUE and the LOCAL models of distributed computation. On the one hand, we give algorithms with sublinear complexity, for the appropriate notion of complexity in each of these models. Our algorithms color a graph G using κ(G)⋅(1+o(1)) colors, where κ(G) is the degeneracy of G: this parameter is closely related to the arboricity α(G). As a function of κ(G) alone, our results are close to best possible, since the optimal number of colors is κ(G)+1. For several classes of graphs, including real-world "big graphs," our results improve upon the number of colors used by the various (Δ(G)+1)-coloring algorithms known for these models, where Δ(G) is the maximum degree in G, since Δ(G) ⩾ κ(G) and can in fact be arbitrarily larger than κ(G). On the other hand, we establish certain lower bounds indicating that sublinear algorithms probably cannot go much further. In particular, we prove that any randomized coloring algorithm that uses at most κ(G)+O(1) colors would require Ω(n²) storage in the one pass streaming model, and Ω(n²) many queries in the general graph query model, where n is the number of vertices in the graph. These lower bounds hold even when the value of κ(G) is known in advance; at the same time, our upper bounds do not require κ(G) to be given in advance.

Cite as

Suman K. Bera, Amit Chakrabarti, and Prantar Ghosh. Graph Coloring via Degeneracy in Streaming and Other Space-Conscious Models. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 11:1-11:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)


Copy BibTex To Clipboard

@InProceedings{bera_et_al:LIPIcs.ICALP.2020.11,
  author =	{Bera, Suman K. and Chakrabarti, Amit and Ghosh, Prantar},
  title =	{{Graph Coloring via Degeneracy in Streaming and Other Space-Conscious Models}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{11:1--11:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.11},
  URN =		{urn:nbn:de:0030-drops-124182},
  doi =		{10.4230/LIPIcs.ICALP.2020.11},
  annote =	{Keywords: Data streaming, Graph coloring, Sublinear algorithms, Massively parallel communication, Distributed algorithms}
}
Document
Simpler and Better Algorithms for Minimum-Norm Load Balancing

Authors: Deeparnab Chakrabarty and Chaitanya Swamy

Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)


Abstract
Recently, Chakrabarty and Swamy (STOC 2019) introduced the minimum-norm load-balancing problem on unrelated machines, wherein we are given a set J of jobs that need to be scheduled on a set of m unrelated machines, and a monotone, symmetric norm; We seek an assignment sigma: J -> [m] that minimizes the norm of the resulting load vector load_{sigma} in R_+^m, where load_{sigma}(i) is the load on machine i under the assignment sigma. Besides capturing all l_p norms, symmetric norms also capture other norms of interest including top-l norms, and ordered norms. Chakrabarty and Swamy (STOC 2019) give a (38+epsilon)-approximation algorithm for this problem via a general framework they develop for minimum-norm optimization that proceeds by first carefully reducing this problem (in a series of steps) to a problem called min-max ordered load balancing, and then devising a so-called deterministic oblivious LP-rounding algorithm for ordered load balancing. We give a direct, and simple 4+epsilon-approximation algorithm for the minimum-norm load balancing based on rounding a (near-optimal) solution to a novel convex-programming relaxation for the problem. Whereas the natural convex program encoding minimum-norm load balancing problem has a large non-constant integrality gap, we show that this issue can be remedied by including a key constraint that bounds the "norm of the job-cost vector." Our techniques also yield a (essentially) 4-approximation for: (a) multi-norm load balancing, wherein we are given multiple monotone symmetric norms, and we seek an assignment respecting a given budget for each norm; (b) the best simultaneous approximation factor achievable for all symmetric norms for a given instance.

Cite as

Deeparnab Chakrabarty and Chaitanya Swamy. Simpler and Better Algorithms for Minimum-Norm Load Balancing. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 27:1-27:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{chakrabarty_et_al:LIPIcs.ESA.2019.27,
  author =	{Chakrabarty, Deeparnab and Swamy, Chaitanya},
  title =	{{Simpler and Better Algorithms for Minimum-Norm Load Balancing}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{27:1--27:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Bender, Michael A. and Svensson, Ola and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.27},
  URN =		{urn:nbn:de:0030-drops-111488},
  doi =		{10.4230/LIPIcs.ESA.2019.27},
  annote =	{Keywords: Approximation Algorithms}
}
Document
Track A: Algorithms, Complexity and Games
Tight FPT Approximations for k-Median and k-Means

Authors: Vincent Cohen-Addad, Anupam Gupta, Amit Kumar, Euiwoong Lee, and Jason Li

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)


Abstract
We investigate the fine-grained complexity of approximating the classical k-Median/k-Means clustering problems in general metric spaces. We show how to improve the approximation factors to (1+2/e+epsilon) and (1+8/e+epsilon) respectively, using algorithms that run in fixed-parameter time. Moreover, we show that we cannot do better in FPT time, modulo recent complexity-theoretic conjectures.

Cite as

Vincent Cohen-Addad, Anupam Gupta, Amit Kumar, Euiwoong Lee, and Jason Li. Tight FPT Approximations for k-Median and k-Means. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 42:1-42:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{cohenaddad_et_al:LIPIcs.ICALP.2019.42,
  author =	{Cohen-Addad, Vincent and Gupta, Anupam and Kumar, Amit and Lee, Euiwoong and Li, Jason},
  title =	{{Tight FPT Approximations for k-Median and k-Means}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{42:1--42:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.42},
  URN =		{urn:nbn:de:0030-drops-106182},
  doi =		{10.4230/LIPIcs.ICALP.2019.42},
  annote =	{Keywords: approximation algorithms, fixed-parameter tractability, k-median, k-means, clustering, core-sets}
}
Document
Adaptive Boolean Monotonicity Testing in Total Influence Time

Authors: Deeparnab Chakrabarty and C. Seshadhri

Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)


Abstract
Testing monotonicity of a Boolean function f:{0,1}^n -> {0,1} is an important problem in the field of property testing. It has led to connections with many interesting combinatorial questions on the directed hypercube: routing, random walks, and new isoperimetric theorems. Denoting the proximity parameter by epsilon, the best tester is the non-adaptive O~(epsilon^{-2}sqrt{n}) tester of Khot-Minzer-Safra (FOCS 2015). A series of recent results by Belovs-Blais (STOC 2016) and Chen-Waingarten-Xie (STOC 2017) have led to Omega~(n^{1/3}) lower bounds for adaptive testers. Reducing this gap is a significant question, that touches on the role of adaptivity in monotonicity testing of Boolean functions. We approach this question from the perspective of parametrized property testing, a concept recently introduced by Pallavoor-Raskhodnikova-Varma (ACM TOCT 2017), where one seeks to understand performance of testers with respect to parameters other than just the size. Our result is an adaptive monotonicity tester with one-sided error whose query complexity is O(epsilon^{-2}I(f)log^5 n), where I(f) is the total influence of the function. Therefore, adaptivity provably helps monotonicity testing for low influence functions.

Cite as

Deeparnab Chakrabarty and C. Seshadhri. Adaptive Boolean Monotonicity Testing in Total Influence Time. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 20:1-20:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)


Copy BibTex To Clipboard

@InProceedings{chakrabarty_et_al:LIPIcs.ITCS.2019.20,
  author =	{Chakrabarty, Deeparnab and Seshadhri, C.},
  title =	{{Adaptive Boolean Monotonicity Testing in Total Influence Time}},
  booktitle =	{10th Innovations in Theoretical Computer Science Conference (ITCS 2019)},
  pages =	{20:1--20:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-095-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{124},
  editor =	{Blum, Avrim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.20},
  URN =		{urn:nbn:de:0030-drops-101133},
  doi =		{10.4230/LIPIcs.ITCS.2019.20},
  annote =	{Keywords: Property Testing, Monotonicity Testing, Influence of Boolean Functions}
}
Document
Interpolating between k-Median and k-Center: Approximation Algorithms for Ordered k-Median

Authors: Deeparnab Chakrabarty and Chaitanya Swamy

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)


Abstract
We consider a generalization of k-median and k-center, called the ordered k-median problem. In this problem, we are given a metric space (D,{c_{ij}}) with n=|D| points, and a non-increasing weight vector w in R_+^n, and the goal is to open k centers and assign each point j in D to a center so as to minimize w_1 *(largest assignment cost)+w_2 *(second-largest assignment cost)+...+w_n *(n-th largest assignment cost). We give an (18+epsilon)-approximation algorithm for this problem. Our algorithms utilize Lagrangian relaxation and the primal-dual schema, combined with an enumeration procedure of Aouad and Segev. For the special case of {0,1}-weights, which models the problem of minimizing the l largest assignment costs that is interesting in and of by itself, we provide a novel reduction to the (standard) k-median problem, showing that LP-relative guarantees for k-median translate to guarantees for the ordered k-median problem; this yields a nice and clean (8.5+epsilon)-approximation algorithm for {0,1} weights.

Cite as

Deeparnab Chakrabarty and Chaitanya Swamy. Interpolating between k-Median and k-Center: Approximation Algorithms for Ordered k-Median. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 29:1-29:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{chakrabarty_et_al:LIPIcs.ICALP.2018.29,
  author =	{Chakrabarty, Deeparnab and Swamy, Chaitanya},
  title =	{{Interpolating between k-Median and k-Center: Approximation Algorithms for Ordered k-Median}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{29:1--29:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.29},
  URN =		{urn:nbn:de:0030-drops-90335},
  doi =		{10.4230/LIPIcs.ICALP.2018.29},
  annote =	{Keywords: Approximation algorithms, Clustering, Facility location, Primal-dual method}
}
Document
Generalized Center Problems with Outliers

Authors: Deeparnab Chakrabarty and Maryam Negahbani

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)


Abstract
We study the F-center problem with outliers: given a metric space (X,d), a general down-closed family F of subsets of X, and a parameter m, we need to locate a subset S in F of centers such that the maximum distance among the closest m points in X to S is minimized. Our main result is a dichotomy theorem. Colloquially, we prove that there is an efficient 3-approximation for the F-center problem with outliers if and only if we can efficiently optimize a poly-bounded linear function over F subject to a partition constraint. One concrete upshot of our result is a polynomial time 3-approximation for the knapsack center problem with outliers for which no (true) approximation algorithm was known.

Cite as

Deeparnab Chakrabarty and Maryam Negahbani. Generalized Center Problems with Outliers. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 30:1-30:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{chakrabarty_et_al:LIPIcs.ICALP.2018.30,
  author =	{Chakrabarty, Deeparnab and Negahbani, Maryam},
  title =	{{Generalized Center Problems with Outliers}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{30:1--30:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.30},
  URN =		{urn:nbn:de:0030-drops-90345},
  doi =		{10.4230/LIPIcs.ICALP.2018.30},
  annote =	{Keywords: Approximation Algorithms, Clustering, k-Center Problem}
}
Document
Better and Simpler Error Analysis of the Sinkhorn-Knopp Algorithm for Matrix Scaling

Authors: Deeparnab Chakrabarty and Sanjeev Khanna

Published in: OASIcs, Volume 61, 1st Symposium on Simplicity in Algorithms (SOSA 2018)


Abstract
Given a non-negative real matrix A, the matrix scaling problem is to determine if it is possible to scale the rows and columns so that each row and each column sums to a specified target value for it. The matrix scaling problem arises in many algorithmic applications, perhaps most notably as a preconditioning step in solving linear system of equations. One of the most natural and by now classical approach to matrix scaling is the Sinkhorn-Knopp algorithm (also known as the RAS method) where one alternately scales either all rows or all columns to meet the target values. In addition to being extremely simple and natural, another appeal of this procedure is that it easily lends itself to parallelization. A central question is to understand the rate of convergence of the Sinkhorn-Knopp algorithm. Specifically, given a suitable error metric to measure deviations from target values, and an error bound epsilon, how quickly does the Sinkhorn-Knopp algorithm converge to an error below epsilon? While there are several non-trivial convergence results known about the Sinkhorn-Knopp algorithm, perhaps somewhat surprisingly, even for natural error metrics such as ell_1-error or ell_2-error, this is not entirely understood. In this paper, we present an elementary convergence analysis for the Sinkhorn-Knopp algorithm that improves upon the previous best bound. In a nutshell, our approach is to show (i) a simple bound on the number of iterations needed so that the KL-divergence between the current row-sums and the target row-sums drops below a specified threshold delta, and (ii) then show that for a suitable choice of delta, whenever KL-divergence is below delta, then the ell_1-error or the ell_2-error is below epsilon. The well-known Pinsker's inequality immediately allows us to translate a bound on the KL divergence to a bound on ell_1-error. To bound the ell_2-error in terms of the KL-divergence, we establish a new inequality, referred to as (KL vs ell_1/ell_2) inequality in the paper. This new inequality is a strengthening of the Pinsker's inequality that we believe is of independent interest. Our analysis of ell_2-error significantly improves upon the best previous convergence bound for ell_2-error. The idea of studying Sinkhorn-Knopp convergence via KL-divergence is not new and has indeed been previously explored. Our contribution is an elementary, self-contained presentation of this approach and an interesting new inequality that yields a significantly stronger convergence guarantee for the extensively studied ell_2-error.

Cite as

Deeparnab Chakrabarty and Sanjeev Khanna. Better and Simpler Error Analysis of the Sinkhorn-Knopp Algorithm for Matrix Scaling. In 1st Symposium on Simplicity in Algorithms (SOSA 2018). Open Access Series in Informatics (OASIcs), Volume 61, pp. 4:1-4:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)


Copy BibTex To Clipboard

@InProceedings{chakrabarty_et_al:OASIcs.SOSA.2018.4,
  author =	{Chakrabarty, Deeparnab and Khanna, Sanjeev},
  title =	{{Better and Simpler Error Analysis of the  Sinkhorn-Knopp Algorithm for Matrix Scaling}},
  booktitle =	{1st Symposium on Simplicity in Algorithms (SOSA 2018)},
  pages =	{4:1--4:11},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-064-4},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{61},
  editor =	{Seidel, Raimund},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2018.4},
  URN =		{urn:nbn:de:0030-drops-83045},
  doi =		{10.4230/OASIcs.SOSA.2018.4},
  annote =	{Keywords: Matrix Scaling, Entropy Minimization, KL Divergence Inequalities}
}
Document
Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps

Authors: Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, and C. Seshadhri

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)


Abstract
We study the problem of testing unateness of functions f:{0,1}^d -> R. We give an O(d/\epsilon . log(d/\epsilon))-query nonadaptive tester and an O(d/\epsilon)-query adaptive tester and show that both testers are optimal for a fixed distance parameter \epsilon. Previously known unateness testers worked only for Boolean functions, and their query complexity had worse dependence on the dimension both for the adaptive and the nonadaptive case. Moreover, no lower bounds for testing unateness were known. We generalize our results to obtain optimal unateness testers for functions f:[n]^d -> R. Our results establish that adaptivity helps with testing unateness of real-valued functions on domains of the form {0,1}^d and, more generally, [n]^d. This stands in contrast to the situation for monotonicity testing where there is no adaptivity gap for functions f:[n]^d -> R.

Cite as

Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, and C. Seshadhri. Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 5:1-5:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InProceedings{baleshzar_et_al:LIPIcs.ICALP.2017.5,
  author =	{Baleshzar, Roksana and Chakrabarty, Deeparnab and Pallavoor, Ramesh Krishnan S. and Raskhodnikova, Sofya and Seshadhri, C.},
  title =	{{Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{5:1--5:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.5},
  URN =		{urn:nbn:de:0030-drops-74844},
  doi =		{10.4230/LIPIcs.ICALP.2017.5},
  annote =	{Keywords: Property testing, unate and monotone functions}
}
Document
The Non-Uniform k-Center Problem

Authors: Deeparnab Chakrabarty, Prachi Goyal, and Ravishankar Krishnaswamy

Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)


Abstract
In this paper, we introduce and study the Non-Uniform k-Center (NUkC) problem. Given a finite metric space (X, d) and a collection of balls of radii {r_1 >= ... >= r_k}, the NUkC problem is to find a placement of their centers on the metric space and find the minimum dilation alpha, such that the union of balls of radius alpha*r_i around the i-th center covers all the points in X. This problem naturally arises as a min-max vehicle routing problem with fleets of different speeds, or as a wireless router placement problem with routers of different powers/ranges. The NUkC problem generalizes the classic k-center problem when all the k radii are the same (which can be assumed to be 1 after scaling). It also generalizes the k-center with outliers (kCwO for short) problem when there are k balls of radius 1 and l balls of radius 0. There are 2-approximation and 3-approximation algorithms known for these problems respectively; the former is best possible unless P=NP and the latter remains unimproved for 15 years. We first observe that no O(1)-approximation is to the optimal dilation is possible unless P=NP, implying that the NUkC problem is more non-trivial than the above two problems. Our main algorithmic result is an (O(1), O(1))-bi-criteria approximation result: we give an O(1)-approximation to the optimal dilation, however, we may open Theta(1) centers of each radii. Our techniques also allow us to prove a simple (uni-criteria), optimal 2-approximation to the kCwO problem improving upon the long-standing 3-factor. Our main technical contribution is a connection between the NUkC problem and the so-called firefighter problems on trees which have been studied recently in the TCS community. We show NUkC is as hard as the firefighter problem. While we don't know if the converse is true, we are able to adapt ideas from recent works [Chalermsook/Chuzhoy, SODA 2010; Asjiashvili/Baggio/Zenklusen, arXiv 2016] in non-trivial ways to obtain our constant factor bi-criteria approximation.

Cite as

Deeparnab Chakrabarty, Prachi Goyal, and Ravishankar Krishnaswamy. The Non-Uniform k-Center Problem. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 67:1-67:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{chakrabarty_et_al:LIPIcs.ICALP.2016.67,
  author =	{Chakrabarty, Deeparnab and Goyal, Prachi and Krishnaswamy, Ravishankar},
  title =	{{The Non-Uniform k-Center Problem}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{67:1--67:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.67},
  URN =		{urn:nbn:de:0030-drops-62178},
  doi =		{10.4230/LIPIcs.ICALP.2016.67},
  annote =	{Keywords: Clustering, k-Center, Approximation Algorithms, Firefighter Problem}
}
Document
Algorithms for Message Ferrying on Mobile ad hoc Networks

Authors: Mostafa Ammar, Deeparnab Chakrabarty, Atish Das Sarma, Subrahmanyam Kalyanasundaram, and Richard J. Lipton

Published in: LIPIcs, Volume 4, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2009)


Abstract
Message Ferrying is a mobility assisted technique for working around the disconnectedness and sparsity of Mobile ad hoc networks. One of the importantquestions which arise in this context is to determine the routing of the ferry,so as to minimize the buffers used to store data at the nodes in thenetwork. We introduce a simple model to capture the ferry routingproblem. We characterize {\em stable} solutions of the system andprovide efficient approximation algorithms for the {\sc Min-Max Buffer Problem} for the case when the nodes are onhierarchically separated metric spaces.

Cite as

Mostafa Ammar, Deeparnab Chakrabarty, Atish Das Sarma, Subrahmanyam Kalyanasundaram, and Richard J. Lipton. Algorithms for Message Ferrying on Mobile ad hoc Networks. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 4, pp. 13-24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)


Copy BibTex To Clipboard

@InProceedings{ammar_et_al:LIPIcs.FSTTCS.2009.2303,
  author =	{Ammar, Mostafa and Chakrabarty, Deeparnab and Sarma, Atish Das and Kalyanasundaram, Subrahmanyam and Lipton, Richard J.},
  title =	{{Algorithms for Message Ferrying on Mobile ad hoc Networks}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
  pages =	{13--24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-13-2},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{4},
  editor =	{Kannan, Ravi and Narayan Kumar, K.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2009.2303},
  URN =		{urn:nbn:de:0030-drops-23031},
  doi =		{10.4230/LIPIcs.FSTTCS.2009.2303},
  annote =	{Keywords: Algorithms, Network Algorithms, Routing, TSP, Buffer Optimization}
}
  • Refine by Author
  • 12 Chakrabarty, Deeparnab
  • 3 Negahbani, Maryam
  • 3 Swamy, Chaitanya
  • 2 Khanna, Sanjeev
  • 2 Sarkar, Ankita
  • Show More...

  • Refine by Classification
  • 6 Theory of computation → Facility location and clustering
  • 2 Theory of computation → Approximation algorithms analysis
  • 1 Theory of computation
  • 1 Theory of computation → Convex optimization
  • 1 Theory of computation → Dynamic graph algorithms
  • Show More...

  • Refine by Keyword
  • 6 Clustering
  • 4 Approximation Algorithms
  • 2 Approximation algorithms
  • 2 Fairness
  • 2 Outliers
  • Show More...

  • Refine by Type
  • 15 document

  • Refine by Publication Year
  • 3 2018
  • 3 2019
  • 3 2021
  • 1 2009
  • 1 2016
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail