2 Search Results for "Singh, Aditi"

Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022.1
A Unified Approach to Discrepancy Minimization

Authors: Nikhil Bansal, Aditi Laddha, and Santosh Vempala

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

Abstract
We study a unified approach and algorithm for constructive discrepancy minimization based on a stochastic process. By varying the parameters of the process, one can recover various state-of-the-art results. We demonstrate the flexibility of the method by deriving a discrepancy bound for smoothed instances, which interpolates between known bounds for worst-case and random instances.
Cite as

Nikhil Bansal, Aditi Laddha, and Santosh Vempala. A Unified Approach to Discrepancy Minimization. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 1:1-1:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bansal_et_al:LIPIcs.APPROX/RANDOM.2022.1,
  author =	{Bansal, Nikhil and Laddha, Aditi and Vempala, Santosh},
  title =	{{A Unified Approach to Discrepancy Minimization}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
  pages =	{1:1--1:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-249-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{245},
  editor =	{Chakrabarti, Amit and Swamy, Chaitanya},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.1},
  URN =		{urn:nbn:de:0030-drops-171238},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2022.1},
  annote =	{Keywords: Discrepancy theory, smoothed analysis}
}
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-dev.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}
}
  • Refine by Author
  • 1 Bansal, Nikhil
  • 1 Gupta, Manoj
  • 1 Laddha, Aditi
  • 1 Singh, Aditi
  • 1 Vempala, Santosh

  • Refine by Classification
  • 1 Theory of computation → Data structures design and analysis
  • 1 Theory of computation → Design and analysis of algorithms
  • 1 Theory of computation → Graph algorithms analysis
  • 1 Theory of computation → Shortest paths

  • Refine by Keyword
  • 1 Data-Structures
  • 1 Discrepancy theory
  • 1 Distance Oracles
  • 1 Fault Tolerant Algorithms
  • 1 Graph Algorithms
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2018
  • 1 2022

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 Imprint Privacy Contact