3 Search Results for "Sonar, Chinmay"

Document
DOI: 10.4230/LIPIcs.IPEC.2025.9
An ETH-Tight FPT Algorithm for Rejection-Proof Set Packing with Applications to Kidney Exchange

Authors: Bart M. P. Jansen, Jeroen S. K. Lamme, and Ruben F. A. Verhaegh

Published in: LIPIcs, Volume 358, 20th International Symposium on Parameterized and Exact Computation (IPEC 2025)

Abstract
We study the parameterized complexity of a recently introduced multi-agent variant of the Kidney Exchange problem. Given a directed graph G and integers d and k, the standard problem asks whether G contains a packing of vertex-disjoint cycles, each of length ≤ d, covering at least k vertices in total. In the multi-agent setting we consider, the vertex set is partitioned over several agents who reject a cycle packing as solution if it can be modified into an alternative packing that covers more of their own vertices. A cycle packing is called rejection-proof if no agent rejects it and the problem asks whether such a packing exists that covers at least k vertices. We exploit the sunflower lemma on a set packing formulation of the problem to give a kernel for this Σ₂^P-complete problem that is polynomial in k for all constant values of d. We also provide a 2^𝒪(k log k) + n^𝒪(1) algorithm based on it and show that this FPT algorithm is asymptotically optimal under the ETH. Further, we generalize the problem by including an additional positive integer c in the input that naturally captures how much agents can modify a given cycle packing to reject it. For every constant c, the resulting problem simplifies from being Σ₂^P-complete to NP-complete. The super-exponential lower bound already holds for c = 2, though. We present an ad-hoc single-exponential algorithm for c = 1. These results reveal an interesting discrepancy between the classical and parameterized complexity of the problem and give a good view of what makes it hard.
Cite as

Bart M. P. Jansen, Jeroen S. K. Lamme, and Ruben F. A. Verhaegh. An ETH-Tight FPT Algorithm for Rejection-Proof Set Packing with Applications to Kidney Exchange. In 20th International Symposium on Parameterized and Exact Computation (IPEC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 358, pp. 9:1-9:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{jansen_et_al:LIPIcs.IPEC.2025.9,
  author =	{Jansen, Bart M. P. and Lamme, Jeroen S. K. and Verhaegh, Ruben F. A.},
  title =	{{An ETH-Tight FPT Algorithm for Rejection-Proof Set Packing with Applications to Kidney Exchange}},
  booktitle =	{20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
  pages =	{9:1--9:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-407-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{358},
  editor =	{Agrawal, Akanksha and van Leeuwen, Erik Jan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2025.9},
  URN =		{urn:nbn:de:0030-drops-251414},
  doi =		{10.4230/LIPIcs.IPEC.2025.9},
  annote =	{Keywords: Parameterized complexity, Multi-agent kidney exchange, Kernelization, Set packing}
}
Document
DOI: 10.4230/LIPIcs.ESA.2023.95
Fault Tolerance in Euclidean Committee Selection

Authors: Chinmay Sonar, Subhash Suri, and Jie Xue

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract
In the committee selection problem, the goal is to choose a subset of size k from a set of candidates C that collectively gives the best representation to a set of voters. We consider this problem in Euclidean d-space where each voter/candidate is a point and voters' preferences are implicitly represented by Euclidean distances to candidates. We explore fault-tolerance in committee selection and study the following three variants: (1) given a committee and a set of f failing candidates, find their optimal replacement; (2) compute the worst-case replacement score for a given committee under failure of f candidates; and (3) design a committee with the best replacement score under worst-case failures. The score of a committee is determined using the well-known (min-max) Chamberlin-Courant rule: minimize the maximum distance between any voter and its closest candidate in the committee. Our main results include the following: (1) in one dimension, all three problems can be solved in polynomial time; (2) in dimension d ≥ 2, all three problems are NP-hard; and (3) all three problems admit a constant-factor approximation in any fixed dimension, and the optimal committee problem has an FPT bicriterion approximation.
Cite as

Chinmay Sonar, Subhash Suri, and Jie Xue. Fault Tolerance in Euclidean Committee Selection. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 95:1-95:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{sonar_et_al:LIPIcs.ESA.2023.95,
  author =	{Sonar, Chinmay and Suri, Subhash and Xue, Jie},
  title =	{{Fault Tolerance in Euclidean Committee Selection}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{95:1--95:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.95},
  URN =		{urn:nbn:de:0030-drops-187489},
  doi =		{10.4230/LIPIcs.ESA.2023.95},
  annote =	{Keywords: Multiwinner elections, Fault tolerance, Geometric Hitting Set, EPTAS}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2021.32
Anonymity-Preserving Space Partitions

Authors: Úrsula Hébert-Johnson, Chinmay Sonar, Subhash Suri, and Vaishali Surianarayanan

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)

Abstract
We consider a multidimensional space partitioning problem, which we call Anonymity-Preserving Partition. Given a set P of n points in ℝ^d and a collection H of m axis-parallel hyperplanes, the hyperplanes of H partition the space into an arrangement A(H) of rectangular cells. Given an integer parameter t > 0, we call a cell C in this arrangement deficient if 0 < |C ∩ P| < t; that is, the cell contains at least one but fewer than t data points of P. Our problem is to remove the minimum number of hyperplanes from H so that there are no deficient cells. We show that the problem is NP-complete for all dimensions d ≥ 2. We present a polynomial-time d-approximation algorithm, for any fixed d, and we also show that the problem can be solved exactly in time (2d-0.924)^k m^O(1) + O(n), where k is the solution size. The one-dimensional case of the problem, where all hyperplanes are parallel, can be solved optimally in polynomial time, but we show that a related Interval Anonymity problem is NP-complete even in one dimension.
Cite as

Úrsula Hébert-Johnson, Chinmay Sonar, Subhash Suri, and Vaishali Surianarayanan. Anonymity-Preserving Space Partitions. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 32:1-32:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{hebertjohnson_et_al:LIPIcs.ISAAC.2021.32,
  author =	{H\'{e}bert-Johnson, \'{U}rsula and Sonar, Chinmay and Suri, Subhash and Surianarayanan, Vaishali},
  title =	{{Anonymity-Preserving Space Partitions}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{32:1--32:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.32},
  URN =		{urn:nbn:de:0030-drops-154654},
  doi =		{10.4230/LIPIcs.ISAAC.2021.32},
  annote =	{Keywords: Anonymity, Hitting Set, LP, Constant Approximation, Fixed-Parameter Tractable, Space Partitions, Parameterized Complexity}
}
  • Refine by Type
  • 3 Document/PDF
  • 1 Document/HTML

  • Refine by Publication Year
  • 1 2025
  • 1 2023
  • 1 2021

  • Refine by Author
  • 2 Sonar, Chinmay
  • 2 Suri, Subhash
  • 1 Hébert-Johnson, Úrsula
  • 1 Jansen, Bart M. P.
  • 1 Lamme, Jeroen S. K.
  • Show More...

  • Refine by Series/Journal
  • 3 LIPIcs

  • Refine by Classification
  • 1 Applied computing → Health informatics
  • 1 Mathematics of computing → Combinatorial algorithms
  • 1 Theory of computation → Algorithmic game theory
  • 1 Theory of computation → Design and analysis of algorithms
  • 1 Theory of computation → Parameterized complexity and exact algorithms
  • Show More...

  • Refine by Keyword
  • 1 Anonymity
  • 1 Constant Approximation
  • 1 EPTAS
  • 1 Fault tolerance
  • 1 Fixed-Parameter Tractable
  • Show More...

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-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact