Search Results

Documents authored by Yingchareonthawornchai, Sorrachai

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
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2022.37
Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver

Authors: Parinya Chalermsook, Chien-Chung Huang, Danupon Nanongkai, Thatchaphol Saranurak, Pattara Sukprasert, and Sorrachai Yingchareonthawornchai

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
In the k-edge-connected spanning subgraph (kECSS) problem, our goal is to compute a minimum-cost sub-network that is resilient against up to k link failures: Given an n-node m-edge graph with a cost function on the edges, our goal is to compute a minimum-cost k-edge-connected spanning subgraph. This NP-hard problem generalizes the minimum spanning tree problem and is the "uniform case" of a much broader class of survival network design problems (SNDP). A factor of two has remained the best approximation ratio for polynomial-time algorithms for the whole class of SNDP, even for a special case of 2ECSS. The fastest 2-approximation algorithm is however rather slow, taking O(mn k) time [Khuller, Vishkin, STOC'92]. A faster time complexity of O(n²) can be obtained, but with a higher approximation guarantee of (2k-1) [Gabow, Goemans, Williamson, IPCO'93]. Our main contribution is an algorithm that (1+ε)-approximates the optimal fractional solution in Õ(m/ε²) time (independent of k), which can be turned into a (2+ε) approximation algorithm that runs in time Õ(m/(ε²) + {k²n^{1.5}}/ε²) for (integral) kECSS; this improves the running time of the aforementioned results while keeping the approximation ratio arbitrarily close to a factor of two.
Cite as

Parinya Chalermsook, Chien-Chung Huang, Danupon Nanongkai, Thatchaphol Saranurak, Pattara Sukprasert, and Sorrachai Yingchareonthawornchai. Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 37:1-37:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{chalermsook_et_al:LIPIcs.ICALP.2022.37,
  author =	{Chalermsook, Parinya and Huang, Chien-Chung and Nanongkai, Danupon and Saranurak, Thatchaphol and Sukprasert, Pattara and Yingchareonthawornchai, Sorrachai},
  title =	{{Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{37:1--37:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.37},
  URN =		{urn:nbn:de:0030-drops-163785},
  doi =		{10.4230/LIPIcs.ICALP.2022.37},
  annote =	{Keywords: Approximation Algorithms, Data Structures}
}
Document
DOI: 10.4230/LIPIcs.SEA.2021.1
Engineering Nearly Linear-Time Algorithms for Small Vertex Connectivity

Authors: Max Franck and Sorrachai Yingchareonthawornchai

Published in: LIPIcs, Volume 190, 19th International Symposium on Experimental Algorithms (SEA 2021)

Abstract
Vertex connectivity is a well-studied concept in graph theory with numerous applications. A graph is k-connected if it remains connected after removing any k-1 vertices. The vertex connectivity of a graph is the maximum k such that the graph is k-connected. There is a long history of algorithmic development for efficiently computing vertex connectivity. Recently, two near linear-time algorithms for small k were introduced by [Forster et al. SODA 2020]. Prior to that, the best known algorithm was one by [Henzinger et al. FOCS'96] with quadratic running time when k is small. In this paper, we study the practical performance of the algorithms by Forster et al. In addition, we introduce a new heuristic on a key subroutine called local cut detection, which we call degree counting. We prove that the new heuristic improves space-efficiency (which can be good for caching purposes) and allows the subroutine to terminate earlier. According to experimental results on random graphs with planted vertex cuts, random hyperbolic graphs, and real world graphs with vertex connectivity between 4 and 15, the degree counting heuristic offers a factor of 2-4 speedup over the original non-degree counting version for most of our data. It also outperforms the previous state-of-the-art algorithm by Henzinger et al. even on relatively small graphs.
Cite as

Max Franck and Sorrachai Yingchareonthawornchai. Engineering Nearly Linear-Time Algorithms for Small Vertex Connectivity. In 19th International Symposium on Experimental Algorithms (SEA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 190, pp. 1:1-1:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{franck_et_al:LIPIcs.SEA.2021.1,
  author =	{Franck, Max and Yingchareonthawornchai, Sorrachai},
  title =	{{Engineering Nearly Linear-Time Algorithms for Small Vertex Connectivity}},
  booktitle =	{19th International Symposium on Experimental Algorithms (SEA 2021)},
  pages =	{1:1--1:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-185-6},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{190},
  editor =	{Coudert, David and Natale, Emanuele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2021.1},
  URN =		{urn:nbn:de:0030-drops-137735},
  doi =		{10.4230/LIPIcs.SEA.2021.1},
  annote =	{Keywords: Algorithm Engineering, Algorithmic Graph Theory, Sublinear Algorithms}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2015.34
Analysis of Bounds on Hybrid Vector Clocks

Authors: Sorrachai Yingchareonthawornchai, Sandeep S. Kulkarni, and Murat Demirbas

Published in: LIPIcs, Volume 46, 19th International Conference on Principles of Distributed Systems (OPODIS 2015)

Abstract
Hybrid vector clocks (HVC) implement vector clocks (VC) in a space-efficient manner by exploiting the availability of loosely-synchronized physical clocks at each node. In this paper, we develop a model for determining the bounds on the size of HVC. Our model uses four parameters, epsilon: uncertainty window, delta: minimum message delay, alpha: communication frequency and n: number of nodes in the system. We derive the size of HVC in terms of a differential equation, and show that the size predicted by our model is almost identical to the results obtained by simulation. We also identify closed form solutions that provide tight lower and upper bounds for useful special cases. Our model and simulations show the HVC size is a sigmoid function with respect to increasing epsilon; it has a slow start but it grows exponentially after a phase transition. We present equations to identify the phase transition point and show that for many practical applications and deployment environments, the size of HVC remains only as a couple entries and substantially less than n. We also find that, in a model with random unicast message transmissions, increasing n actually helps for reducing HVC size.
Cite as

Sorrachai Yingchareonthawornchai, Sandeep S. Kulkarni, and Murat Demirbas. Analysis of Bounds on Hybrid Vector Clocks. In 19th International Conference on Principles of Distributed Systems (OPODIS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 46, pp. 34:1-34:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{yingchareonthawornchai_et_al:LIPIcs.OPODIS.2015.34,
  author =	{Yingchareonthawornchai, Sorrachai and Kulkarni, Sandeep S. and Demirbas, Murat},
  title =	{{Analysis of Bounds on Hybrid Vector Clocks}},
  booktitle =	{19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
  pages =	{34:1--34:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-98-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{46},
  editor =	{Anceaume, Emmanuelle and Cachin, Christian and Potop-Butucaru, Maria},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.34},
  URN =		{urn:nbn:de:0030-drops-66771},
  doi =		{10.4230/LIPIcs.OPODIS.2015.34},
  annote =	{Keywords: Vector Clocks, Physical Clocks, Large Scale Systems}
}
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