Search Results

Documents authored by Bajpai, Tanvi

Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.25
Covering a Few Submodular Constraints and Applications

Authors: Tanvi Bajpai, Chandra Chekuri, and Pooja Kulkarni

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
We consider the problem of covering multiple submodular constraints. Given a finite ground set N, a cost function c: N → ℝ_+, r monotone submodular functions f_1,f_2,…,f_r over N and requirements b_1,b_2,…,b_r the goal is to find a minimum cost subset S ⊆ N such that f_i(S) ≥ b_i for 1 ≤ i ≤ r. When r = 1 this is the well-known Submodular Set Cover problem. Previous work [Chekuri et al., 2022] considered the setting when r is large and developed bi-criteria approximation algorithms, and approximation algorithms for the important special case when each f_i is a weighted coverage function. These are fairly general models and capture several concrete and interesting problems as special cases. The approximation ratios for these problem are at least Ω(log r) which is unavoidable when r is part of the input. In this paper, motivated by some recent applications, we consider the problem when r is a fixed constant and obtain two main results. When the f_i are weighted coverage functions from a deletion-closed set system we obtain a (1+ε)(e/(e-1))(1+β)-approximation where β is the approximation ratio for the underlying set cover instances via the natural LP. Second, for covering multiple submodular constraints we obtain a randomized bi-criteria approximation algorithm that for any given integer α ≥ 1 outputs a set S such that f_i(S) ≥ (1-1/e^α-ε)b_i for each i ∈ [r] and 𝔼[c(S)] ≤ (1+ε)α ⋅ OPT. These results show that one can obtain nearly as good an approximation for any fixed r as what one would achieve for r = 1. We also demonstrate applications of our results to implicit covering problems such as fair facility location.
Cite as

Tanvi Bajpai, Chandra Chekuri, and Pooja Kulkarni. Covering a Few Submodular Constraints and Applications. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 25:1-25:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bajpai_et_al:LIPIcs.APPROX/RANDOM.2025.25,
  author =	{Bajpai, Tanvi and Chekuri, Chandra and Kulkarni, Pooja},
  title =	{{Covering a Few Submodular Constraints and Applications}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{25:1--25:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.25},
  URN =		{urn:nbn:de:0030-drops-243917},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.25},
  annote =	{Keywords: covering, linear programming, rounding, fairness}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.7
Bicriteria Approximation Algorithms for Priority Matroid Median

Authors: Tanvi Bajpai and Chandra Chekuri

Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)

Abstract
Fairness considerations have motivated new clustering problems and algorithms in recent years. In this paper we consider the Priority Matroid Median problem which generalizes the Priority k-Median problem that has recently been studied. The input consists of a set of facilities ℱ and a set of clients 𝒞 that lie in a metric space (ℱ ∪ 𝒞,d), and a matroid ℳ = (ℱ,ℐ) over the facilities. In addition, each client j has a specified radius r_j ≥ 0 and each facility i ∈ ℱ has an opening cost f_i > 0. The goal is to choose a subset S ⊆ ℱ of facilities to minimize ∑_{i ∈ ℱ} f_i + ∑_{j ∈ 𝒞} d(j,S) subject to two constraints: (i) S is an independent set in ℳ (that is S ∈ ℐ) and (ii) for each client j, its distance to an open facility is at most r_j (that is, d(j,S) ≤ r_j). For this problem we describe the first bicriteria (c₁,c₂) approximations for fixed constants c₁,c₂: the radius constraints of the clients are violated by at most a factor of c₁ and the objective cost is at most c₂ times the optimum cost. We also improve the previously known bicriteria approximation for the uniform radius setting (r_j : = L ∀ j ∈ 𝒞).
Cite as

Tanvi Bajpai and Chandra Chekuri. Bicriteria Approximation Algorithms for Priority Matroid Median. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 7:1-7:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{bajpai_et_al:LIPIcs.APPROX/RANDOM.2023.7,
  author =	{Bajpai, Tanvi and Chekuri, Chandra},
  title =	{{Bicriteria Approximation Algorithms for Priority Matroid Median}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{7:1--7:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-296-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{275},
  editor =	{Megow, Nicole and Smith, Adam},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.7},
  URN =		{urn:nbn:de:0030-drops-188328},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.7},
  annote =	{Keywords: k-median, fair clustering, matroid}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.21
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.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}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact