6 Search Results for "Le, Hung"

Document
DOI: 10.4230/LIPIcs.SoCG.2023.47
Sparse Euclidean Spanners with Optimal Diameter: A General and Robust Lower Bound via a Concave Inverse-Ackermann Function

Authors: Hung Le, Lazar Milenković, and Shay Solomon

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Abstract
In STOC'95 [S. Arya et al., 1995] Arya et al. showed that any set of n points in ℝ^d admits a (1+ε)-spanner with hop-diameter at most 2 (respectively, 3) and O(n log n) edges (resp., O(n log log n) edges). They also gave a general upper bound tradeoff of hop-diameter k with O(n α_k(n)) edges, for any k ≥ 2. The function α_k is the inverse of a certain Ackermann-style function, where α₀(n) = ⌈n/2⌉, α₁(n) = ⌈√n⌉, α₂(n) = ⌈log n⌉, α₃(n) = ⌈log log n⌉, α₄(n) = log^* n, α₅(n) = ⌊ 1/2 log^*n ⌋, …. Roughly speaking, for k ≥ 2 the function α_{k} is close to ⌊(k-2)/2⌋-iterated log-star function, i.e., log with ⌊(k-2)/2⌋ stars. Despite a large body of work on spanners of bounded hop-diameter, the fundamental question of whether this tradeoff between size and hop-diameter of Euclidean (1+ε)-spanners is optimal has remained open, even in one-dimensional spaces. Three lower bound tradeoffs are known: - An optimal k versus Ω(n α_k(n)) by Alon and Schieber [N. Alon and B. Schieber, 1987], but it applies to stretch 1 (not 1+ε). - A suboptimal k versus Ω(nα_{2k+6}(n)) by Chan and Gupta [H. T.-H. Chan and A. Gupta, 2006]. - A suboptimal k versus Ω(n/(2^{6⌊k/2⌋}) α_k(n)) by Le et al. [Le et al., 2022]. This paper establishes the optimal k versus Ω(n α_k(n)) lower bound tradeoff for stretch 1+ε, for any ε > 0, and for any k. An important conceptual contribution of this work is in achieving optimality by shaving off an extremely slowly growing term, namely 2^{6⌊k/2⌋} for k ≤ O(α(n)); such a fine-grained optimization (that achieves optimality) is very rare in the literature. To shave off the 2^{6⌊k/2⌋} term from the previous bound of Le et al., our argument has to drill much deeper. In particular, we propose a new way of analyzing recurrences that involve inverse-Ackermann style functions, and our key technical contribution is in presenting the first explicit construction of concave versions of these functions. An important advantage of our approach over previous ones is its robustness: While all previous lower bounds are applicable only to restricted 1-dimensional point sets, ours applies even to random point sets in constant-dimensional spaces.
Cite as

Hung Le, Lazar Milenković, and Shay Solomon. Sparse Euclidean Spanners with Optimal Diameter: A General and Robust Lower Bound via a Concave Inverse-Ackermann Function. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 47:1-47:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{le_et_al:LIPIcs.SoCG.2023.47,
  author =	{Le, Hung and Milenkovi\'{c}, Lazar and Solomon, Shay},
  title =	{{Sparse Euclidean Spanners with Optimal Diameter: A General and Robust Lower Bound via a Concave Inverse-Ackermann Function}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{47:1--47:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.47},
  URN =		{urn:nbn:de:0030-drops-178976},
  doi =		{10.4230/LIPIcs.SoCG.2023.47},
  annote =	{Keywords: Euclidean spanners, Ackermann functions, convex functions, hop-diameter}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2022.54
Sparse Euclidean Spanners with Tiny Diameter: A Tight Lower Bound

Authors: Hung Le, Lazar Milenković, and Shay Solomon

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

Abstract
In STOC'95 [ADMSS95] Arya et al. showed that any set of n points in R^d admits a (1+ε)-spanner with hop-diameter at most 2 (respectively, 3) and O(n log n) edges (resp., O(n log log n) edges). They also gave a general upper bound tradeoff of hop-diameter at most k and O(n α_k(n)) edges, for any k≥2. The function α_k is the inverse of a certain Ackermann-style function at the ⌊k/2⌋th level of the primitive recursive hierarchy, where α₀(n)=⌈n/2⌉, α₁(n)=⌈√n⌉, α₂(n)=⌈log n⌉, α₃(n)=⌈log log n⌉, α₄(n)=log^* n, α₅(n)=⌊1/2 log^*n⌋, .... Roughly speaking, for k≥2 the function α_{k} is close to ⌊(k-2)/2⌋-iterated log-star function, i.e., log with ⌊(k-2)/2⌋ stars. Also, α_{2α(n)+4}(n)≤4, where α(n) is the one-parameter inverse Ackermann function, which is an extremely slowly growing function. Whether or not this tradeoff is tight has remained open, even for the cases k=2 and k=3. Two lower bounds are known: The first applies only to spanners with stretch 1 and the second is sub-optimal and applies only to sufficiently large (constant) values of k. In this paper we prove a tight lower bound for any constant k: For any fixed ε>0, any (1+ε)-spanner for the uniform line metric with hop-diameter at most k must have at least Ω(n α_k(n)) edges.
Cite as

Hung Le, Lazar Milenković, and Shay Solomon. Sparse Euclidean Spanners with Tiny Diameter: A Tight Lower Bound. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 54:1-54:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{le_et_al:LIPIcs.SoCG.2022.54,
  author =	{Le, Hung and Milenkovi\'{c}, Lazar and Solomon, Shay},
  title =	{{Sparse Euclidean Spanners with Tiny Diameter: A Tight Lower Bound}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{54:1--54:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.54},
  URN =		{urn:nbn:de:0030-drops-160629},
  doi =		{10.4230/LIPIcs.SoCG.2022.54},
  annote =	{Keywords: Euclidean spanners, hop-diameter, inverse-Ackermann, lower bounds, sparse spanners}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2022.96
Dynamic Matching Algorithms Under Vertex Updates

Authors: Hung Le, Lazar Milenković, Shay Solomon, and Virginia Vassilevska Williams

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract
Dynamic graph matching algorithms have been extensively studied, but mostly under edge updates. This paper concerns dynamic matching algorithms under vertex updates, where in each update step a single vertex is either inserted or deleted along with its incident edges. A basic setting arising in online algorithms and studied by Bosek et al. [FOCS'14] and Bernstein et al. [SODA'18] is that of dynamic approximate maximum cardinality matching (MCM) in bipartite graphs in which one side is fixed and vertices on the other side either arrive or depart via vertex updates. In the BASIC-incremental setting, vertices only arrive, while in the BASIC-decremental setting vertices only depart. When vertices can both arrive and depart, we have the BASIC-dynamic setting. In this paper we also consider the setting in which both sides of the bipartite graph are dynamic. We call this the MEDIUM-dynamic setting, and MEDIUM-decremental is the restriction when vertices can only depart. The GENERAL-dynamic setting is when the graph is not necessarily bipartite and the vertices can both depart and arrive. Denote by K the total number of edges inserted and deleted to and from the graph throughout the entire update sequence. A well-studied measure, the recourse of a dynamic matching algorithm is the number of changes made to the matching per step. We largely focus on Maximal Matching (MM) which is a 2-approximation to the MCM. Our main results are as follows. - In the BASIC-dynamic setting, there is a straightforward algorithm for maintaining a MM, with a total runtime of O(K) and constant worst-case recourse. In fact, this algorithm never removes an edge from the matching; we refer to such an algorithm as irrevocable. - For the MEDIUM-dynamic setting we give a strong conditional lower bound that even holds in the MEDIUM-decremental setting: if for any fixed η > 0, there is an irrevocable decremental MM algorithm with a total runtime of O(K ⋅ n^{1-η}), this would refute the OMv conjecture; a similar (but weaker) hardness result can be achieved via a reduction from the Triangle Detection conjecture. - Next, we consider the GENERAL-dynamic setting, and design an MM algorithm with a total runtime of O(K) and constant worst-case recourse. We achieve this result via a 1-revocable algorithm, which may remove just one edge per update step. As argued above, an irrevocable algorithm with such a runtime is not likely to exist. - Finally, back to the BASIC-dynamic setting, we present an algorithm with a total runtime of O(K), which provides an (e/(e-1))-approximation to the MCM. To this end, we build on the classic "ranking" online algorithm by Karp et al. [STOC'90]. Beyond the results, our work draws connections between the areas of dynamic graph algorithms and online algorithms, and it proposes several open questions that seem to be overlooked thus far.
Cite as

Hung Le, Lazar Milenković, Shay Solomon, and Virginia Vassilevska Williams. Dynamic Matching Algorithms Under Vertex Updates. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 96:1-96:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{le_et_al:LIPIcs.ITCS.2022.96,
  author =	{Le, Hung and Milenkovi\'{c}, Lazar and Solomon, Shay and Vassilevska Williams, Virginia},
  title =	{{Dynamic Matching Algorithms Under Vertex Updates}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{96:1--96:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.96},
  URN =		{urn:nbn:de:0030-drops-156923},
  doi =		{10.4230/LIPIcs.ITCS.2022.96},
  annote =	{Keywords: maximal matching, approximate matching, dynamic algorithm, vertex updates}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2020.33
Fully Dynamic Sequential and Distributed Algorithms for MAX-CUT

Authors: Omer Wasim and Valerie King

Published in: LIPIcs, Volume 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)

Abstract
This paper initiates the study of the MAX-CUT problem in fully dynamic graphs. Given a graph G = (V,E), we present deterministic fully dynamic distributed and sequential algorithms to maintain a cut on G which always contains at least |E|/2 edges in sublinear update time under edge insertions and deletions to G. Our results include the following deterministic algorithms: i) an O(Δ) worst-case update time sequential algorithm, where Δ denotes the maximum degree of G, ii) the first fully dynamic distributed algorithm taking O(1) rounds and O(Δ) total bits of communication per update in the Massively Parallel Computation (MPC) model with n machines and O(n) words of memory per machine. The aforementioned algorithms require at most one adjustment, that is, a move of one vertex from one side of the cut to the other. We also give the following fully dynamic sequential algorithms: i) a deterministic O(m^{1/2}) amortized update time algorithm where m denotes the maximum number of edges in G during any sequence of updates and, ii) a randomized algorithm which takes Õ(n^{2/3}) worst-case update time when edge updates come from an oblivious adversary.
Cite as

Omer Wasim and Valerie King. Fully Dynamic Sequential and Distributed Algorithms for MAX-CUT. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, pp. 33:1-33:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{wasim_et_al:LIPIcs.FSTTCS.2020.33,
  author =	{Wasim, Omer and King, Valerie},
  title =	{{Fully Dynamic Sequential and Distributed Algorithms for MAX-CUT}},
  booktitle =	{40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)},
  pages =	{33:1--33:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-174-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{182},
  editor =	{Saxena, Nitin and Simon, Sunil},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.33},
  URN =		{urn:nbn:de:0030-drops-132746},
  doi =		{10.4230/LIPIcs.FSTTCS.2020.33},
  annote =	{Keywords: data structures, dynamic graph algorithms, approximate maximum cut, distributed computing, parallel computing}
}
Document
DOI: 10.4230/LIPIcs.ESA.2020.67
Light Euclidean Spanners with Steiner Points

Authors: Hung Le and Shay Solomon

Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)

Abstract
The FOCS'19 paper of Le and Solomon [Hung Le and Shay Solomon, 2019], culminating a long line of research on Euclidean spanners, proves that the lightness (normalized weight) of the greedy (1+ε)-spanner in ℝ^d is Õ(ε^{-d}) for any d = O(1) and any ε = Ω(n^{-1/(d-1)}) (where Õ hides polylogarithmic factors of 1/ε), and also shows the existence of point sets in ℝ^d for which any (1+ε)-spanner must have lightness Ω(ε^{-d}). Given this tight bound on the lightness, a natural arising question is whether a better lightness bound can be achieved using Steiner points. Our first result is a construction of Steiner spanners in ℝ² with lightness O(ε^{-1} log Δ), where Δ is the spread of the point set. In the regime of Δ ≪ 2^(1/ε), this provides an improvement over the lightness bound of [Hung Le and Shay Solomon, 2019]; this regime of parameters is of practical interest, as point sets arising in real-life applications (e.g., for various random distributions) have polynomially bounded spread, while in spanner applications ε often controls the precision, and it sometimes needs to be much smaller than O(1/log n). Moreover, for spread polynomially bounded in 1/ε, this upper bound provides a quadratic improvement over the non-Steiner bound of [Hung Le and Shay Solomon, 2019], We then demonstrate that such a light spanner can be constructed in O_ε(n) time for polynomially bounded spread, where O_ε hides a factor of poly(1/(ε)). Finally, we extend the construction to higher dimensions, proving a lightness upper bound of Õ(ε^{-(d+1)/2} + ε^{-2} log Δ) for any 3 ≤ d = O(1) and any ε = Ω(n^{-1/(d-1)}).
Cite as

Hung Le and Shay Solomon. Light Euclidean Spanners with Steiner Points. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 67:1-67:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{le_et_al:LIPIcs.ESA.2020.67,
  author =	{Le, Hung and Solomon, Shay},
  title =	{{Light Euclidean Spanners with Steiner Points}},
  booktitle =	{28th Annual European Symposium on Algorithms (ESA 2020)},
  pages =	{67:1--67:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-162-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{173},
  editor =	{Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.67},
  URN =		{urn:nbn:de:0030-drops-129331},
  doi =		{10.4230/LIPIcs.ESA.2020.67},
  annote =	{Keywords: Euclidean spanners, Steiner spanners, light spanners}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2016.8
Optimal Dynamic Program for r-Domination Problems over Tree Decompositions

Authors: Glencora Borradaile and Hung Le

Published in: LIPIcs, Volume 63, 11th International Symposium on Parameterized and Exact Computation (IPEC 2016)

Abstract
There has been recent progress in showing that the exponential dependence on treewidth in dynamic programming algorithms for solving NP-hard problems is optimal under the Strong Exponential Time Hypothesis (SETH). We extend this work to r-domination problems. In r-dominating set, one wishes to find a minimum subset S of vertices such that every vertex of G is within r hops of some vertex in S. In connected r-dominating set, one additionally requires that the set induces a connected subgraph of G. We give a O((2r+1)^tw n) time algorithm for r-dominating set and a randomized O((2r+2)^tw n^{O(1)}) time algorithm for connected r-dominating set in n-vertex graphs of treewidth tw. We show that the running time dependence on r and tw is the best possible under SETH. This adds to earlier observations that a "+1" in the denominator is required for connectivity constraints.
Cite as

Glencora Borradaile and Hung Le. Optimal Dynamic Program for r-Domination Problems over Tree Decompositions. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 8:1-8:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{borradaile_et_al:LIPIcs.IPEC.2016.8,
  author =	{Borradaile, Glencora and Le, Hung},
  title =	{{Optimal Dynamic Program for r-Domination Problems over Tree Decompositions}},
  booktitle =	{11th International Symposium on Parameterized and Exact Computation (IPEC 2016)},
  pages =	{8:1--8:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-023-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{63},
  editor =	{Guo, Jiong and Hermelin, Danny},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2016.8},
  URN =		{urn:nbn:de:0030-drops-69199},
  doi =		{10.4230/LIPIcs.IPEC.2016.8},
  annote =	{Keywords: r-dominating set, Exponential Time Hypothesis, Dynamic Programming}
}
  • Refine by Author
  • 5 Le, Hung
  • 4 Solomon, Shay
  • 3 Milenković, Lazar
  • 1 Borradaile, Glencora
  • 1 King, Valerie
  • Show More...

  • Refine by Classification
  • 2 Theory of computation → Computational geometry
  • 1 Theory of computation
  • 1 Theory of computation → Design and analysis of algorithms
  • 1 Theory of computation → Dynamic graph algorithms
  • 1 Theory of computation → Sparsification and spanners

  • Refine by Keyword
  • 3 Euclidean spanners
  • 2 hop-diameter
  • 1 Ackermann functions
  • 1 Dynamic Programming
  • 1 Exponential Time Hypothesis
  • Show More...

  • Refine by Type
  • 6 document

  • Refine by Publication Year
  • 2 2020
  • 2 2022
  • 1 2017
  • 1 2023

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