Search Results

Documents authored by Gupta, Manoj

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.38
The Group Access Bounds for Binary Search Trees

Authors: Parinya Chalermsook, Manoj Gupta, Wanchote Jiamjitrak, Akash Pareek, and Sorrachai Yingchareonthawornchai

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
The access lemma (Sleator and Tarjan, JACM 1985) is a property of binary search trees (BSTs) that implies interesting consequences such as static optimality, static finger, and working set property on any access sequence X = (x_1,x_2,… ,x_m). However, there are known corollaries of the dynamic optimality that cannot be derived via the access lemma, such as the dynamic finger, and any o(log n)-competitive ratio to the optimal BST where n is the number of keys. In this paper, we introduce the group access bound that can be defined with respect to a reference group access tree. Group access bounds generalize the access lemma and imply properties that are far stronger than those implied by the classical access lemma. For each of the following results, there is a group access tree whose group access bound 1) Is O(√{log n})-competitive to the optimal BST. 2) Achieves the k-finger bound with an additive term of O(m log k log log n) (randomized) when the reference tree is an almost complete binary tree. 3) Satisfies the unified bound with an additive term of O(m log log n). 4) Matches the unified bound with a time window k with an additive term of O(m log k log log n) (randomized). Furthermore, we prove the simulation theorem: For every group access tree, there is an online BST algorithm that is O(1)-competitive with its group access bound. In particular, any new group access bound will automatically imply a new BST algorithm achieving the same bound. Thereby, we obtain an improved k-finger bound (reference tree is an almost complete binary tree), an improved unified bound with a time window k, and matching the best-known bound for Unified bound in the BST model. Since any dynamically optimal BST must achieve the group access bounds, we believe our results provide a new direction towards proving o(log n)-competitiveness of the Splay tree and Greedy, two prime candidates for the dynamic optimality conjecture.
Cite as

Parinya Chalermsook, Manoj Gupta, Wanchote Jiamjitrak, Akash Pareek, and Sorrachai Yingchareonthawornchai. The Group Access Bounds for Binary Search Trees. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 38:1-38:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chalermsook_et_al:LIPIcs.ICALP.2024.38,
  author =	{Chalermsook, Parinya and Gupta, Manoj and Jiamjitrak, Wanchote and Pareek, Akash and Yingchareonthawornchai, Sorrachai},
  title =	{{The Group Access Bounds for Binary Search Trees}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{38:1--38:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.38},
  URN =		{urn:nbn:de:0030-drops-201817},
  doi =		{10.4230/LIPIcs.ICALP.2024.38},
  annote =	{Keywords: Dynamic Optimality, Binary Search Tree, Online Algorithm}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.42
Near Optimal Algorithm for Fault Tolerant Distance Oracle and Single Source Replacement Path Problem

Authors: Dipan Dey and Manoj Gupta

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

Abstract
In a graph G with a source s, we design a distance oracle that can answer the following query: Query(s,t,e) - find the length of shortest path from a fixed source s to any destination vertex t while avoiding any edge e. We design a deterministic algorithm that builds such an oracle in Õ(m √n) time. Our oracle uses Õ(n √n) space and can answer queries in Õ(1) time. Our oracle is an improvement of the work of Bilò et al. (ESA 2021) in the preprocessing time, which constructs the first deterministic oracle for this problem in Õ(m √n+n²) time. Using our distance oracle, we also solve the single source replacement path problem (Ssrp problem). Chechik and Cohen (SODA 2019) designed a randomized combinatorial algorithm to solve the Ssrp problem. The running time of their algorithm is Õ(m √n + n²). In this paper, we show that the Ssrp problem can be solved in Õ(m √n + |ℛ|) time, where ℛ is the output set of the Ssrp problem in G. Our Ssrp algorithm is optimal (upto polylogarithmic factor) as there is a conditional lower bound of Ω(m √n) for any combinatorial algorithm that solves this problem.
Cite as

Dipan Dey and Manoj Gupta. Near Optimal Algorithm for Fault Tolerant Distance Oracle and Single Source Replacement Path Problem. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 42:1-42:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{dey_et_al:LIPIcs.ESA.2022.42,
  author =	{Dey, Dipan and Gupta, Manoj},
  title =	{{Near Optimal Algorithm for Fault Tolerant Distance Oracle and Single Source Replacement Path Problem}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{42:1--42:18},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.42},
  URN =		{urn:nbn:de:0030-drops-169800},
  doi =		{10.4230/LIPIcs.ESA.2022.42},
  annote =	{Keywords: distance sensitivity oracle, single-source replacement paths}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.72
Generic Single Edge Fault Tolerant Exact Distance Oracle

Authors: Manoj Gupta and Aditi Singh

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

Abstract
Given an undirected unweighted graph G and a source set S of |S| = sigma sources, we want to build a data structure which can process the following query Q(s,t,e): find the shortest distance from s to t avoiding an edge e, where s in S and t in V. When sigma=n, Demetrescu, Thorup, Chowdhury and Ramachandran (SIAM Journal of Computing, 2008) designed an algorithm with O~(n^2) space and O(1) query time. A natural open question is to generalize this result to any number of sources. Recently, Bil{ò} et. al. (STACS 2018) designed a data-structure of size O~(sigma^{1/2}n^{3/2}) with the query time of O(sqrt{n sigma}) for the above problem. We improve their result by designing a data-structure of size O~(sigma^{1/2} n^{3/2}) that can answer queries in O~(1) time. In a related problem of finding fault tolerant subgraph, Parter and Peleg (ESA 2013) showed that if detours of replacement paths ending at a vertex t are disjoint, then the number of such paths is O(sqrt{n sigma}). This eventually gives a bound of O(n sqrt{n sigma}) = O(sigma^{1/2}n^{3/2}) for their problem. Disjointness of detours is a very crucial property used in the above result. We show a similar result for a subset of replacement path which may not be disjoint. This result is the crux of our paper and may be of independent interest.
Cite as

Manoj Gupta and Aditi Singh. Generic Single Edge Fault Tolerant Exact Distance Oracle. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 72:1-72:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{gupta_et_al:LIPIcs.ICALP.2018.72,
  author =	{Gupta, Manoj and Singh, Aditi},
  title =	{{Generic Single Edge Fault Tolerant Exact Distance Oracle}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{72:1--72:15},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.72},
  URN =		{urn:nbn:de:0030-drops-90766},
  doi =		{10.4230/LIPIcs.ICALP.2018.72},
  annote =	{Keywords: Fault Tolerant Algorithms, Graph Algorithms, Distance Oracles, Data-Structures}
}
Document
DOI: 10.4230/LIPIcs.ESA.2017.15
Improved Algorithm for Dynamic b-Matching

Authors: Sayan Bhattacharya, Manoj Gupta, and Divyarthi Mohan

Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)

Abstract
Recently there has been extensive work on maintaining (approximate) maximum matchings in dynamic graphs. We consider a generalisation of this problem known as the maximum b-matching: Every node v has a positive integral capacity b_v, and the goal is to maintain an (approximate) maximum-cardinality subset of edges that contains at most b_v edges incident on every node v. The maximum matching problem is a special case of this problem where b_v = 1 for every node v. Bhattacharya, Henzinger and Italiano [ICALP 2015] showed how to maintain a O(1) approximate maximum b-matching in a graph in O(log^3 n) amortised update time. Their approximation ratio was a large (double digit) constant. We significantly improve their result both in terms of approximation ratio as well as update time. Specifically, we design a randomised dynamic algorithm that maintains a (2+epsilon)-approximate maximum $b$-matching in expected amortised O(1/epsilon^4) update time. Thus, for every constant epsilon in (0, 1), we get expected amortised O(1) update time. Our algorithm generalises the framework of Baswana, Gupta, Sen [FOCS 2011] and Solomon [FOCS 2016] for maintaining a maximal matching in a dynamic graph.
Cite as

Sayan Bhattacharya, Manoj Gupta, and Divyarthi Mohan. Improved Algorithm for Dynamic b-Matching. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 15:1-15:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{bhattacharya_et_al:LIPIcs.ESA.2017.15,
  author =	{Bhattacharya, Sayan and Gupta, Manoj and Mohan, Divyarthi},
  title =	{{Improved Algorithm for Dynamic b-Matching}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{15:1--15:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Pruhs, Kirk and Sohler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.15},
  URN =		{urn:nbn:de:0030-drops-78443},
  doi =		{10.4230/LIPIcs.ESA.2017.15},
  annote =	{Keywords: dynamic data structures, graph algorithms}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2017.127
Multiple Source Dual Fault Tolerant BFS Trees

Authors: Manoj Gupta and Shahbaz Khan

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

Abstract
Let G=(V,E) be a graph with n vertices and m edges, with a designated set of sigma sources S subseteq V. The fault tolerant subgraph for any graph problem maintains a sparse subgraph H=(V,E') of G with E' subseteq E, such that for any set F of k failures, the solution for the graph problem on G\F is maintained in its subgraph H\F. We address the problem of maintaining a fault tolerant subgraph for computing Breath First Search tree (BFS) of the graph from a single source s in V (referred as k FT-BFS) or multiple sources S subseteq V (referred as k FT-MBFS). We simply refer to them as FT-BFS (or FT-MBFS) for k=1, and dual FT-BFS (or dual FT-MBFS) for k=2. The problem of k FT-BFS was first studied by Parter and Peleg [ESA13]. They designed an algorithm to compute FT-BFS subgraph of size O(n^{3/2}). Further, they showed how their algorithm can be easily extended to FT-MBFS requiring O(sigma^{1/2}n^{3/2}) space. They also presented matching lower bounds for these results. The result was later extended to solve dual FT-BFS by Parter [PODC15] requiring (n^{5/3}) space, again with matching lower bounds. However, their result was limited to only edge failures in undirected graphs and involved very complex analysis. Moreover, their solution doesn't seems to be directly extendible for dual FT-MBFS problem. We present a similar algorithm to solve dual FT-BFS problem with a much simpler analysis. Moreover, our algorithm also works for vertex failures and directed graphs, and can be easily extended to handle dual FT-MBFS problem, matching the lower bound of O(sigma^{1/3}n^{5/3}) space described by Parter [PODC15]. The key difference in our approach is a much simpler classification of path interactions which formed the basis of the analysis by Parter [PODC15].
Cite as

Manoj Gupta and Shahbaz Khan. Multiple Source Dual Fault Tolerant BFS Trees. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 127:1-127:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{gupta_et_al:LIPIcs.ICALP.2017.127,
  author =	{Gupta, Manoj and Khan, Shahbaz},
  title =	{{Multiple Source Dual Fault Tolerant BFS Trees}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{127:1--127:15},
  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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.127},
  URN =		{urn:nbn:de:0030-drops-74184},
  doi =		{10.4230/LIPIcs.ICALP.2017.127},
  annote =	{Keywords: BFS, fault-tolerant, graph, algorithms, data-structures}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2014.227
Maintaining Approximate Maximum Matching in an Incremental Bipartite Graph in Polylogarithmic Update Time

Authors: Manoj Gupta

Published in: LIPIcs, Volume 29, 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)

Abstract
A sparse subgraph G' of G is called a matching sparsifier if the size or weight of matching in G' is approximately equal to the size or weight of maximum matching in G. Recently, algorithms have been developed to find matching sparsifiers in a static bipartite graph. In this paper, we show that we can find matching sparsifier even in an incremental bipartite graph. This observation leads to following results: 1. We design an algorithm that maintains a (1+epsilon) approximate matching in an incremental bipartite graph in O(log^2(n) / (epsilon^{4}) update time. 2. For weighted graphs, we design an algorithm that maintains (1+epsilon) approximate weighted matching in O((log(n)*log(n*N)) / (epsilon^4) update time where \maxweight is the maximum weight of any edge in the graph.
Cite as

Manoj Gupta. Maintaining Approximate Maximum Matching in an Incremental Bipartite Graph in Polylogarithmic Update Time. In 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 29, pp. 227-239, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{gupta:LIPIcs.FSTTCS.2014.227,
  author =	{Gupta, Manoj},
  title =	{{Maintaining Approximate Maximum Matching in an Incremental Bipartite Graph in Polylogarithmic Update Time}},
  booktitle =	{34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)},
  pages =	{227--239},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-77-4},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{29},
  editor =	{Raman, Venkatesh and Suresh, S. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2014.227},
  URN =		{urn:nbn:de:0030-drops-48453},
  doi =		{10.4230/LIPIcs.FSTTCS.2014.227},
  annote =	{Keywords: Graph Algorithm, Dynamic Graph}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2012.257
Maintaining Approximate Maximum Weighted Matching in Fully Dynamic Graphs

Authors: Abhash Anand, Surender Baswana, Manoj Gupta, and Sandeep Sen

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

Abstract
We present a fully dynamic algorithm for maintaining approximate maximum weight matching in general weighted graphs. The algorithm maintains a matching M whose weight is at least 1/8 M^{*} where M^{*} is the weight of the maximum weight matching. The algorithm achieves an expected amortized O(log n log C) time per edge insertion or deletion, where C is the ratio of the weights of the highest weight edge to the smallest weight edge in the given graph.
Cite as

Abhash Anand, Surender Baswana, Manoj Gupta, and Sandeep Sen. Maintaining Approximate Maximum Weighted Matching in Fully Dynamic Graphs. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 18, pp. 257-266, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{anand_et_al:LIPIcs.FSTTCS.2012.257,
  author =	{Anand, Abhash and Baswana, Surender and Gupta, Manoj and Sen, Sandeep},
  title =	{{Maintaining Approximate Maximum Weighted Matching in Fully  Dynamic Graphs}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)},
  pages =	{257--266},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-47-7},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{18},
  editor =	{D'Souza, Deepak and Radhakrishnan, Jaikumar and Telikepalli, Kavitha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2012.257},
  URN =		{urn:nbn:de:0030-drops-38648},
  doi =		{10.4230/LIPIcs.FSTTCS.2012.257},
  annote =	{Keywords: Matching, Dynamic Algorithm, Graph Algorithm}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2011.325
The update complexity of selection and related problems

Authors: Manoj Gupta, Yogish Sabharwal, and Sandeep Sen

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

Abstract
We present a framework for computing with input data specified by intervals, representing uncertainty in the values of the input parameters. To compute a solution, the algorithm can query the input parameters that yield more refined estimates in form of sub-intervals and the objective is to minimize the number of queries.The previous approaches address the scenario where every query returns an exact value. Our framework is more general as it can deal with a wider variety of inputs and query responses and we establish interesting relationships between them that have not been investigated previously. Although some of the approaches of the previous restricted models can be adapted to the more general model, we require more sophisticated techniques for the analysis and we also obtain improved algorithms for the previous model. We address selection problems in the generalized model and show that there exist 2-update competitive algorithms that do not depend on the lengths or distribution of the sub-intervals and hold against the worst case adversary. We also obtain similar bounds on the competitive ratio for the MST problem in graphs.
Cite as

Manoj Gupta, Yogish Sabharwal, and Sandeep Sen. The update complexity of selection and related problems. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 13, pp. 325-338, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{gupta_et_al:LIPIcs.FSTTCS.2011.325,
  author =	{Gupta, Manoj and Sabharwal, Yogish and Sen, Sandeep},
  title =	{{The update complexity of selection and related problems}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)},
  pages =	{325--338},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-34-7},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{13},
  editor =	{Chakraborty, Supratik and Kumar, Amit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2011.325},
  URN =		{urn:nbn:de:0030-drops-33314},
  doi =		{10.4230/LIPIcs.FSTTCS.2011.325},
  annote =	{Keywords: Uncertain data, Competitive analysis}
}
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact