Source author record

Sorrachai Yingchareonthawornchai

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Distributed, Parallel, and Cluster Computing

Catalog footprint

Research overview

3works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver

In the $k$ -edge-connected spanning subgraph ( $k$ ECSS) 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 $2$ ECSS. 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^2)$ 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 $\tilde O(m/ε^2)$ time (independent of $k$ ), which can be turned into a $(2+ε)$ approximation algorithm that runs in time $\tilde O\left(\frac{m}{ε^2} + \frac{k^2n^{1.5}}{ε^2}\right)$ for (integral) $k$ ECSS; this improves the running time of the aforementioned results while keeping the approximation ratio arbitrarily close to a factor of two.

preprint2021arXiv

Breaking Quadratic Time for Small Vertex Connectivity and an Approximation Scheme

Vertex 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(n^2)$ time even for $k=4$ and $m=O(n)$ . In the simplest case where $m=O(n)$ and $k=O(1)$ , the $O(n^2)$ bound dates five decades back to [Kleitman IEEE Trans. Circuit Theory'69]. For general $k$ and $m$ , the best bound is $\tilde{O}(\min(kn^2, n^ω+nk^ω))$ . In this paper, we present a randomized Monte Carlo algorithm with $\tilde{O}(m+k^{7/3}n^{4/3})$ time for any $k=O(\sqrt{n})$ . This gives the {\em first subquadratic time} bound for any $4\leq k \leq o(n^{2/7})$ and improves all above classic bounds for all $k\le n^{0.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 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(n^2)$ 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.

preprint2016arXiv

Precision, Recall, and Sensitivity of Monitoring Partially Synchronous Distributed Systems

Runtime verification focuses on analyzing the execution of a given program by a monitor to determine if it is likely to violate its specifications. There is often an impedance mismatch between the assumptions/model of the monitor and that of the underlying program. This constitutes problems especially for distributed systems, where the concept of current time and state are inherently uncertain. A monitor designed with asynchronous system model assumptions may cause false-positives for a program executing in a partially synchronous system: the monitor may flag a global predicate that does not actually occur in the underlying system. A monitor designed with a partially synchronous system model assumption may cause false negatives as well as false positives for a program executing in an environment where the bounds on partial synchrony differ (albeit temporarily) from the monitor model assumptions. In this paper we analyze the effects of the impedance mismatch between the monitor and the underlying program for the detection of conjunctive predicates. We find that there is a small interval where the monitor assumptions are hypersensitive to the underlying program environment. We provide analytical derivations for this interval, and also provide simulation support for exploring the sensitivity of predicate detection to the impedance mismatch between the monitor and the program under a partially synchronous system.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.