Browsing by Author "Saranurak, Thatchaphol"
Now showing 1 - 7 of 7
- Results Per Page
- Sort Options
- Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver
A4 Artikkeli konferenssijulkaisussa(2022-07-01) Chalermsook, Parinya; Huang, Chien Chung; Nanongkai, Danupon; Saranurak, Thatchaphol; Sukprasert, Pattara; Yingchareonthawornchai, SorrachaiIn 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(mnk) time [Khuller, Vishkin, STOC'92]. A faster time complexity of O(n2) 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/ε2) time (independent of k), which can be turned into a (2 + ε) approximation algorithm that runs in time (Equation presented) for (integral) kECSS; this improves the running time of the aforementioned results while keeping the approximation ratio arbitrarily close to a factor of two. - Breaking quadratic time for small vertex connectivity and an approximation scheme
A4 Artikkeli konferenssijulkaisussa(2019-06-23) Nanongkai, Danupon; Saranurak, Thatchaphol; Yingchareonthawornchai, SorrachaiVertex connectivity a classic extensively-studied problem. Given an integer k, its goal is to decide if an n-node m-edge graph can be disconnected by removing k vertices. Although a linear-time algorithm was postulated since 1974 [Aho, Hopcroft and Ullman], and despite its sibling problem of edge connectivity being resolved over two decades ago [Karger STOC’96], so far no vertex connectivity algorithms are faster than O(n2) time even for k = 4 and m = O(n). In the simplest case where m = O(n) and k = O(1), the O(n2) bound dates five decades back to [Kleitman IEEE Trans. Circuit Theory’69]. For higher m, O(m) time is known for k ≤ 3 [Tarjan FOCS’71; Hopcroft, Tarjan SICOMP’73], the first O(n2) time is from [Kanevsky, Ramachandran, FOCS’87] for k = 4 and from [Nagamochi, Ibaraki, Algorithmica’92] for k = O(1). For general k and m, the best bound is Õ (min(kn2, nω + nkω )) [Henzinger, Rao, Gabow FOCS’96; Linial, Lovász, Wigderson FOCS’86] where Õ hides polylogarithmic terms and ω < 2.38 is the matrix multiplication exponent. In this paper, we present a randomized Monte Carlo algorithm with Õ (m + k7/3n4/3) time for any k = O(n). This gives the first subquadratic time bound for any 4 ≤ k ≤ o(n2/7) (subquadratic time refers to O(m) + o(n2) time.) and improves all above classic bounds for all k ≤ n0.44. We also present a new randomized Monte Carlo (1 + ϵ)-approximation algorithm that is strictly faster than the previous Henzinger’s 2-approximation algorithm [J. Algorithms’97] and all previous exact algorithms. The story is the same for the directed case, where our exact Õ (min(km2/3n, km4/3))-time for any k = O(n) and (1 + ϵ)-approximation algorithms improve all previous exact bounds. Additionally, our algorithm is the first approximation algorithm on directed graphs. The key to our results is to avoid computing single-source connectivity, which was needed by all previous exact algorithms and is not known to admit o(n2) time. Instead, we design the first local algorithm for computing vertex connectivity; without reading the whole graph, our algorithm can find a separator of size at most k or certify that there is no separator of size at most k “near” a given seed node. - Deterministic Small Vertex Connectivity in Almost Linear Time
A4 Artikkeli konferenssijulkaisussa(2022-10-30) Saranurak, Thatchaphol; Yingchareonthawornchai, SorrachaiIn the vertex connectivity problem, given an undirected n-vertex m-edge graph G, we need to compute the minimum number of vertices that can disconnect G after removing them. This problem is one of the most well-studied graph problems. From 2019, a new line of work [Nanongkai et al.~STOC'19;SODA'20;STOC'21] has used randomized techniques to break the quadratic-time barrier and, very recently, culminated in an almost-linear time algorithm via the recently announced max-flow algorithm by Chen et al. In contrast, all known deterministic algorithms are much slower. The fastest algorithm [Gabow FOCS'00] takes O(m(n+min{c^(5/2),cn^(3/4)})) time where c is the vertex connectivity. It remains open whether there exists a subquadratic-time deterministic algorithm for any constant c>3. In this paper, we give the first deterministic almost-linear time vertex connectivity algorithm for all constants c. Our running time is m1+o(1)2O(c2) time, which is almost-linear for all c=o(sqrt(log n)). This is the first deterministic algorithm that breaks the O(n^2)-time bound on sparse graphs where m=O(n), which is known for more than 50 years ago [Kleitman'69]. Towards our result, we give a new reduction framework to vertex expanders which in turn exploits our new almost-linear time construction of mimicking network for vertex connectivity. The previous construction by Kratsch and Wahlström [FOCS'12] requires large polynomial time and is randomized. - Multi-finger binary search trees
A4 Artikkeli konferenssijulkaisussa(2018) Chalermsook, Parinya; Goswami, Mayank; Kozma, László; Mehlhorn, Kurt; Saranurak, Thatchaphol - Pinning down the strong wilber 1 bound for binary search trees
A4 Artikkeli konferenssijulkaisussa(2020-08-01) Chalermsook, Parinya; Chuzhoy, Julia; Saranurak, ThatchapholThe dynamic optimality conjecture, postulating the existence of an O(1)-competitive online algorithm for binary search trees (BSTs), is among the most fundamental open problems in dynamic data structures. Despite extensive work and some notable progress, including, for example, the Tango Trees (Demaine et al., FOCS 2004), that give the best currently known O(log log n)-competitive algorithm, the conjecture remains widely open. One of the main hurdles towards settling the conjecture is that we currently do not have approximation algorithms achieving better than an O(log log n)-approximation, even in the offline setting. All known non-trivial algorithms for BST's so far rely on comparing the algorithm's cost with the so-called Wilber's first bound (WB-1). Therefore, establishing the worst-case relationship between this bound and the optimal solution cost appears crucial for further progress, and it is an interesting open question in its own right. Our contribution is two-fold. First, we show that the gap between the WB-1 bound and the optimal solution value can be as large as Ω(log log n/log log log n); in fact, we show that the gap holds even for several stronger variants of the bound. Second, we provide a simple algorithm, that, given an integer D > 0, obtains an O(D)-approximation in time exp ( O (n1/2Ω(D) log n )). In particular, this yields a constant-factor approximation algorithm with sub-exponential running time. Moreover, we obtain a simpler and cleaner efficient O(log log n)-approximation algorithm that can be used in an online setting. Finally, we suggest a new bound, that we call the Guillotine Bound, that is stronger than WB-1, while maintaining its algorithm-friendly nature, that we hope will lead to better algorithms. All our results use the geometric interpretation of the problem, leading to cleaner and simpler analysis. - Pinning Down the Strong Wilber-1 Bound for Binary Search Trees
A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä(2023-12-19) Chalermsook, Parinya; Chuzhoy, Julia; Saranurak, ThatchapholDynamic Optimality Conjecture, postulating the existence of an O(1)-competitive online algorithm for binary search trees (BSTs), is among the most fundamental open problems in dynamic data structures. The conjecture remains wide open, despite extensive work and some notable progress, including, for example, the O(loglogn)-competitive Tango Trees, which is the best currently known competitive ratio. One of the main hurdles towards settling the conjecture is that we currently do not have polynomial-time approximation algorithms achieving better than an O(loglogn)-approximation, even in the offline setting. All known non-trivial algorithms for BSTs rely on comparing the algorithm's cost with the so-called Wilber-1 bound (WB-1). Therefore, establishing the worst-case relationship between this bound and the optimal solution cost appears crucial for further progress, and it is an interesting open question in its own right. Our contribution is twofold. First, we show that the gap between WB-1 and the optimal solution value can be as large as Ω(loglogn/logloglogn) ; in fact, we show that the gap holds even for several stronger variants of the bound.∗ Second, we show, given an integer D>0, a D-approximation algorithm that runs in time exp(O(n1/2Ω(D)logn)). In particular, this yields a constant-factor approximation algorithm with subexponential running time.∗∗ Moreover, we obtain a simpler and cleaner efficient O(loglogn)-approximation algorithm that can be used in an online setting. Finally, we suggest a new bound, that we call the Guillotine Bound, that is stronger than WB-1, while maintaining its algorithm-friendly nature, that we hope will lead to better algorithms. All our results use the geometric interpretation of the problem, leading to cleaner and simpler analysis. - Vertex Connectivity in Poly-Logarithmic Max-Flows
A4 Artikkeli konferenssijulkaisussa(2021-06-15) Li, Jason; Nanongkai, Danupon; Panigrahi, Debmalya; Saranurak, Thatchaphol; Yingchareonthawornchai, SorrachaiThe vertex connectivity of an m-edge n-vertex undirected graph is the smallest number of vertices whose removal disconnects the graph, or leaves only a singleton vertex. In this paper, we give a reduction from the vertex connectivity problem to a set of maxflow instances. Using this reduction, we can solve vertex connectivity in (mα) time for any α ≥ 1, if there is a mα-time maxflow algorithm. Using the current best maxflow algorithm that runs in m4/3+o(1) time (Kathuria, Liu and Sidford, FOCS 2020), this yields a m4/3+o(1)-time vertex connectivity algorithm. This is the first improvement in the running time of the vertex connectivity problem in over 20 years, the previous best being an Õ(mn)-time algorithm due to Henzinger, Rao, and Gabow (FOCS 1996). Indeed, no algorithm with an o(mn) running time was known before our work, even if we assume an (m)-time maxflow algorithm. Our new technique is robust enough to also improve the best Õ(mn)-time bound for directed vertex connectivity to mn1−1/12+o(1) time