Search Results

Documents authored by Dey, Palash

Document
DOI: 10.4230/LIPIcs.ISAAC.2024.27
Knapsack with Vertex Cover, Set Cover, and Hitting Set

Authors: Palash Dey, Ashlesha Hota, Sudeshna Kolay, and Sipra Singh

Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)

Abstract
In the Vertex Cover Knapsack problem, we are given an undirected graph G = (V, E), with weights (w(u))_{u ∈ V} and values (𝛂(u))_{u ∈ V} of the vertices, the size s of the knapsack, a target value p, and the goal is to compute if there exists a vertex cover U ⊆ V with total weight at most s, and total value at least p. This problem simultaneously generalizes the classical vertex cover and knapsack problems. We show that this problem is strongly NP-complete. However, it admits a pseudo-polynomial time algorithm for trees. In fact, we show that there is an algorithm that runs in time O (2^tw ⋅ n ⋅ min) where tw is the treewidth of G. Moreover, we can compute a (1-ε)- approximate solution for maximizing the value of the solution given the knapsack size as input in time O (2^tw ⋅ poly(n,1/ε,log(∑_{v ∈ V} 𝛂(v)))) and a (1+ε)-approximate solution to minimize the size of the solution given a target value as input, in time O (2^tw ⋅ poly(n,1/ε,log(∑_{v ∈ V} w(v)))) for every ε > 0. Restricting our attention to polynomial-time algorithms only, we then consider polynomial-time algorithms and present a 2 factor polynomial-time approximation algorithm for this problem for minimizing the total weight of the solution, which is optimal up to additive o(1) assuming Unique Games Conjecture (UGC). On the other hand, we show that there is no ρ factor polynomial-time approximation algorithm for maximizing the total value of the solution given a knapsack size for any ρ > 1 unless 𝖯 = NP. Furthermore, we show similar results for the variants of the above problem when the solution U needs to be a minimal vertex cover, minimum vertex cover, and vertex cover of size at most k for some input integer k. Then, we consider set families (equivalently hypergraphs) and study the variants of the above problem when the solution needs to be a set cover and hitting set. We show that there are H_d and f factor polynomial-time approximation algorithms for Set Cover Knapsack where d is the maximum cardinality of any set and f is the maximum number of sets in the family where any element can belongs in the input for minimizing the weight of the knapsack given a target value, and a d factor polynomial-time approximation algorithm for d-Hitting Set Knapsack which are optimal up to additive o(1) assuming UGC. On the other hand, we show that there is no ρ factor polynomial-time approximation algorithm for maximizing the total value of the solution given a knapsack size for any ρ > 1 unless 𝖯 = NP for both Set Cover Knapsack and d-Hitting Set Knapsack.
Cite as

Palash Dey, Ashlesha Hota, Sudeshna Kolay, and Sipra Singh. Knapsack with Vertex Cover, Set Cover, and Hitting Set. In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 27:1-27:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dey_et_al:LIPIcs.ISAAC.2024.27,
  author =	{Dey, Palash and Hota, Ashlesha and Kolay, Sudeshna and Singh, Sipra},
  title =	{{Knapsack with Vertex Cover, Set Cover, and Hitting Set}},
  booktitle =	{35th International Symposium on Algorithms and Computation (ISAAC 2024)},
  pages =	{27:1--27:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-354-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{322},
  editor =	{Mestre, Juli\'{a}n and Wirth, Anthony},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.27},
  URN =		{urn:nbn:de:0030-drops-221540},
  doi =		{10.4230/LIPIcs.ISAAC.2024.27},
  annote =	{Keywords: Knapsack, vertex cover, minimal vertex cover, minimum vertex cover, hitting set, set cover, algorithm, approximation algorithm, parameterized complexity}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2020.28
Improved Explicit Data Structures in the Bit-Probe Model Using Error-Correcting Codes

Authors: Palash Dey, Jaikumar Radhakrishnan, and Santhoshini Velusamy

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Abstract
We consider the bit-probe complexity of the set membership problem: represent an n-element subset S of an m-element universe as a succinct bit vector so that membership queries of the form "Is x ∈ S" can be answered using at most t probes into the bit vector. Let s(m,n,t) (resp. s_N(m,n,t)) denote the minimum number of bits of storage needed when the probes are adaptive (resp. non-adaptive). Lewenstein, Munro, Nicholson, and Raman (ESA 2014) obtain fully-explicit schemes that show that s(m,n,t) = 𝒪((2^t-1)m^{1/(t - min{2⌊log n⌋, n-3/2})}) for n ≥ 2,t ≥ ⌊log n⌋+1 . In this work, we improve this bound when the probes are allowed to be superlinear in n, i.e., when t ≥ Ω(nlog n), n ≥ 2, we design fully-explicit schemes that show that s(m,n,t) = 𝒪((2^t-1)m^{1/(t-{n-1}/{2^{t/(2(n-1))}})}), asymptotically (in the exponent of m) close to the non-explicit upper bound on s(m,n,t) derived by Radhakrishan, Shah, and Shannigrahi (ESA 2010), for constant n. In the non-adaptive setting, it was shown by Garg and Radhakrishnan (STACS 2017) that for a large constant n₀, for n ≥ n₀, s_N(m,n,3) ≥ √{mn}. We improve this result by showing that the same lower bound holds even for storing sets of size 2, i.e., s_N(m,2,3) ≥ Ω(√m).
Cite as

Palash Dey, Jaikumar Radhakrishnan, and Santhoshini Velusamy. Improved Explicit Data Structures in the Bit-Probe Model Using Error-Correcting Codes. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 28:1-28:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{dey_et_al:LIPIcs.MFCS.2020.28,
  author =	{Dey, Palash and Radhakrishnan, Jaikumar and Velusamy, Santhoshini},
  title =	{{Improved Explicit Data Structures in the Bit-Probe Model Using Error-Correcting Codes}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{28:1--28:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.28},
  URN =		{urn:nbn:de:0030-drops-126965},
  doi =		{10.4230/LIPIcs.MFCS.2020.28},
  annote =	{Keywords: Set membership, Bit-probe model, Fully-explicit data structures, Adaptive data structures, Error-correcting codes}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2017.57
On the Exact Amount of Missing Information that Makes Finding Possible Winners Hard

Authors: Palash Dey and Neeldhara Misra

Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

Abstract
We consider election scenarios with incomplete information, a situation that arises often in practice. There are several models of incomplete information and accordingly, different notions of outcomes of such elections. In one well-studied model of incompleteness, the votes are given by partial orders over the candidates. In this context we can frame the problem of finding a possible winner, which involves determining whether a given candidate wins in at least one completion of a given set of partial votes for a specific voting rule. The Possible Winner problem is well-known to be NP-Complete in general, and it is in fact known to be NP-Complete for several voting rules where the number of undetermined pairs in every vote is bounded only by some constant. In this paper, we address the question of determining precisely the smallest number of undetermined pairs for which the Possible Winner problem remains NP-Complete. In particular, we find the exact values of t for which the Possible Winner problem transitions to being NP-Complete from being in P, where t is the maximum number of undetermined pairs in every vote. We demonstrate tight results for a broad subclass of scoring rules which includes all the commonly used scoring rules (such as plurality, veto, Borda, and k-approval), Copeland^\alpha for every \alpha in [0,1], maximin, and Bucklin voting rules. A somewhat surprising aspect of our results is that for many of these rules, the Possible Winner problem turns out to be hard even if every vote has at most one undetermined pair of candidates.
Cite as

Palash Dey and Neeldhara Misra. On the Exact Amount of Missing Information that Makes Finding Possible Winners Hard. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 57:1-57:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{dey_et_al:LIPIcs.MFCS.2017.57,
  author =	{Dey, Palash and Misra, Neeldhara},
  title =	{{On the Exact Amount of Missing Information that Makes Finding Possible Winners Hard}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{57:1--57:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.57},
  URN =		{urn:nbn:de:0030-drops-81354},
  doi =		{10.4230/LIPIcs.MFCS.2017.57},
  annote =	{Keywords: Computational Social Choice, Dichotomy, NP-completeness, Maxflow, Voting, Possible winner}
}
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact